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:

m n	0	1	2	3	4	5	6	7	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	1 289	2 241	3 649
5	1	11	61	231	681	1 683	3 653	7 183	13 073
6	1	13	85	377	1 289	3 653	8 989	19 825	40 081
7	1	15	113	575	2 241	7 183	19 825	48 639	108 545
8	1	17	145	833	3 649	13 073	40 081	108 545	265 729
9	1	19	181	1 159	5 641	22 363	75 517	224 143	598 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:

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

Voci correlate

• Numero di Motzkin
• Numero di Narayana

Collegamenti esterni

• (EN) Eric W. Weisstein, Numero di Delannoy, su MathWorld, Wolfram Research.