Numero di Delannoy

In matematica, data una griglia rettangolare nel 1° quadrante di un sistema di riferimento cartesiano, il numero di Delannoy, ${\displaystyle 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, ${\displaystyle D(m,n)}$, che prende il nome dal matematico e ufficiale dell'esercito francese Henri Delannoy,^[1] rappresenta anche il numero di allineamenti globali di due sequenze di lunghezza ${\displaystyle m}$ e ${\displaystyle n}$,^[2] il numero di punti in un reticolo intero m-dimensionale che sono al massimo a n passi di distanza dall'origine,^[3] e, in un automa cellulare, il numero di celle in un intorno di von Neumann m-dimensionale di raggio n.^[4]

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 ${\displaystyle 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:^[5]

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

Calcolo

Numeri di Delannoy

Per raggiungere il punto di coordinate ${\displaystyle (m,n)}$, per ${\displaystyle k}$ passi diagonali ci devono essere ${\displaystyle m-k}$ passi in direzione ${\displaystyle x}$ e ${\displaystyle n-k}$ passi in direzione ${\displaystyle y}$; poiché tali passi possono essere compiuti in qualunque ordine, il numero dei cammini possibili è per raggiungere il suddetto punto è data dal coefficiente multinomiale ${\displaystyle {\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:

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

Un'espressione alternativa è data dalla da:

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

o dalla serie infinita:

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

E anche da:

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

dove ${\displaystyle A(m,k)}$ è data dalla successione "A266213".^[8]

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

${\displaystyle 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:

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

Numeri di Delannoy centrali

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

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

mentre la seconda espressione conduce a:

${\displaystyle 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:^[9]

${\displaystyle nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),}$

e hanno la seguente funzione generatrice:

${\displaystyle \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:

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

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

Note

1. Cyril Banderier e Sylviane Schwer, Why Delannoy numbers?, in Journal of Statistical Planning and Inference, vol. 135, n. 1, 2005, pp. 40-54, DOI:10.1016/j.jspi.2005.02.004, arXiv:math/0411128.
2. Michael A. Covington, The number of distinct alignments of two strings, in Journal of Quantitative Linguistics, vol. 11, n. 3, 2004, pp. 173-182, DOI:10.1080/0929617042000314921.
3. Sebastian Luther e Stephan Mertens, Counting lattice animals in high dimensions, in Journal of Statistical Mechanics: Theory and Experiment, vol. 2011, n. 9, 2011, pp. P09026, Bibcode:2011JSMTE..09..026L, DOI:10.1088/1742-5468/2011/09/P09026, arXiv:1106.1078.
4. R. Breukelaar e Th. Bäck, Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior, in Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05), ACM, 2005, pp. 107-114, DOI:10.1145/1068009.1068024, ISBN 1-59593-010-8.
5. Robert A. Sulanke, Objects counted by the central Delannoy numbers (PDF), in Journal of Integer Sequences, vol. 6, n. 1, 2003, pp. Article 03.1.5. URL consultato il 3 maggio 2021 (archiviato dall'url originale il 4 marzo 2016).
6. (EN) N. J. A. Sloane, Sequenza A008288, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation. URL consultato il 3 maggio 2021.
7. (EN) N. J. A. Sloane, Sequenza A001850, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation. URL consultato il 3 maggio 2021.
8. (EN) Dmitry Zaitsev, Sequenza A266213, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation. URL consultato il 3 maggio 2021.
9. Paul Peart e Wen-Jin Woan, A bijective proof of the Delannoy recurrence, in Congressus Numerantium, vol. 158, 2002, pp. 29-33, ISSN 0384-9864 (WC · ACNP).

Voci correlate

• Numero di Motzkin
• Numero di Narayana

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Numero di Delannoy

Collegamenti esterni

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica