Nombre de Delannoy

Summarize Timeline Top Qs Fact Check

Le nombre de Delannoy ${\displaystyle D(n,m)}$ est le nombre de chemins de ${\displaystyle \mathbb {N} ^{2}}$ joignant le point ${\displaystyle (0,0)}$ au point ${\displaystyle (n,m)}$ en utilisant des pas élémentaires de direction nord (ajout de ${\displaystyle (0,1)}$), nord-est (ajout de ${\displaystyle (1,1)}$), et est (ajout de ${\displaystyle (1,0)}$).

Notons que ${\displaystyle D(n,m)\geqslant {\binom {n+m}{n}}}$, le coefficient binomial ne comptant que les chemins prenant des directions est et nord.

${\displaystyle D(n,m)}$ est aussi le nombre de chemins de ${\displaystyle \mathbb {N} \times \mathbb {Z} }$ joignant le point ${\displaystyle (0,0)}$ au point ${\displaystyle (n+m,n-m)}$ en utilisant des pas élémentaires de direction nord-est (ajout de ${\displaystyle (1,1)}$), sud-est (ajout de ${\displaystyle (1,-1)}$), et des pas doubles de direction est (ajout de ${\displaystyle (2,0)}$).

${\displaystyle D(n,m)}$ est le nombre de points du réseau ${\displaystyle \mathbb {Z} ^{m}}$ situés à une distance d'au plus ${\displaystyle n}$ pas de l'origine^[3], autrement dit, le nombre de points à coordonnées entières de l'hyperoctaèdre plein ${\displaystyle \left\{(x_{1},x_{2},...,x_{m})\in \mathbb {R} ^{m}/|x_{1}|+|x_{2}|+...+|x_{m}|\leqslant n\right\}}$. On a donc ici un exemple de généralisation en dimensions supérieures du concept de nombre figuré (tel qu'étudié notamment par Pythagore et Pascal), les nombres de Delannoy correspondant en l'occurrence à des "nombres hyperoctaédriques centrés"^[4].

Tout comme les nombres de Catalan, de Motzkin, de Fibonacci, etc., les nombres de Delannoy apparaissent dans de nombreux problèmes. On trouvera notamment dans l'article de Sulanke^[5] 29 définitions combinatoires différentes des nombres de Delannoy « centraux » ${\displaystyle D(n,n)}$. Cette ubiquité s'explique en partie par des définitions récursives assez naturelles, et donc promptes à apparaître dans diverses situations.

Par la première définition, on obtient la définition récursive :

${\displaystyle D(0,m)=1}$ pour ${\displaystyle m\geqslant 0}$

${\displaystyle D(n,0)=1}$ pour ${\displaystyle n\geqslant 0}$

et, pour ${\displaystyle n,m\geqslant 1}$ :

${\displaystyle D(n,m)=D(n-1,m)+D(n-1,m-1)+D(n,m-1)}$, ce qui permet d'obtenir la ligne ${\displaystyle n}$ de proche en proche, connaissant la ligne ${\displaystyle n-1}$.

Par la deuxième définition, ou en conséquence de la précédente, on obtient la définition récursive^[6] :

${\displaystyle D(0,m)=1}$ pour ${\displaystyle m\geqslant 0}$

et, pour ${\displaystyle n,m\geqslant 1}$ :

${\displaystyle D(n,m)={\biggl (}2\sum _{k=0}^{m-1}D(n-1,k){\biggl )}+D(n-1,m)}$

ce qui permet d'obtenir la ligne ${\displaystyle n}$ connaissant la ligne ${\displaystyle n-1}$.

n\m	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	1289	2241	3649
5	1	11	61	231	681	1683	3653	7183	13073
6	1	13	85	377	1289	3653	8989	19825	40081
7	1	15	113	575	2241	7183	19825	48639	108545
8	1	17	145	833	3649	13073	40081	108545	265729
9	1	19	181	1159	5641	22363	75517	224143	598417

Voir la suite A008288 de l'OEIS.

La diagonale du tableau donne les nombres de Delannoy centraux ${\displaystyle D(n)=D(n,n)}$, dénombrant les chemins de ${\displaystyle (0,0)}$ à ${\displaystyle (n,n)}$ ; les premières valeurs en sont :

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ... ; voir la suite A001850 de l'OEIS.

Summarize Timeline Fact Check

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

Summarize Timeline Top Qs Fact Check

• Symétrie :

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

• Formules par lignes du tableau ou diagonales du triangle :

${\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)^[4]

${\displaystyle D(n,5)={\frac {1}{15}}(2n+1)(2n^{4}+4n^{3}+18n^{2}+16n+15)}$ (nombres 5-hyperoctaédriques centrés, suite A001847 de l'OEIS)^[4]

${\displaystyle D(n,6)={\frac {1}{45}}(2n^{2}+2n+5)(2n^{4}+4n^{3}+26n^{2}+24n+9)}$ (nombres 6-hyperoctaédriques centrés, suite A001848 de l'OEIS)^[4]

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 }$

Summarize Timeline Fact Check

• 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}$.