Chemin dans un réseau

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

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

Chemins nord-est dans un réseau

Un chemin nord-est (NE) est un chemin dans le réseau $ℤ^{2}$ avec des marches dans $S = {(0, 1), (1, 0)}$ . Les pas correspondant à $(0, 1)$ (c'est-à-dire les $i$ tels que $v_{i} - v_{i - 1} = (0, 1)$ sont appelés nord et notés $N$ ; les pas correspondant à $(1, 0)$ sont appelés est et notés $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 $L$ comme un simple mot de permutation. La longueur du mot est le nombre $k$ de pas du chemin. L'ordre des $N$ et des $E$ permet de reconstituer la suite $L$ . De plus, le nombre de $N$ et le nombre de $E$ dans le mot déterminent le point final de $L$ .

Si le mot associé à un chemin NE contient $n$ pas $N$ et $e$ pas $E$ et si le chemin part de l'origine, alors il se termine nécessairement en $(e, n)$ . Ce résultat intuitif se vérifie facilement par simple télescopage : $v_{k} = (v_{k} - v_{k - 1}) + \dots + (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 $(0, 0)$ à $(a, b)$ est le nombre de combinaisons de $a$ objets dans un ensemble de $a + b$ objets : c'est le coefficient binomial $(\binom{a + b}{a})$ (voir ci-dessous) ;
les chemins de Dyck sont comptés par les nombres de Catalan $C_{n}$ ( $n \in ℕ$ ). Un chemin de Dyck est un chemin dans $ℤ^{2}$ de $(0, 0)$ à $(2 n, 0)$ dont les pas appartiennent à $S = {(1, 1), (1, - 1)}$ et qui ne passe jamais sous l'axe des abscissesModèle:Sfnp. De façon équivalente, un chemin de Dyck est un chemin NE de $(0, 0)$ à $(n, n)$ qui reste au-dessus de la diagonale $y = x$ (et peut la toucher)Modèle:Sfnp Modèle:,^[1] ;
les nombres de Schröder comptent les chemins dans $ℤ^{2}$ de $(0, 0)$ à $(n, n)$ dont les pas appartiennent à $S = {(1, 0), (0, 1), (1, 1)}$ et qui ne passent jamais au-dessus de la diagonale $y = x$ Modèle:Sfnp.

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 $(0, 0)$ à $(n, k)$ est égal au coefficient binomial $(\binom{n + k}{n})$ . La figure le montre pour $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 $(0, 0)$ à $(n, k)$ que de mots de longueur $n + k$ avec $n$ occurrences de la lettre $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 $N$ ), c'est-à-dire par une partie à $n$ éléments de ${1, \dots, n}$ ;
par récurrence sur l'indice $n + k$ de l'anti-diagonale à laquelle appartient le point d'arrivée : c'est en effet clair si $n + k = 0$ , c'est-à-dire si $n = k = 0$ ; pour l'hérédité, on remarque qu'un chemin qui aboutit en $(n, k)$ , le dernier pas est soit $E$ (il y a, par hypothèse de récurrence, $(\binom{n - 1 + k}{n - 1})$ chemins qui aboutissent en $(n - 1, k)$ ), soit $N$ (il y a $(\binom{n + k - 1}{n})$ chemins qui aboutissent en $(n, k - 1)$ ) et on conclut par la relation de Pascal $(\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 $E$ ou $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

n, k \in ℕ

, 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.

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

Démonstration : Le membre de droite est égal au nombre de chemins NE de

(0, 0)

à

(n, n)

. Or chacun de ces chemins contient exactement un des points de coordonnées

(k, n - k)

pour

k \in {0, 1, \dots, n}

convenable (dans la figure ci-dessous, pour

n = 4

, ce sont les points colorés).

Dans le membre de gauche, le terme

{(\binom{n}{k})}^{2} = (\binom{n}{k}) (\binom{n}{n - k})

compte les couples formés par un chemin NE de

(0, 0)

à

(k, n - k)

et un chemin de

(0, 0)

à

(n - k, k)

ou, ce qui revient au même, un chemin de

(k, n - k)

à

(n, n)

.

Ensembles de chemins de réseau NE au carré, avec le deuxième terme du couple symétrisé.

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

(k, n - k)

qu'ils contiennent donne donc l'égalité à démontrer.

◻

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

Notes et références

Modèle:Traduction/Référence Modèle:Références

Bibliographie

Modèle:Ouvrage
Modèle:Ouvrage
Modèle:Ouvrage
Modèle:Ouvrage (avec un appendice par Sergei Fomin)

Articles connexes

Modèle:Portail

↑ Modèle:MathWorld.

[Wolfram_Dyck-1] Modèle:MathWorld.

[1]

Chemin dans un réseau

Sommaire

Chemins nord-est dans un réseau

Compter les chemins dans un réseau