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.. Ce dernier a présenté ce problème comme recherche de dénombrement de chemins parcourus par la reine dans un échiquier.
Définitions et valeurs particulières
Première définition combinatoire Le nombre de Delannoy est le nombre de chemins de joignant le point au point en utilisant des pas élémentaires de direction nord (ajout de ), nord-est (ajout de ), et est (ajout de ).
Notons que , le coefficient binomial ne comptant que les chemins prenant des directions est et nord.
est aussi le nombre de chemins de joignant le point au point en utilisant des pas élémentaires de direction nord-est (ajout de ), sud-est (ajout de ), et des pas doubles de direction est (ajout de ).
vignette|188x188px|Les D(2,2)=13 points entiers dans le carré d'équation .|alt=
Deuxième définition combinatoire est le nombre de points du réseau situés à une distance d'au plus pas de l'origine, autrement dit, le nombre de points à coordonnées entières de l'hyperoctaèdre plein . 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"..
Définitions combinatoires des nombres de Delannoy « centraux » 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 29 définitions combinatoires différentes des nombres de Delannoy « centraux » . Cette ubiquité s'explique en partie par des définitions récursives assez naturelles, et donc promptes à apparaître dans diverses situations.
Définition récursive 1 Par la première définition, on obtient la définition récursive : pour pour
et, pour :
, ce qui permet d'obtenir la ligne de proche en proche, connaissant la ligne .
Définition récursive 2 Par la deuxième définition, ou en conséquence de la précédente, on obtient la définition récursive :
pour
pour
et, pour :
ce qui permet d'obtenir la ligne connaissant la ligne .
Premières valeurs
{| class="wikitable" |- ! 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 . La diagonale du tableau donne les nombres de Delannoy centraux , dénombrant les chemins de à ; les premières valeurs en sont : 1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ... ; voir la .
Triangle de Delannoy Comme pour le triangle de Pascal, on peut aussi disposer les nombres de Delannoy en triangle. La ligne du triangle est constituée des nombres pour , vérifiant pour ; 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
Propriétés du triangle de Delannoy
Symétrie :
Formules par lignes du tableau ou diagonales du triangle :
(nombres carrés centrés, )
(nombres octaédriques centrés, )
(nombres 4-hyperoctaédriques centrés, )
(nombres 5-hyperoctaédriques centrés, )
(nombres 6-hyperoctaédriques centrés, )
Pour fixé, est un polynôme en de degré et de coefficient dominant .
Formules closes :
où est une fonction hypergéométrique.
Justification de la première formule : la liste des pas successifs d'un chemin possédant pas diagonaux possède forcément pas horizontaux et pas verticaux. Le dénombrement de ces listes est donc donné par le coefficient multinomial .
Séries génératrices :
.
Sommes de diagonales montantes du tableau (i.e., sommes des lignes du triangle) :
où est la suite de Pell
Plus généralement les polynômes vérifient la relation de récurrence .
Sommes de diagonales "super-montantes" du tableau (i.e., sommes des diagonales montantes du triangle) :
où est la suite de Tribonacci (d'où le nom de triangle de Tribonacci donné au triangle de Delannoy dans),
formule à mettre en parallèle avec celle concernant le triangle de Pascal :
Les nombres de Delannoy sont reliés au nombre ; les valeurs de la ligne de leur tableau interviennent en effet dans la formule d'accélération de convergence suivante (voir ) :
. Pour , on obtient par exemple :
et pour :
Propriétés des nombres de Delannoy centraux
Relation de récurrence d'ordre 2 :
.
Expression polynomiale :
où est le polynôme de Legendre. d'ordre .
Série génératrice :
Formule close :
Évaluation asymptotique :
où et .
Pages connexes
Nombres de Schröder dénombrant les chemins de Delannoy de à 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 au point , constitués de pas élémentaires nord-est (ajout de ), sud-est (ajout de ) ou est (ajout de ) 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)
Notes et références Notes
Références
.
. .
Lien externe
Delannoy Catégorie:Combinatoire Catégorie:Coefficient binomial