Chemin dans un réseau

En combinatoire, un chemin dans un réseau L dans le réseau entier ${\displaystyle \mathbb {Z} ^{d}}$ de dimension d de longueur k avec des pas dans l'ensemble S, est une suite finie de vecteurs ${\displaystyle (v_{0},v_{1},\dots ,v_{k})\in \mathbb {Z} ^{d}}$ telle que les différences successives ${\displaystyle v_{i}-v_{i-1}}$appartiennent à ${\displaystyle S}$. Plus généralement, un chemin dans un réseau peut être tracé dans n'importe quel réseau de ${\displaystyle \mathbb {R} ^{d}}$ (un sous-groupe de type fini qui contient une base) mais le réseau entier ${\displaystyle \mathbb {Z} ^{d}}$ est le plus couramment utilisé.

Voici un exemple de chemin dans le réseau ${\displaystyle \mathbb {Z} ^{2}}$ de longueur 5 dont les pas appartiennent à ${\displaystyle S=\lbrace (2,0),(1,1),(0,-1)\rbrace }$ :${\displaystyle L=\lbrace (-1,-2),(0,-1),(2,-1),(2,-2),(2,-3),(4,-3)\rbrace }$ (figure ci-contre).

Chemins nord-est dans un réseau

Un chemin nord-est (NE) est un chemin dans le réseau ${\displaystyle \mathbb {Z} ^{2}}$ avec des marches dans ${\displaystyle S=\lbrace (0,1),(1,0)\rbrace }$. Les pas correspondant à ${\displaystyle (0,1)}$ (c'est-à-dire les ${\displaystyle i}$ tels que ${\displaystyle v_{i}-v_{i-1}=(0,1)}$ sont appelés nord et notés ${\displaystyle N}$ ; les pas correspondant à ${\displaystyle (1,0)}$ sont appelés est et notés ${\displaystyle E}$.

Les chemins NE ont le plus souvent leur point de départ à l'origine. Cette convention permet de coder toutes les informations sur un chemin NE ${\displaystyle L}$ comme un simple mot de permutation. La longueur du mot est le nombre ${\displaystyle k}$ de pas du chemin. L'ordre des ${\displaystyle N}$ et des ${\displaystyle E}$ permet de reconstituer la suite ${\displaystyle L}$. De plus, le nombre de ${\displaystyle N}$ et le nombre de ${\displaystyle E}$ dans le mot déterminent le point final de ${\displaystyle L}$ .

Si le mot associé à un chemin NE contient ${\displaystyle n}$ pas ${\displaystyle N}$ et ${\displaystyle e}$ pas ${\displaystyle E}$ et si le chemin part de l'origine, alors il se termine nécessairement en ${\displaystyle (e,n)}$. Ce résultat intuitif se vérifie facilement par simple télescopage : ${\displaystyle v_{k}=(v_{k}-v_{k-1}) \cdots (v_{1}-v_{0}) v_{0}=\sum _{i=1}^{k}(v_{i}-v_{i-1})}$.

Compter les chemins dans un réseau

Les chemins dans un réseau sont souvent utilisés pour compter d’autres objets combinatoires. Inversement, il existe de nombreux objets combinatoires qui comptent le nombre de chemins dans un réseau d'un certain type. Cela se produit lorsque les chemins dans le réseau sont en bijection avec l'objet en question. Par exemple :

• le nombre de chemins NE de ${\displaystyle (0,0)}$ à ${\displaystyle (a,b)}$ est le nombre de combinaisons de ${\displaystyle a}$ objets dans un ensemble de ${\displaystyle a b}$ objets : c'est le coefficient binomial ${\displaystyle {\binom {a b}{a}}}$ (voir ci-dessous) ;
• les chemins de Dyck sont comptés par les nombres de Catalan ${\displaystyle C_{n}}$ (${\displaystyle n\in \mathbb {N} }$). Un chemin de Dyck est un chemin dans ${\displaystyle \mathbb {Z} ^{2}}$ de ${\displaystyle (0,0)}$ à ${\displaystyle (2n,0)}$ dont les pas appartiennent à ${\displaystyle S=\lbrace (1,1),(1,-1)\rbrace }$ et qui ne passe jamais sous l'axe des abscisses. De façon équivalente, un chemin de Dyck est un chemin NE de ${\displaystyle (0,0)}$ à ${\displaystyle (n,n)}$ qui reste au-dessus de la diagonale ${\displaystyle y=x}$ (et peut la toucher)^, ;
• les nombres de Schröder comptent les chemins dans ${\displaystyle \mathbb {Z} ^{2}}$ de ${\displaystyle (0,0)}$ à ${\displaystyle (n,n)}$ dont les pas appartiennent à ${\displaystyle S=\{(1,0),(0,1),(1,1)\}}$ et qui ne passent jamais au-dessus de la diagonale ${\displaystyle y=x}$.

Combinaisons et chemins NE

On détaille ici le premier exemple. Les chemins NE ont des liens étroits avec les nombres de combinaisons, qui sont comptées par les coefficients binomiaux et que l'ont peut arranger dans le triangle de Pascal. La figure ci-dessous illustre certains liens.

Le nombre de chemins NE de ${\displaystyle (0,0)}$ à ${\displaystyle (n,k)}$ est égal au coefficient binomial ${\displaystyle {\binom {n k}{n}}}$. La figure le montre pour ${\displaystyle 0\leq k\leq n=4}$. On peut le démontrer d'au moins deux façons raisonnables :

• directement, puisqu'il y a autant de chemins NE de ${\displaystyle (0,0)}$ à ${\displaystyle (n,k)}$ que de mots de longueur ${\displaystyle n k}$ avec ${\displaystyle n}$ occurrences de la lettre ${\displaystyle E}$ et qu'un tel mot est déterminé par les emplacements de ces lettres (les lettres situées aux autres emplacement sont nécessairement ${\displaystyle N}$), c'est-à-dire par une partie à ${\displaystyle n}$ éléments de ${\displaystyle \{1,\dots ,n\}}$ ;
• par récurrence sur l'indice ${\displaystyle n k}$ de l'anti-diagonale à laquelle appartient le point d'arrivée : c'est en effet clair si ${\displaystyle n k=0}$, c'est-à-dire si ${\displaystyle n=k=0}$; pour l'hérédité, on remarque qu'un chemin qui aboutit en ${\displaystyle (n,k)}$, le dernier pas est soit ${\displaystyle E}$ (il y a, par hypothèse de récurrence, ${\displaystyle {\binom {n-1 k}{n-1}}}$ chemins qui aboutissent en ${\displaystyle (n-1,k)}$), soit ${\displaystyle N}$ (il y a ${\displaystyle {\binom {n k-1}{n}}}$ chemins qui aboutissent en ${\displaystyle (n,k-1)}$) et on conclut par la relation de Pascal ${\displaystyle {\binom {n k}{n}}={\binom {n k-1}{n-1}} {\binom {n k-1}{n}}}$ ;
• on peut également utiliser le premier point et la partition des chemins selon que le dernier pas est ${\displaystyle E}$ ou ${\displaystyle N}$ pour démontrer la relation de Pascal...

On peut remarquer qu'en faisant tourner la figure de 135° dans le sens des aiguilles d'une montre autour de l'origine et que l'on l'étend pour inclure tous les ${\displaystyle n,k\in \mathbb {N} }$, on retrouve le triangle de Pascal.

Application à certaines démonstrations

Comme on l'a constaté ci-dessus, la représentation graphique des chemins NE se prête à de nombreuses preuves bijectives impliquant les combinaisons. Voici quelques exemples.

• ${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$ si ${\displaystyle 0\leq k\leq n}$. En effet, une symétrie par rapport à la diagonale ${\displaystyle y=x}$ échange les chemins NE de ${\displaystyle (0,0)}$ à ${\displaystyle (k,n-k)}$ et les chemins NE de ${\displaystyle (0,0)}$ à ${\displaystyle (n-k,k)}$.
• ${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.}$

Démonstration : Le membre de droite est égal au nombre de chemins NE de ${\displaystyle (0,0)}$ à ${\displaystyle (n,n)}$. Or chacun de ces chemins contient exactement un des points de coordonnées ${\displaystyle (k,n-k)}$ pour ${\displaystyle k\in \lbrace 0,1,\ldots ,n\rbrace }$ convenable (dans la figure ci-dessous, pour ${\displaystyle n=4}$, ce sont les points colorés).

Dans le membre de gauche, le terme ${\displaystyle {\binom {n}{k}}^{2}={\binom {n}{k}}{\binom {n}{n-k}}}$ compte les couples formés par un chemin NE de ${\displaystyle (0,0)}$ à ${\displaystyle (k,n-k)}$ et un chemin de ${\displaystyle (0,0)}$ à ${\displaystyle (n-k,k)}$ ou, ce qui revient au même, un chemin de ${\displaystyle (k,n-k)}$ à ${\displaystyle (n,n)}$.

Si l'on superpose les chemins du réseau NE au carré sur le même réseau rectangulaire, comme le montre la figure ci-dessous. Plus formellement, la partition des chemins selon le point ${\displaystyle (k,n-k)}$ qu'ils contiennent donne donc l'égalité à démontrer. ${\displaystyle \Box }$

Cette formule est un cas particulier de l'identité de Vandermonde.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lattice path » (voir la liste des auteurs).

Bibliographie

• Tadepalli Venkata Narayana, Lattice Path Combinatorics with Statistical Applications, Toronto, University of Toronto Press, 15 décembre 1979, 1^re éd. (ISBN 978-1487587284, lire en ligne)
• Chunwei Song (en), Lattice Path Combinatorics and Special Counting Sequences : From an Enumerative Perspective, Boca Raton, CRC Press, 2024 (ISBN 978-1032671758, DOI 10.1201/9781003509912, lire en ligne)
• Richard Stanley, Enumerative Combinatorics, vol. 1, Cambridge University Press, 2011, 2^e éd., 626 p. (ISBN 978-1-107-60262-5, DOI 10.1017/CBO9781139058520), p. 21
• Richard Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999, 585 p. (ISBN 978-0-521-78987-5, DOI 10.1017/CBO9780511609589), p. 173, 239 (avec un appendice par Sergei Fomin)

Articles connexes

• Lemme de Lindström-Gessel-Viennot
• Tadepalli Venkata Narayana
• Chemin auto-évitant

• Portail des mathématiques