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, 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, , , , , , , , , , , , , , , , , , , , , ...
Esempi 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 ():
Proprietà 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:
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, ,
Interpretazioni combinatorie 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, mentre nel 2001, un altro studio ha dimostrato che le involuzioni vessillari sono enumerate dai numeri di Motzkin.
Note
Voci correlate Numero di Delannoy Numero di Narayana Numero di Schröder
Altri progetti
Collegamenti esterni
Categoria:Successioni di interi