Număr Motzkin

Format:Infocaseta Șiruri de numere întregi În matematică un număr Motzkin, Format:Mvar, este numărul diferitelor moduri de a trasa coarde care nu se intersectează între Format:Mvar 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.

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 (Format:Math):

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

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 }(\genfrac{}{}{0ex}{}{n}{2k})C_k.$

Funcția genertoare $m(x)=\sum _{n=0}^{\mathrm{\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. Format:Asof. Se cunosc doar patru asemenea numere:

2, 127, 15511, 953467954114363

Interpretări combinatorice

Al Format:Mvar-lea număr Motzkin este și numărul de secvențe întregi pozitive de lungime Format:Math î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 Format:Mvar-lea număr Motzkin este numărul de secvențe întregi pozitive de lungime Format:Math î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 Format:Mvar-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 (Format:Mvar, 0) în Format:Mvar 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 Format:Mvar = 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 Format:Harvtxt în studiul numerelor Motzkin. Format:Harvtxt a arătat că permutările vexilare sunt enumerate prin numere Motzkin.

Bibliografie

• Format:En icon Format:Citation
• Format:En icon Format:Citation
• Format:En icon Format:Citation
• Format:En icon Format:Citation

Vezi și

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

Legături externe

• Format:En icon Format:MathWorld