Sari la conținut

Număr Motzkin

De la Wikipedia, enciclopedia liberă
Număr Motzkin
Numit dupăTheodore Motzkin
Anul publicării1948
Autorul publicăriiTheodore Motzkin
Nr. de termeni cunoscuțiinfinit
Formulav. Proprietăți
Primii termeni1, 1, 2, 4, 9, 21, 51
Index OEIS

Î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 pentru 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, ...

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

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

Proprietăți

[modificare | modificare sursă]

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

unde .

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

Funcția genertoare a numerelor Motzkin satisface relația:

.

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

2, 127, 15511, 953467954114363

Interpretări combinatorice

[modificare | modificare sursă]

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.

  1. ^ a b Șirul A001006 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  2. ^ a b c d Marius Coman, Enciclopedia matematică a claselor de numere întregi, Columbus, Ohio: Education Publishing, 2013, ISBN: 978-1-59973-237-4, p. 52
  3. ^ Șirul A092832 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  • en Bernhart, Frank R. (), „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. (), „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. (), „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 (), „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 

Legături externe

[modificare | modificare sursă]