Exercice 62

Idée. On raisonne par récurrence sur $n$. On découpe $\mathfrak{S}_{n}$ en $n$ blocs selon la position de la valeur $n$ ; chaque bloc est une copie de $\mathfrak{S}_{n - 1}$, que l'on parcourt grâce à l'hypothèse de récurrence, et l'on passe d'un bloc à un autre en échangeant la valeur $n$ avec une autre valeur.

La réponse est oui, pour tout $n \geqslant 2$. Rappelons que multiplier $\sigma$ à gauche par $\tau = (a\ b)$ échange les valeurs $a$ et $b$ dans la suite $\sigma(1)$, …, $\sigma(n)$. Appelons chaîne de $\mathfrak{S}_{n}$ une suite $(\sigma_{0}, \dots, \sigma_{n! - 1})$ contenant chaque élément de $\mathfrak{S}_{n}$ exactement une fois, avec $\sigma_{0} = \mathrm{id}$ et, pour tout $k \geqslant 1$, $\sigma_{k} = \tau_{k}\sigma_{k - 1}$ pour une transposition $\tau_{k}$. Il s'agit de montrer qu'il existe une chaîne.

Initialisation. Pour $n = 2$, la suite $\big(\mathrm{id}, (1\ 2)\big)$ est une chaîne.

Hérédité. Soit $n \geqslant 3$, et $(\rho_{0}, \dots, \rho_{N})$, avec $N = (n - 1)! - 1$, une chaîne de $\mathfrak{S}_{n - 1}$ ; on voit chaque $\rho_{k}$ comme un élément de $\mathfrak{S}_{n}$ qui fixe $n$, et l'on écrit $\rho_{k} = \tau_{k}\rho_{k - 1}$, où chaque $\tau_{k}$ fixe $n$.

• Les blocs. Pour $p \in [\![1\,;n]\!]$, soit $\mathcal{B}_{p}$ l'ensemble des $\sigma \in \mathfrak{S}_{n}$ telles que $\sigma(p) = n$. Si $g \in \mathcal{B}_{p}$, l'application $\rho \mapsto \rho g$ est une bijection de $\mathfrak{S}_{n - 1}$ sur $\mathcal{B}_{p}$ : on a bien $\rho g(p) = \rho(n) = n$, et la réciproque est $\sigma \mapsto \sigma g^{-1}$, qui envoie $\mathcal{B}_{p}$ dans les permutations fixant $n$. La suite $(\rho_{0}g, \dots, \rho_{N}g)$ parcourt donc $\mathcal{B}_{p}$ exactement une fois, à partir de $g$, et $\rho_{k}g = \tau_{k}(\rho_{k - 1}g)$ : on passe toujours d'un terme au suivant par une transposition.

• Le passage d'un bloc à l'autre. Si $e \in \mathcal{B}_{p}$ et $q \neq p$, soit $x = e(q) \neq n$. Alors $(x\ n)e$ envoie $q$ sur $n$ : elle appartient à $\mathcal{B}_{q}$.

On parcourt successivement les blocs $\mathcal{B}_{n}$, $\mathcal{B}_{n - 1}$, …, $\mathcal{B}_{1}$. On commence par $\mathcal{B}_{n}$ avec $g_{n} = \mathrm{id}$, ce qui fournit les permutations $\rho_{0}$, …, $\rho_{N}$. Si le parcours de $\mathcal{B}_{p}$ s'est achevé en $e_{p} = \rho_{N}g_{p}$, on passe à $g_{p - 1} = \big(e_{p}(p - 1)\ \ n\big)e_{p} \in \mathcal{B}_{p - 1}$, puis on parcourt $\mathcal{B}_{p - 1}$ à partir de $g_{p - 1}$. Les blocs étant disjoints et de réunion $\mathfrak{S}_{n}$, on obtient $n \times (n - 1)! = n!$ permutations distinctes : c'est une chaîne de $\mathfrak{S}_{n}$. $$\boxed{\text{oui, pour tout } n \geqslant 2 : \text{ une telle suite } (\tau_{1}, \dots, \tau_{n! - 1}) \text{ existe}}$$ Pour $n = 3$, la construction donne $\mathrm{id}$, $(1\ 2)$ dans $\mathcal{B}_{3}$, puis $(1\ 2\ 3)$, $(2\ 3)$ dans $\mathcal{B}_{2}$, puis $(1\ 3\ 2)$, $(1\ 3)$ dans $\mathcal{B}_{1}$, en échangeant successivement les valeurs $1$ et $2$, $1$ et $3$, $1$ et $2$, $1$ et $3$, $1$ et $2$. Un programme qui suit cette construction en vérifie la validité jusqu'à $n = 6$.

À retenir. Les signatures de deux termes consécutifs sont opposées : une telle énumération alterne permutations paires et impaires, ce qui est cohérent avec le fait qu'il y en a autant de chaque sorte. Un algorithme classique, dit de Steinhaus, Johnson et Trotter, réalise même une énumération dans laquelle chaque transposition échange deux positions voisines.