Numero di Motzkin

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

In matematica, dati n punti su una circonferenza, si definisce come numero di Motzkin, , il numero di modi in cui si possono tracciare tra questi delle corde non intersecanti, senza che tutti i punti siano necessariamente toccati da una corda.

La successione di tali numeri interi, che prende il nome dal matematico statunitense Theodore Motzkin,[1] trova diverse applicazioni in geometria, combinatoria e teoria dei numeri, e, per , ha come primi elementi:

1, 1, 2, 4, 9, 21, 51, 125, 323, 835, 2 188, 5 798, 15 511, 41 835, 113 634, 310 572, 853 467, 2 356 779, 6 536 382, 18 199 284, 50 852 019, 142 547 559, 400 763 223, 1 129 760 415, 3 192 727 797, 9 043 402 501, 25 669 818 476, 73 007 772 802, 208 023 278 209, 593 742 784 829, ...[2]

La figura seguente mostra i 9 modi di disegnare corde non intersecanti tra 4 punti di una circonferenza ():

La figura seguente mostra invece i 21 modi di disegnare corde non intersecanti tra 5 punti di una circonferenza ():

I numeri di Motzkin soddisfano le seguenti relazioni di ricorrenza:

I numeri di Motzkin possono essere espressi in termini di coefficienti binomiali e di numeri di Catalan:[3]

La funzione generatrice dei numeri di Motzkin soddisfa la condizione:

.

Un primo di Motzkin è un numero primo che appartiene alla sequenza dei numeri di Motzkin. Al 2021, sono noti quattro di questi numeri:

2, 127, 15 511, 953 467 954 114 363[4]

Interpretazioni combinatorie

[modifica | modifica wikitesto]

Il numero di Motzkin per n punti è anche il numero di sequenze di interi positivi di lunghezza aventi come elemento iniziale e finale i numeri 1 o 2 e la differenza tra elementi consecutivi pari a −1, 0 o 1. Allo stesso modo, il numero di Motzkin per n punti è anche il numero di sequenze di interi positivi di lunghezza aventi come elemento iniziale e finale il numero 1 e la differenza tra elementi consecutivi pari a −1, 0 o 1.

Inoltre, dato un sistema di riferimento cartesiano, il numero di Motzkin per n punti è il numero di cammini che è possibile fare in una griglia nel quadrante superiore destro per andare dal punto di coordinate (0,0) al punto di coordinate (n,0) in n passi e ammettendo di potersi muovere solo verso destra (in su, in giù o alla stessa quota) ad ogni passo ma senza poter scendere oltre y = 0.

Ad esempio, la figura seguente mostra i 9 cammini di Motzkin validi per passare da (0,0) a (4,0):

In uno studio sui numeri di Motzkin effettuato nel 1977 da R. Donaghey e L. W. Shapiro, sono state identificate almeno 14 manifestazioni dei numeri di Motzkin in diverse branche della matematica,[5] mentre nel 2001, un altro studio ha dimostrato che le involuzioni vessillari sono enumerate dai numeri di Motzkin.[6]

  1. ^ T. S. Motzkin, Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products, in Bulletin of the American Mathematical Society, vol. 54, n. 4, 1948, pp. 352-360, DOI:10.1090/S0002-9904-1948-09002-4.
  2. ^ (EN) N. J. A. Sloane, Sequenza A001006, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation. URL consultato il 3 maggio 2021.
  3. ^ Frank R. Bernhart, Catalan, Motzkin, and Riordan numbers, in Discrete Mathematics, vol. 204, n. 1-3, 1999, pp. 73-112, DOI:10.1016/S0012-365X(99)00054-0.
  4. ^ (EN) Eric W. Weisstein, Sequenza A092832, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation. URL consultato il 3 maggio 2021.
  5. ^ R. Donaghey e L. W. Shapiro, Motzkin numbers, in Journal of Combinatorial Theory, vol. 23, n. 3, 1977, pp. 291-301, DOI:10.1016/0097-3165(77)90020-6.
  6. ^ O. Guibert, E. Pergola e R. Pinzani, Vexillary involutions are enumerated by Motzkin numbers, in Annals of Combinatorics, vol. 5, n. 2, 2001, pp. 153-174, DOI:10.1007/PL00001297, ISSN 0218-0006 (WC · ACNP).

Voci correlate

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica