In matematica, data una griglia rettangolare nel 1° quadrante di un sistema di riferimento cartesiano, il numero di Delannoy, , descrive il numero di cammini possibili per arrivare dal punto di coordinate (0, 0) al punto di coordinate (m, n), ammettendo di potersi muovere soltanto in verticale e in orizzontale o in diagonale verso nord-est.
Il numero di Delannoy, , che prende il nome dal matematico e ufficiale dell'esercito francese Henri Delannoy, rappresenta anche il numero di allineamenti globali di due sequenze di lunghezza e , il numero di punti in un reticolo intero m-dimensionale che sono al massimo a n passi di distanza dall'origine, e, in un automa cellulare, il numero di celle in un intorno di von Neumann m-dimensionale di raggio n.
Esempio Il numero di cammini possibili per arrivare, con le sopraccitate condizioni, al punto di coordinate (3,3) partendo dal punto di coordinate (0,0), ossia il numero di Delannoy D(3,3) è pari a 63, come riportato nella seguente figura:
Il sottoinsieme dato dai cammini che non contengono punti al di sopra della diagonale data da costituisce un'altra famiglia di numeri: i numeri di Schröder.
Disposizione di Delannoy La disposizione di Delannoy, chiamata anche array di Delannoy, è una matrice infinita di numeri di Delannoy:
{| class="wikitable" |- ! ! width="50" | 0 ! width="50" | 1 ! width="50" | 2 ! width="50" | 3 ! width="50" | 4 ! width="50" | 5 ! width="50" | 6 ! width="50" | 7 ! width="50" | 8 |- ! 0 | 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 |- ! 1 | 1 || 3 || 5 || 7 || 9 || 11 || 13 || 15 || 17 |- ! 2 | 1 || 5 || 13 || 25 || 41 || 61 || 85 || 113 || 145 |- ! 3 | 1 || 7 || 25 || 63 || 129 || 231 || 377 || 575 || 833 |- ! 4 | 1 || 9 || 41 || 129 || 321 || 681 || || || |- ! 5 | 1 || 11 || 61 || 231 || 681 || || || || |- ! 6 | 1 || 13 || 85 || 377 || || || || || |- ! 7 | 1 || 15 || 113 || 575 || || || || || |- ! 8 | 1 || 17 || 145 || 833 || || || || || |- ! 9 | 1 || 19 || 181 || || || || || ||
In tale matrice, i numeri nella prima riga sono tutti 1, i numeri della seconda riga sono i numeri dispari, i numeri della terza riga sono i numeri quadrati centrati e i numeri della quarta riga sono i numeri ottaedrici centrati. Gli stessi numeri possono poi essere ordinati in una disposizione triangolare che ricorda il triangolo di Pascal, chiamata, in cui ogni numero è dato dalla somma dei tre numeri formanti un triangolo sopra di esso: 1 1 1 1 3 1 1 5 5 1 1 7 13 7 1 1 9 25 25 9 1 1 11 41 63 41 11 1
Numeri di Delannoy centrali I numeri di Delannoy centrali, D(n) = D(n,n), sono i numeri relativi a una griglia quadrata di dimensione n × n. I primi numeri centrali di Delannoy (partendo dal caso n=0) sono:
1, 3, 13, 63, 321, , , , , ...
Calcolo Numeri di Delannoy Per raggiungere il punto di coordinate , per passi diagonali ci devono essere passi in direzione e passi in direzione ; poiché tali passi possono essere compiuti in qualunque ordine, il numero dei cammini possibili è per raggiungere il suddetto punto è data dal coefficiente multinomiale . Quindi, sia ha la seguente espressione in forma compatta:
Un'espressione alternativa è data dalla da:
o dalla serie infinita:
E anche da:
dove è data dalla successione "A266213".
Si vede che la relazione di ricorrenza fondamentale per i numeri di Delannoy è:
Tale relazione di ricorrenza conduce direttamente alla funzione generatrice:
Numeri di Delannoy centrali Sostituendo nella prima espressione in forma compatta sopra riportata, utilizzando la sostituzione e un po' di algebra si ottiene:
mentre la seconda espressione conduce a:
I numeri di Delannoy centrali soddisfano inoltre la seguente relazione di ricorrenza a tre termini:
e hanno la seguente funzione generatrice:
Il comportamento asintotico dominante dei numeri di Delannoy centrali è dato da:
dove
e .
Note
Voci correlate Numero di Motzkin Numero di Narayana
Altri progetti
Collegamenti esterni
Categoria:Successioni di interi