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,^[1] 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, ...^[2]

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:^[3]

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

La funzione generatrice $m(x)=\sum _{n=0}^{\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^[4]

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,^[5] mentre nel 2001, un altro studio ha dimostrato che le involuzioni vessillari sono enumerate dai numeri di Motzkin.^[6]