Nombre de Delannoy

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, et notamment en combinatoire, un nombre de Delannoy est le nombre des chemins joignant deux points d'une grille que ce soit en pas horizontaux, diagonaux ou verticaux. Ces nombres sont nommés d'après Henri Auguste Delannoy, un officier français, mathématicien amateur et aussi historien[1].

Les 63 chemins de Delannoy D(3), dans une grille 3 × 3.

Définition et exemple[modifier | modifier le code]

Le nombre de Delannoy D(m,n) est, dans une grille, le nombre de chemins allant du point (0,0) au point (m,n) en utilisant des pas unité de direction nord, nord-est et est. On a :

D(0,n)=D(m,0)=1

et, pour m,n>0 :

D(m,n)=D(m-1,n) + D(m-1,n-1) + D(m,n-1).

Voici une table des premiers nombres de Delannoy :

1  1  1   1   1    1    1    1     1 ...
1  3  5   7   9   11   13   15    17 ...
1  5 13  25  41   61   85  113   145 ...
1  7 25  63 129  231  377  575   833 ...
1  9 41 129 321  681 1289 2241  3649 ...
1 11 61 231 681 1683 3653 7183 13073 ... 

On voit que :

D(n,m)=D(m,n).

La diagonale de ce tableau donne les nombres de Delannoy centraux D(n)=D(n,n), qui sont les nombres pour la grille n\times n. Les premiers nombres de Delannoy centraux sont :

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ...

Ils constituent la suite A001850 de l'OEIS.

Propriétés[modifier | modifier le code]

Les nombres de Delannoy admettent les expressions closes :

\begin{align}D(m,n)&=\sum_{k=0}^n\binom n k \binom{m+n-k} n\\
&=\sum_{k=0}^n2^n\binom n k \binom m k\\
&=\binom {m+n} n {}_2F_1(-m,-n;-(m+n);-1).
\end{align}

La fonction {}_2F_1(a,b;c;d) est une fonction hypergéométrique. Leur série génératrice est[2] :

\sum D(m,n)x^my^n=\frac1{1-x-y-xy}

Les nombres de Delannoy ont une connexion étroite avec la constante \log(2). Les entrées de la ne ligne interviennent dans la formule d'accélération (A001850):

\log(2)=\Big(1-1/2+1/3-\cdots+\frac{(-1)^{n+1}}n\Big)+\sum_{n=1}^\infty(-1)^{n+1}\frac1{k\cdot D(m,n-1)\cdot D(m,n)}.

Par exemple, pour m=3, la table donne la série :

\log(2)=1-1/2+1/3- - 1/(1\cdot1\cdot7) + 1/(2\cdot7\cdot25) - 1/(3\cdot25\cdot63) + 1/(4\cdot63\cdot129) - \cdots.

Propriétés des nombres centraux[modifier | modifier le code]

Les nombres de Delannoy centraux vérifient la relation de récurrence ternaire :

 n D(n) = 3(2n-1)D(n-1) - (n-1)D(n-2).

Ils s'expriment également sous la forme :

D(n)=P_n(3)

P_n(x) est un polynôme de Legendre[3].

Leur série génératrice est :

 \sum D(n) x^n = (1-6x+x^2)^{-1/2}

et les nombres possèdent l'expression close :

 D(n) = \sum_{k=0}^n \binom{n}{k} \binom{n+k}{k}.

Le chemins qui sont sous-diagonaux, c'est-à-dire ne dépassent pas la diagonale sud-ouest — nord-est sont comptés par les nombres de Schröder.

Pages connexes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

(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).

Références[modifier | modifier le code]

  • Cyril Banderier et Sylviane Schwer, « Why Delannoy numbers? », Journal of Statistical Planning and Inference, vol. 135, no 1,‎ , p. 40-54 (arXiv math/0411128).
  • Louis Comtet, Advanced Combinatorics : The Art of Finite and Infinite Expansions, Dordrecht, Redei,‎ .
  • L Moser, « King Paths on a Chessboard », Math. Gaz., vol. 39,‎ , p. 54.
  • Paul Peart et Wen-Jin Woan, « A bijective proof of the Delannoy recurrence », Congressus Numerantium, vol. 158,‎ , p. 29–33 (ISSN 0384-9864, zbMATH 1030.05003)
  • Fernando Rodriguez Villegas, Experimental number theory, vol. 13, Oxford University Press,‎ (ISBN 978-0-19-922730-3, zbMATH 1130.11002)
  • I Vardi, Computational Recreations in Mathematica, Addison-Wesley,‎ (ISBN 978-0685479414)

Lien externe[modifier | modifier le code]

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