Exercice 21

1. Un chemin N/E de $(0, 0)$ à $(a, b)$ fait $a$ pas $E$ et $b$ pas $N$, puisque chaque pas augmente de $1$ l'une des coordonnées ; réciproquement, tout mot formé de $a$ lettres $E$ et $b$ lettres $N$ code un tel chemin. Un tel mot est déterminé par l'ensemble des positions de ses lettres $E$, partie à $a$ éléments de $\llbracket 1\,,a + b \rrbracket$. $$\boxed{\binom{a + b}{a} \text{ chemins N/E de } (0, 0) \text{ à } (a, b)}$$

2. Pour $n \in \mathbb{N}$, on écrit les coefficients avec des factorielles : $$\frac{1}{2n + 1}\binom{2n + 1}{n} = \frac{(2n + 1)!}{(2n + 1)\,n!\,(n + 1)!} = \frac{(2n)!}{n!\,(n + 1)!} = \frac{1}{n + 1} \cdot \frac{(2n)!}{n!\,n!}.$$

3.(a) On étend la définition de $\rho_{i}$ à tout $i \in \mathbb{Z}$, les indices étant lus modulo $2n + 1$. Alors $\rho_{i}\big(\rho_{j}(w)\big) = \rho_{i+j}(w)$, puisque la lettre d'indice $k$ des deux mots est $w_{i+j+k}$, et $\rho_{i} = \rho_{j}$ si $i \equiv j \pmod{2n + 1}$. La classe de $w$ est $\{\rho_{i}(w) \mid i \in \llbracket 0\,,2n \rrbracket\}$ ; elle a $2n + 1$ éléments si et seulement si les mots $\rho_{i}(w)$, pour $i \in \llbracket 0\,,2n \rrbracket$, sont deux à deux distincts. Or $\rho_{i}(w) = \rho_{j}(w)$ entraîne $\rho_{j-i}(w) = w$ en appliquant $\rho_{-i}$.

Supposons qu'il existe $d \in \llbracket 1\,,2n \rrbracket$ tel que $\rho_{d}(w) = w$, et choisissons le plus petit. Écrivons la division euclidienne $2n + 1 = qd + r$, avec $0 \leqslant r < d$ (chapitre 12, théorème 1). Comme $\rho_{2n+1}(w) = w$ et $\rho_{qd}(w) = w$, on obtient $\rho_{r}(w) = w$, et la minimalité de $d$ impose $r = 0$ : $d$ divise $2n + 1$, et $q \geqslant 2$. La relation $w_{k+d} = w_{k}$ pour tout $k$ montre que $w$ est formé de $q$ copies du bloc $(w_{0}, \dots, w_{d-1})$. Si ce bloc contient $e$ lettres $E$ et $\nu$ lettres $N$, alors $n + 1 = qe$ et $n = q\nu$ : l'entier $q \geqslant 2$ divise $n + 1$ et $n$, donc leur différence $1$, ce qui est absurde. $$\boxed{\text{Chaque classe possède exactement } 2n + 1 \text{ éléments}}$$ C'est ici que sert le choix de $n + 1$ lettres $E$ et $n$ lettres $N$ : avec autant de lettres de chaque sorte, le mot $ENEN$ n'aurait que deux rotations distinctes.

3.(b) Pour $k \in \mathbb{N}$, on note $h(k)$ le nombre de lettres $E$ moins le nombre de lettres $N$ parmi les $k$ premières lettres du mot infini $W = www\cdots$ obtenu en répétant $w$ ; ainsi $h(0) = 0$, $h(k + 1) - h(k) = \pm 1$, et, comme $w$ a une lettre $E$ de plus que de lettres $N$, $h(k + 2n + 1) = h(k) + 1$. Le préfixe de longueur $k + 1$ du mot $\rho_{i}(w)$ est formé des lettres d'indices $i$ à $i + k$ de $W$, et son nombre de $E$ moins son nombre de $N$ vaut $h(i + k + 1) - h(i)$. Le mot $\rho_{i}(w)$ a donc la propriété demandée si et seulement si $$h(j) > h(i) \quad \text{pour tout } j \in \llbracket i + 1\,,i + 2n + 1 \rrbracket. \tag{$\ast$}$$

