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 (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.

Număr Motzkin

Numit după	Theodore Motzkin
Anul publicării	1948
Autorul publicării	Theodore Motzkin
Nr. de termeni cunoscuți	infinit
Formula	v. Proprietăți
Primii termeni	1, 1, 2, 4, 9, 21, 51
Index OEIS	A001006 Motzkin

Numerele Motzkin $M_{n}$ pentru $n=0,1,\dots$ formează șirul:

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ță:

$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 $M_{0}=M_{1}=1$.

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

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

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

$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. La data de octombrie 2013^[update]. Se cunosc doar patru asemenea numere:

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.

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.