Nombre de Delannoy (original) (raw)

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, et notamment en combinatoire, les nombres de Delannoy dénombrent les chemins joignant deux points d'un réseau carré, en pas horizontaux, verticaux, et aussi diagonaux. Ils sont ainsi nommés en l'honneur de l'officier français, mathématicien amateur et aussi historien Henri Auguste Delannoy[1]. Ce dernier a présenté ce problème comme recherche de dénombrement de chemins parcourus par la reine dans un échiquier[2].

Les D(3)=63 chemins de Delannoy joignant (0,0) à (3,3).

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

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

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

Les D(2,2)=13 points entiers dans le carré d'équation | x | + | y | ⩽ 2 {\displaystyle |x|+|y|\leqslant 2} .

D ( n , m ) {\displaystyle D(n,m)} est le nombre de points du réseau Z m {\displaystyle \mathbb {Z} ^{m}} situés à une distance d'au plus n {\displaystyle n} pas de l'origine[3], autrement dit, le nombre de points à coordonnées entières de l'hyperoctaèdre plein { ( x 1 , x 2 , . . . , x m ) ∈ R m / | x 1 | + | x 2 | + . . . + | x m | ⩽ n } {\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 » D ( n , n ) {\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 :

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

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

D ( n , m ) = D ( n − 1 , m ) + D ( n − 1 , m − 1 ) + D ( n , m − 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 n {\displaystyle n} de proche en proche, connaissant la ligne n − 1 {\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] :

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

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

D ( n , m ) = ( 2 ∑ k = 0 m − 1 D ( n − 1 , k ) ) + D ( n − 1 , m ) {\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 n {\displaystyle n} connaissant la ligne n − 1 {\displaystyle n-1} .

Voir la suite A008288 de l'OEIS.

La diagonale du tableau donne les nombres de Delannoy centraux D ( n ) = D ( n , n ) {\displaystyle D(n)=D(n,n)} , dénombrant les chemins de ( 0 , 0 ) {\displaystyle (0,0)} à ( n , n ) {\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.

Comme pour le triangle de Pascal, on peut aussi disposer les nombres de Delannoy en triangle. La ligne n {\displaystyle n} du triangle est constituée des nombres ( n k ) D = D ( k , n − k ) {\displaystyle {\binom {n}{k}}_{D}=D(k,n-k)} pour 0 ⩽ k ⩽ n {\displaystyle 0\leqslant k\leqslant n} , vérifiant ( n k ) D = ( n − 1 k − 1 ) D + ( n − 1 k ) D + ( n − 2 k − 1 ) D {\displaystyle {\binom {n}{k}}_{D}={\binom {n-1}{k-1}}_{D}+{\binom {n-1}{k}}_{D}+{\binom {n-2}{k-1}}_{D}} pour 0 < k < n {\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 :

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

• Formules par lignes du tableau ou diagonales du triangle :

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

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

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

D ( n , 4 ) = ( 2 n 4 + 4 n 3 + 10 n 2 + 8 n + 3 ) / 3 {\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]

D ( n , 5 ) = 1 15 ( 2 n + 1 ) ( 2 n 4 + 4 n 3 + 18 n 2 + 16 n + 15 ) {\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]

D ( n , 6 ) = 1 45 ( 2 n 2 + 2 n + 5 ) ( 2 n 4 + 4 n 3 + 26 n 2 + 24 n + 9 ) {\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 m {\displaystyle m} fixé, D ( n , m ) {\displaystyle D(n,m)} est un polynôme en n {\displaystyle n} de degré m {\displaystyle m} et de coefficient dominant 2 m m ! {\displaystyle 2^{m} \over m!} .

• Formules closes :

D ( n , m ) = ∑ k = 0 min ( n , m ) ( n + m − k k , m − k , n − k ) = ∑ k = 0 min ( n , m ) ( n k ) ( n + m − k n ) = ∑ k = 0 min ( n , m ) 2 k ( n k ) ( m k ) = ∑ k = 0 ∞ 1 2 k + 1 ( k n ) ( k m ) = 2 F 1 ( − n , − m ; − ( n + m ) ; − 1 ) ( n + m n ) {\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ù 2 F 1 ( a , b ; c ; d ) {\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 k {\displaystyle k} pas diagonaux possède forcément n − k {\displaystyle n-k} pas horizontaux et m − k {\displaystyle m-k} pas verticaux. Le dénombrement de ces listes est donc donné par le coefficient multinomial ( n + m − k k , m − k , n − k ) {\displaystyle {\binom {n+m-k}{k,m-k,n-k}}} .

• Séries génératrices :

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

∑ n ⩾ 0 D ( n , m ) x n = ( 1 + x ) m ( 1 − x ) m + 1 {\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) :

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

Plus généralement les polynômes D n ( x ) = ∑ k = 0 n D ( n − k , k ) x k = ∑ k = 0 n ( n k ) D x k {\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 D n ( x ) = ( 1 + x ) D n − 1 ( x ) + x D n − 2 ( x ) {\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) :

∑ k = 0 ⌊ n 2 ⌋ D ( n − 2 k , k ) = ∑ k = 0 ⌊ n 2 ⌋ ( n − k k ) D = T n + 1 {\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ù ( T n ) {\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 : ∑ k = 0 ⌊ n 2 ⌋ ( n − k k ) = F n {\displaystyle \sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F_{n}}

ln ⁡ 2 = ( 1 − 1 / 2 + 1 / 3 − ⋯ + ( − 1 ) n + 1 n ) + ( − 1 ) n ∑ m = 1 ∞ ( − 1 ) m + 1 m D ( n , m − 1 ) D ( n , m ) {\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 n = 1 {\displaystyle n=1} , on obtient par exemple :

ln ⁡ 2 = 1 + ∑ m = 1 ∞ ( − 1 ) m m ( 4 m 2 − 1 ) {\displaystyle \ln 2=1+\sum _{m=1}^{\infty }{\frac {(-1)^{m}}{m(4m^{2}-1)}}}

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

ln ⁡ 2 = 1 − 1 2 + 1 3 − 1 1 × 1 × 7 + 1 2 × 7 × 25 − 1 3 × 25 × 63 + 1 4 × 63 × 129 − ⋯ {\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 :

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

• Expression polynomiale :

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

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

• Série génératrice :

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

• Formule close :

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

• Évaluation asymptotique :

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

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

• Nombres de Motzkin dénombrant les chemins reliant le point ( 0 , 0 ) {\displaystyle (0,0)} au point ( n , 0 ) {\displaystyle (n,0)} , constitués de pas élémentaires nord-est (ajout de ( 1 , 1 ) {\displaystyle (1,1)} ), sud-est (ajout de ( 1 , − 1 ) {\displaystyle (1,-1)} ) ou est (ajout de ( 1 , 0 ) {\displaystyle (1,0)} ) et restant au-dessus de l'axe horizontal.
• Nombres de Narayana
• Nombres hyperoctaédriques (non centrés), ayant même relation de récurrence que les nombres de Delannoy
• Triangle de Rascal (dont la formule de récurrence fait intervenir les mêmes termes que pour le triangle de Delannoy)

1. ↑ Banderier et Schwer 2005.
2. ↑ H. Delannoy, « Emploi de l’échiquier pour la résolution de certains problèmes de probabilités », Comptes-Rendus du Congrès annuel de l’Association Française pour l’Avancement des Sciences, 24, Bordeaux,‎ 1895, p. 76 (lire en ligne)
3. ↑ (en) Sebastian Luther, Stephan Mertens, « Counting lattice animals in high dimensions », Journal of Statistical Mechanics: Theory and Experiment,‎ 2011 (lire en ligne)
4. ↑ a b c et d (en) Elena Deza et Michel Marie Deza, Figurate Numbers, World Scientific, 2012 (lire en ligne), p. 229-231.
5. ↑ (en) Robert A. Sulanke, « Objects counted by the central Delannoy numbers », Journal of Integer Sequences, Vol. 6,‎ 2003 (lire en ligne)
6. ↑ a et b (en) Sebastian Luther, Stephan Mertens, « Counting lattice animals in high dimensions », Journal of Statistical Mechanics: Theory and Experiment,‎ 2011, p. 4 (lire en ligne)
7. ↑ Comtet 1970, p. 94.
8. ↑ (en) K. Alladi, V. E. Hoggatt Jr., « On tribonacci numbers and related functions », Fibonacci Quart. 15,‎ 1977, p. 42-45 (lire en ligne)
9. ↑ Moser 1955, Comtet 1974, p. 81, Vardi 1991.

• Cyril Banderier et Sylviane Schwer, « Why Delannoy numbers? », Journal of Statistical Planning and Inference, vol. 135, no 1,‎ 2005, p. 40-54 (lire en ligne).
• Louis Comtet, Analyse combinatoire, Paris, PUF, 1970, p. 93-94.
• Leo Moser, « King Paths on a Chessboard », Math. Gaz., vol. 39,‎ 1955, p. 54.
• Paul Peart et Wen-Jin Woan, « A bijective proof of the Delannoy recurrence », Congressus Numerantium, vol. 158,‎ 2002, p. 29–33 (ISSN 0384-9864, zbMATH 1030.05003)
• Fernando Rodriguez Villegas, Experimental number theory, vol. 13, Oxford University Press, coll. « Oxford Graduate Texts in Mathematics », 2007, 214 p. (ISBN 978-0-19-922730-3, zbMATH 1130.11002)
• Ilan Vardi, Computational Recreations in Mathematica, Addison-Wesley, 1991 (ISBN 978-0-685-47941-4)
• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Delannoy number » (voir la liste des auteurs).

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

• Portail des mathématiques