$\triangleright$ Existence. Soit $m$ le minimum de $h$ sur $\llbracket 0\,,2n \rrbracket$, et $i$ le plus grand indice de $\llbracket 0\,,2n \rrbracket$ où il est atteint. Pour $j \in \llbracket i + 1\,,2n \rrbracket$, on a $h(j) \geqslant m$ et $h(j) \neq m$, donc $h(j) > h(i)$. Pour $j \in \llbracket 2n + 1\,,i + 2n + 1 \rrbracket$, on a $h(j) = h(j - 2n - 1) + 1 \geqslant m + 1 > h(i)$. Ainsi $(\ast)$ est vérifiée, et $\rho_{i}(w)$ a la propriété.

$\triangleright$ Unicité. Soit $i < i'$ deux indices de $\llbracket 0\,,2n \rrbracket$ vérifiant $(\ast)$. Comme $i' \in \llbracket i + 1\,,i + 2n \rrbracket$, la propriété en $i$ donne $h(i') > h(i)$. Comme $i + 2n + 1 \in \llbracket i' + 1\,,i' + 2n + 1 \rrbracket$, la propriété en $i'$ donne $h(i + 2n + 1) > h(i')$, c'est-à-dire $h(i) + 1 > h(i')$. On aurait $h(i) < h(i') < h(i) + 1$ entre entiers, ce qui est impossible. Par la question (a), les $2n + 1$ rotations sont des mots distincts, et l'unicité de l'indice est celle du mot. $$\boxed{\text{Chaque classe contient un unique mot dont tous les préfixes ont strictement plus de } E \text{ que de } N}$$

La figure trace $h$ pour $n = 2$ et $w = NENEE$, sur deux périodes séparées par les pointillés. Le minimum $-1$ sur $\llbracket 0\,,4 \rrbracket$ est atteint en $1$ et en $3$ ; à partir du dernier, $i = 3$, la courbe reste strictement au-dessus de la droite en tirets sur toute la fenêtre ocre de longueur $5$. On lit le mot $\rho_{3}(w) = EENEN$, dont tous les préfixes ont plus de $E$ que de $N$. Partir de $i = 1$ échouerait, la courbe revenant à $-1$ en $k = 3$.

3.(c) Notons $\mathcal{G}$ l'ensemble des mots de $\mathcal{M}$ dont tous les préfixes ont strictement plus de $E$ que de $N$. Les classes d'équivalence forment une partition de $\mathcal{M}$ (chapitre 2, théorème 4), chacune a $2n + 1$ éléments, et $|\mathcal{M}| = \binom{2n + 1}{n}$ par la question 1 : il y a $\frac{1}{2n + 1}\binom{2n + 1}{n}$ classes (lemme des bergers), et autant de mots dans $\mathcal{G}$ par la question (b).

Un mot $w \in \mathcal{G}$ commence par $E$, puisque son préfixe de longueur $1$ doit contenir plus de $E$ que de $N$ ; on écrit $w = E\,v$, où $v$ a $n$ lettres $E$ et $n$ lettres $N$. Pour $k \in \llbracket 1\,,2n \rrbracket$, le préfixe de longueur $k + 1$ de $w$ a strictement plus de $E$ que de $N$ si et seulement si le préfixe de longueur $k$ de $v$ a au moins autant de $E$ que de $N$, c'est-à-dire si le chemin codé par $v$ est, après $k$ pas, en un point $(x, y)$ tel que $x \geqslant y$. L'application $w \mapsto v$ est donc une bijection de $\mathcal{G}$ sur l'ensemble des chemins N/E de $(0, 0)$ à $(n, n)$ qui restent dans $S$, de réciproque $v \mapsto Ev$. Avec la question 2 : $$\boxed{C_{n} = |\mathcal{G}| = \frac{1}{2n + 1}\binom{2n + 1}{n} = \frac{1}{n + 1}\binom{2n}{n}}$$ On trouve $C_{0}$, …, $C_{5}$ égaux à $1$, $1$, $2$, $5$, $14$, $42$, valeurs confirmées par énumération des chemins ; le lemme des rotations a lui aussi été vérifié classe par classe pour $n \leqslant 5$.

À retenir. L'argument des rotations est un lemme des bergers : on ne sait pas compter directement les bons chemins, mais on sait compter les classes, et chaque classe en contient exactement un. La division par $2n + 1$ est légitime parce que toutes les classes ont la même taille, ce que garantit la question (a) ; c'est l'étape que l'on oublie le plus souvent.