Nombre de Delannoy

Comme pour le triangle de Pascal, on peut aussi disposer les nombres de Delannoy en triangle. La ligne ${\displaystyle n}$ du triangle est constituée des nombres ${\displaystyle {\binom {n}{k}}_{D}=D(k,n-k)}$ pour ${\displaystyle 0\leqslant k\leqslant n}$, vérifiant ${\displaystyle {\binom {n}{k}}_{D}={\binom {n-1}{k-1}}_{D}+{\binom {n-1}{k}}_{D}+{\binom {n-2}{k-1}}_{D}}$pour ${\displaystyle 0<k<n}$ ; chaque terme est la somme de trois termes : les deux termes situés juste au dessus de lui et un troisième situé deux-lignes au dessus (par exemple 25=13+7+5, comme illustré en couleur dans la figure suivante).

            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

• Symétrie :

${\displaystyle D(n,m)=D(m,n)}$

• Formules par lignes du tableau :

${\displaystyle D(n,1)=2n+1}$

${\displaystyle D(n,2)=2n(n+1)+1=n^{2}+(n+1)^{2}}$ (nombres carrés centrés, suite A001844 de l'OEIS)

${\displaystyle D(n,3)={1 \over 3}(2n+1)(2n^{2}+2n+3)}$ (nombres octaédriques centrés, suite A001845 de l'OEIS)

${\displaystyle D(n,4)=(2n^{4}+4n^{3}+10n^{2}+8n+3)/3}$ (nombres 4-hyperoctaédriques centrés, suite A001846 de l'OEIS)

Pour ${\displaystyle m}$ fixé, ${\displaystyle D(n,m)}$ est un polynôme en ${\displaystyle n}$ de degré ${\displaystyle m}$ et de coefficient dominant ${\displaystyle 2^{m} \over m!}$.

• Formules closes :

${\displaystyle {\begin{aligned}D(n,m)&=\sum _{k=0}^{\min(n,m)}{\binom {n+m-k}{k,m-k,n-k}}=\sum _{k=0}^{\min(n,m)}{\binom {n}{k}}{\binom {n+m-k}{n}}\\&=\sum _{k=0}^{\min(n,m)}2^{k}{\binom {n}{k}}{\binom {m}{k}}\\&=\sum _{k=0}^{\infty }{\frac {1}{2^{k+1}}}{\binom {k}{n}}{\binom {k}{m}}\\&={}_{2}F_{1}(-n,-m;-(n+m);-1){\binom {n+m}{n}}\end{aligned}}}$

où ${\displaystyle {}_{2}F_{1}(a,b;c;d)}$ est une fonction hypergéométrique.

Justification de la première formule : la liste des pas successifs d'un chemin possédant ${\displaystyle k}$ pas diagonaux possède forcément ${\displaystyle n-k}$ pas horizontaux et ${\displaystyle m-k}$ pas verticaux. Le dénombrement de ces listes est donc donné par le coefficient multinomial ${\displaystyle {\binom {n+m-k}{k,m-k,n-k}}}$.

• Séries génératrices :

${\displaystyle \sum _{n,m\geqslant 0}D(n,m)x^{n}y^{m}={\frac {1}{1-x-y-xy}}}$[7]

${\displaystyle \sum _{n\geqslant 0}D(n,m)x^{n}={\frac {(1+x)^{m}}{(1-x)^{m+1}}}}$[6]

• Sommes de diagonales montantes du tableau (i.e., sommes des lignes du triangle) :

${\displaystyle \sum _{k=0}^{n}D(n-k,k)=\sum _{k=0}^{n}{\binom {n}{k}}_{D}=P_{n+1}}$ où ${\displaystyle (P_{n})}$ est la suite de Pell

Plus généralement les polynômes ${\displaystyle D_{n}(x)=\sum _{k=0}^{n}D(n-k,k)x^{k}=\sum _{k=0}^{n}{\binom {n}{k}}_{D}x^{k}}$ vérifient la relation de récurrence ${\displaystyle D_{n}(x)=(1+x)D_{n-1}(x)+xD_{n-2}(x)}$.

• Sommes de diagonales "super-montantes" du tableau (i.e., sommes des diagonales montantes du triangle) :

${\displaystyle \sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }D(n-2k,k)=\sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}_{D}=T_{n+1}}$ où ${\displaystyle (T_{n})}$ est la suite de Tribonacci (d'où le nom de triangle de Tribonacci donné au triangle de Delannoy dans[8]),

formule à mettre en parallèle avec celle concernant le triangle de Pascal : ${\displaystyle \sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F_{n}}$

• Les nombres de Delannoy sont reliés au nombre ${\displaystyle \ln 2}$ ; les valeurs de la ligne ${\displaystyle n}$ de leur tableau interviennent en effet dans la formule d'accélération de convergence suivante (voir  A001850) :

${\displaystyle \ln 2=\left(1-1/2+1/3-\cdots +{\frac {(-1)^{n+1}}{n}}\right)+(-1)^{n}\sum _{m=1}^{\infty }{\frac {(-1)^{m+1}}{mD(n,m-1)D(n,m)}}}$.

Pour ${\displaystyle n=1}$, on obtient par exemple :

${\displaystyle \ln 2=1+\sum _{m=1}^{\infty }{\frac {(-1)^{m}}{m(4m^{2}-1)}}}$

et pour ${\displaystyle n=3}$ :

${\displaystyle \ln 2=1-{1 \over 2}+{1 \over 3}-{\frac {1}{1\times 1\times 7}}+{\frac {1}{2\times 7\times 25}}-{\frac {1}{3\times 25\times 63}}+{\frac {1}{4\times 63\times 129}}-\cdots }$

• Relation de récurrence d'ordre 2 :

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

• Expression polynomiale :

${\displaystyle D(n)=P_{n}(3)}$

où ${\displaystyle P_{n}}$ est le polynôme de Legendre[9] d'ordre ${\displaystyle n}$.

• Série génératrice :

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

• Formule close :

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

• Évaluation asymptotique :

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

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

• Nombres de Schröder dénombrant les chemins de Delannoy de ${\displaystyle (0,0)}$ à ${\displaystyle (n,n)}$ sous-diagonaux, c'est-à-dire ne dépassant pas la diagonale sud-ouest - nord-est.
• Nombres de Schröder-Hipparque

• Nombres de Motzkin dénombrant les chemins reliant le point ${\displaystyle (0,0)}$ au point ${\displaystyle (n,0)}$, constitués de pas élémentaires nord-est (ajout de ${\displaystyle (1,1)}$), sud-est (ajout de ${\displaystyle (1,-1)}$) ou est (ajout de ${\displaystyle (1,0)}$) et restant au dessus de l'axe horizontal.
• Nombres de Narayana

(en) Eric W. Weisstein, « Delannoy Number », sur MathWorld