Delannoy Henri Auguste

Imaginez une grille et un pion placé dans son coin inférieur gauche. Pour atteindre le coin supérieur droit, le pion peut avancer horizontalement, verticalement ou en diagonale, sans revenir en arrière. Les nombres de Delannoy répondent à une question de comptage : combien de trajets différents respectent ces règles ?

Sur une petite grille, on peut encore dessiner les trajets. Sur une grande grille, une règle de récurrence les dénombre sans les énumérer un par un. Cette idée relie une promenade visible à un problème général de combinatoire.

Le nombre de Delannoy D_m,n est le nombre de chemins monotones reliant deux sommets séparés par m pas horizontaux et n pas verticaux sur une grille. « Monotone » signifie que chaque déplacement avance dans l'une des deux directions choisies, sans retour en arrière. Trois mouvements sont autorisés : un pas horizontal, un pas vertical ou un pas diagonal qui avance simultanément dans les deux directions.

Les indices m et n désignent donc les écarts horizontaux et verticaux entre le départ et l'arrivée. Le comptage commence avec D_0,n = 1 et D_m,0 = 1 : lorsqu'un seul type de pas reste possible, il n'existe qu'un chemin. Pour m et n positifs, le dernier mouvement est horizontal, vertical ou diagonal ; ces trois possibilités donnent la relation

Elle s'applique lorsque m et n sont des entiers naturels, avec les valeurs de bord précédentes. La définition compte des chemins sur une grille ; elle ne décrit ni la longueur géométrique minimale d'un trajet, ni une probabilité de déplacement.

Considérons un départ et une arrivée séparés par deux pas horizontaux et deux pas verticaux. On cherche le nombre de chemins monotones possibles, en autorisant les trois mouvements de la définition.

Données : m = 2 ; n = 2 ; D_0,n = 1 ; D_m,0 = 1.

On calcule d'abord D_1,1 = 1 + 1 + 1 = 3.
On obtient ensuite D_1,2 = 1 + 3 + 1 = 5.
Par symétrie des écarts, D_2,1 = 3 + 1 + 1 = 5.
Enfin, D_2,2 = 5 + 5 + 3 = 13.

Le résultat est donc D_2,2 = 13 chemins. Un contrôle indépendant consiste à classer ces chemins selon leur dernier mouvement : les 5 qui arrivent par l'horizontale, les 5 qui arrivent par la verticale et les 3 qui arrivent en diagonale totalisent bien 13.

En combinatoire, les nombres de Delannoy servent à compter des configurations construites par deux progressions coordonnées. Le geste consiste à repérer les deux écarts, puis à décomposer les chemins selon leur dernier mouvement.

Sur un échiquier, un problème de déplacement peut conduire à ce modèle lorsque les mouvements autorisés correspondent à un pas horizontal, vertical ou diagonal et que les retours en arrière sont exclus. Si les pièces ou les obstacles changent ces règles, un autre comptage est nécessaire.

Pour une grille assez petite, le dessin des chemins permet de vérifier le résultat. Pour une grille plus grande, la récurrence est préférable, car elle évite de lister chaque trajet.

Le nombre de Delannoy ne se confond pas avec le nombre de chemins monotones qui n'autorisent que les pas horizontaux et verticaux. Dans ce second comptage, les diagonales sont interdites ; pour le déplacement de deux pas dans chaque direction, le total est différent de 13. Le critère qui tranche est donc la liste exacte des mouvements autorisés.

Il ne faut pas non plus confondre le nombre de chemins avec la distance minimale entre les deux sommets. Une diagonale réduit le nombre de mouvements d'un trajet, mais le nombre de Delannoy compte tous les trajets admissibles, quelle que soit leur longueur en mouvements.

Le cas m = 0 ou n = 0 est une frontière importante. Un seul axe reste disponible, donc D_0,n = D_m,0 = 1. Appliquer la récurrence avec des indices négatifs sortirait du modèle ; il faut utiliser ces valeurs de bord.

Le mot « diagonal » suppose ici un déplacement d'un pas dans chaque direction à la fois. Une diagonale de deux cases, un déplacement oblique de longueur variable ou un saut d'échiquier ne relève pas automatiquement du même dénombrement. Le symptôme est un résultat qui ne se décompose plus en trois catégories selon le dernier mouvement ; il faut alors redéfinir les mouvements avant de compter.

Enfin, la grille doit être considérée comme sans obstacle et les déplacements doivent rester monotones. Un obstacle, un mouvement autorisant un retour ou une case de départ différente modifie les conditions et peut exiger une nouvelle relation de récurrence.

Le calcul de D_m,n illustre une méthode générale de dénombrement par récurrence : on rattache une configuration à la dernière décision qui la construit, puis on additionne les cas disjoints. En variant les mouvements autorisés ou les obstacles, on obtient d'autres problèmes de chemins sur grille, avec des récurrences adaptées.

La biographie de Delannoy rappelle aussi que la combinatoire peut naître de questions récréatives : carrés magiques, déplacements sur l'échiquier et probabilités de scrutins forment des contextes différents, mais chacun transforme une situation en objets dénombrables ou en événements mesurables.