Numero di Delannoy
# Numero di Delannoy

In matematica, data una griglia rettangolare nel 1° quadrante di un sistema di riferimento cartesiano, il numero di Delannoy, $D(m,n)$, 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, $D(m,n)$, 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 $m$ e $n$, 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 $y=x$ 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:

    mn  0 1 2 3 4 5 6 7 8 0 111111111 1 1357911131517 2 151325416185113145 3 172563129231377575833 4 19411293216811 2892 2413 649 5 111612316811 6833 6537 18313 073 6 113853771 2893 6538 98919 82540 081 7 1151135752 2417 18319 82548 639108 545 8 1171458333 64913 07340 081108 545265 729 9 1191811 1595 64122 36375 517224 143598 417

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:

## 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, 1 683, 8 989, 48 639, 265 729, ...

## Calcolo

### Numeri di Delannoy

Per raggiungere il punto di coordinate $(m,n)$, per $k$ passi diagonali ci devono essere $m-k$ passi in direzione $x$ e $n-k$ passi in direzione $y$; poiché tali passi possono essere compiuti in qualunque ordine, il numero dei cammini possibili è per raggiungere il suddetto punto è data dal coefficiente multinomiale ${\binom {m+n-k}{k,m-k,n-k}}={\binom {m+n-k}{m}}{\binom {m}{k}}$. Quindi, sia ha la seguente espressione in forma compatta:

    $D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m+n-k}{m}}{\binom {m}{k}}.$

Un'espressione alternativa è data dalla da:

    $D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}$

o dalla serie infinita:

    $D(m,n)=\sum _{k=0}^{\infty }{\frac {1}{2^{k+1}}}{\binom {k}{n}}{\binom {k}{m}}.$

E anche da:

    $D(m,n)=\sum _{k=0}^{n}A(m,k),$

dove $A(m,k)$ è data dalla successione "A266213".

Si vede che la relazione di ricorrenza fondamentale per i numeri di Delannoy è:

    $D(m,n)={\begin{cases}1&{\text{Se }}m=0{\text{ o }}n=0\\D(m-1,n)+D(m-1,n-1)+D(m,n-1)&{\text{altrimenti}}\end{cases}}$

Tale relazione di ricorrenza conduce direttamente alla funzione generatrice:

    $\sum _{m,n=0}^{\infty }D(m,n)x^{m}y^{n}=(1-x-y-xy)^{-1}.$

### Numeri di Delannoy centrali

Sostituendo $m=n$ nella prima espressione in forma compatta sopra riportata, utilizzando la sostituzione $k\leftrightarrow n-k$ e un po' di algebra si ottiene:

    $D(n)=\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n+k}{k}},$

mentre la seconda espressione conduce a:

    $D(n)=\sum _{k=0}^{n}{\binom {n}{k}}^{2}2^{k}.$

I numeri di Delannoy centrali soddisfano inoltre la seguente relazione di ricorrenza a tre termini:

    $nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),$

e hanno la seguente funzione generatrice:

    $\sum _{n=0}^{\infty }D(n)x^{n}=(1-6x+x^{2})^{-1/2}.$

Il comportamento asintotico dominante dei numeri di Delannoy centrali è dato da:

    $D(n)={\frac {c\,\alpha ^{n}}{\sqrt {n}}}\,(1+O(n^{-1}))$

dove $\alpha =3+2{\sqrt {2}}\approx 5,828$ e $c=(4\pi (3{\sqrt {2}}-4))^{-1/2}\approx 0,5727$.

