title: Numero di Delannoy
text: # 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$.
  
  