Număr Motzkin

În matematică un număr Motzkin, n, este numărul diferitelor moduri de a trasa coarde care nu se intersectează între n puncte pe un cerc^[1] (nu este obligatoriu ca din fiecare punct să fie trasată o coardă). Numerele Motzkin sunt numite după Theodore Motzkin și au diverse aplicații în geometrie, combinatorică și teoria numerelor.

Numerele Motzkin ${\displaystyle M_{n}}$ pentru ${\displaystyle n=0,1,\dots }$ formează șirul:^[1][2]

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ...

Exemple

Următoarea figură prezintă cele 9 moduri de a trasa coarde care nu se intersectează între 4 puncte pe un cerc (M₄ = 9):

Următoarea figură prezintă cele 21 de moduri de a trasa coarde care nu se intersectează între 5 puncte pe un cerc (M₅ = 21):

Proprietăți

Numerele Motzkin satisfac următoarele relații de recurență:^[2]

${\displaystyle M_{n}=M_{n-1}+\sum _{i=0}^{n-2}M_{i}M_{n-2-i}={\frac {2n+1}{n+2}}M_{n-1}+{\frac {3n-3}{n+2}}M_{n-2}.}$

unde ${\displaystyle M_{0}=M_{1}=1}$.

Numerele Motzkin pot fi exprimate prin coeficienți binomial și numere Catalan:

${\displaystyle M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k}.}$

Funcția genertoare ${\displaystyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}}$ a numerelor Motzkin satisface relația:

${\displaystyle x^{2}m(x)^{2}+(x-1)m(x)+1=0}$.

Un număr prim Motzkin este un număr Motzkin care este și prim.^[2] La data de octombrie 2013^[update]. Se cunosc doar patru asemenea numere:^[2][3]

2, 127, 15511, 953467954114363

Interpretări combinatorice

Al n-lea număr Motzkin este și numărul de secvențe întregi pozitive de lungime n − 1 în care elementele de început și sfârșit sunt fie 1 sau 2, iar diferența dintre oricare două elemente consecutive este −1, 0 sau 1. Echivalent, al n-lea număr Motzkin este numărul de secvențe întregi pozitive de lungime n + 1 în care elementele de început și sfârșit sunt 1, iar diferența dintre oricare două elemente consecutive este −1, 0 sau 1.

Al n-lea număr Motzkin dă și numărul de căi din primul cadran (dreapta sus) al unei grile de la coordonatele (0, 0) la coordonatele (n, 0) în n pași dacă cineva are voie să se deplaseze doar spre dreapta (în sus, în jos sau înainte) la fiecare pas, dar este interzis să tracă sub axa y = 0.

De exemplu, imaginea următoare arată cele 9 căi valide de la (0, 0) la (4, 0):

Există cel puțin paisprezece utilizări diferite ale numerelor Motzkin în diferite ramuri ale matematicii, cum le-a enumerat Donaghey & Shapiro (1977) în studiul numerelor Motzkin. Guibert, Pergola & Pinzani (2001) a arătat că permutările vexilare sunt enumerate prin numere Motzkin.

Note

Bibliografie

• en Bernhart, Frank R. (1999), „Catalan, Motzkin, and Riordan numbers”, Discrete Mathematics, 204 (1-3): 73–112, doi:10.1016/S0012-365X(99)00054-0 
• en Donaghey, R.; Shapiro, L. W. (1977), „Motzkin numbers”, Journal of Combinatorial Theory, Series A, 23 (3): 291–301, doi:10.1016/0097-3165(77)90020-6, MR 0505544 
• en Guibert, O.; Pergola, E.; Pinzani, R. (2001), „Vexillary involutions are enumerated by Motzkin numbers”, Annals of Combinatorics, 5 (2): 153–174, doi:10.1007/PL00001297, ISSN 0218-0006, MR 1904383 
• en Motzkin, Theodore (1948), „Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products”, Bulletin of the American Mathematical Society, 54 (4): 352–360, doi:10.1090/S0002-9904-1948-09002-4 

Vezi și

• Număr Delannoy
• Număr Narayana
• Număr Schröder
• Număr Schröder–Hiparh
• Număr Catalan

Legături externe

• en Eric W. Weisstein, Motzkin Number la MathWorld.