Numero di Motzkin

In matematica, dati n punti su una circonferenza, si definisce come numero di Motzkin, $M_n$, 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, trova diverse applicazioni in geometria, combinatoria e teoria dei numeri, e, per $n=0,1,\dots$, 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, ...

Esempi

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

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

Proprietà

I numeri di Motzkin soddisfano le seguenti relazioni di ricorrenza:

$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}.$

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

$M_n=\sum _{k=0}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n}{2k})C_k.$

La funzione generatrice $m(x)=\sum _{n=0}^{\mathrm{\infty }}{M}_n{x}^n$ dei numeri di Motzkin soddisfa la condizione:

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

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

Interpretazioni combinatorie

Il numero di Motzkin per n punti è anche il numero di sequenze di interi positivi di lunghezza $n-1$ 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 $n+1$ 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, mentre nel 2001, un altro studio ha dimostrato che le involuzioni vessillari sono enumerate dai numeri di Motzkin.

Voci correlate

• Numero di Delannoy
• Numero di Narayana
• Numero di Schröder

Collegamenti esterni

• Template:Collegamenti esterni