Montrer que tout élément de Sₙ est produit de transpositions de la…

Stratégie : récurrence forte sur le nombre d'inversions. C'est la traduction mathématique du tri à bulles : tant qu'il reste une descente, on l'échange, et on prouve qu'on progresse en montrant qu'un tel échange fait perdre exactement une inversion.

Le compteur. Pour $\sigma \in {\mathcal{S}}_n$, posons $$I(\sigma )=\#\{(i,j):i<j\text{et}\sigma (i)>\sigma (j)\}\in \left[\left[0,\left(\genfrac{}{}{0ex}{}{n}{2}\right)\right]\right].$$

Initialisation ($I(\sigma )=0$). Alors $\sigma (1)<\sigma (2)<\cdots <\sigma (n)$ ; une suite strictement croissante de $[[1,n]]$ dans lui-même vaut nécessairement $\sigma (k)=k$. Donc $\sigma =\mathrm{id}$, produit vide de transpositions voisines.

Hérédité. Supposons le résultat acquis pour toute permutation ayant strictement moins de $m$ inversions, et soit $\sigma$ avec $I(\sigma )=m⩾1$. Comme $\sigma \ne \mathrm{id}$, la suite $(\sigma (1),\dots ,\sigma (n))$ n'est pas croissante : il existe un indice $i$ avec $$\sigma (i)>\sigma (i+1).$$ Posons $\tau =(ii+1)$ et considérons $\sigma \tau$ : c'est $\sigma$ dont on a échangé les valeurs aux positions $i$ et $i+1$, puisque $(\sigma \tau )(i)=\sigma (i+1)$ et $(\sigma \tau )(i+1)=\sigma (i)$.

⚠️ Le point délicat, et c'est là que l'adjacence sert. Comptons les inversions de $\sigma \tau$ : pour tout couple $\{k,\ell \}$ autre que $\{i,i+1\}$, l'ordre relatif des deux valeurs est inchangé — car les positions $i$ et $i+1$ sont voisines, donc aucun indice ne se trouve entre elles pour voir son statut basculer. Seul le couple $(i,i+1)$ change : il était inversé, il ne l'est plus. Donc $$I(\sigma \tau )=I(\sigma )-1=m-1.$$ Avec une transposition non voisine $(ij)$, $j>i+1$, ce comptage s'effondre : le nombre d'inversions varie de $2(j-i)-1$, et la récurrence ne descend plus d'un cran.

Par hypothèse de récurrence, $\sigma \tau ={\tau }_1\cdots {\tau }_p$ avec des ${\tau }_k$ voisines. Alors $$\sigma =(\sigma \tau ){\tau }^{-1}={\tau }_1\cdots {\tau }_p\tau ,$$ produit de transpositions voisines. $■$

$$\boxed{{\mathcal{S}}_n=⟨(12),(23),\dots ,(n-1n)⟩}$$

Contrôle sur un exemple. $\sigma =(13)$ dans ${\mathcal{S}}_3$, de mot $(3,2,1)$, avec $I(\sigma )=3$. Le tri à bulles : $$(3,2,1)\stackrel{{\tau }_1=(12)}{\to }(2,3,1)\stackrel{{\tau }_2=(23)}{\to }(2,1,3)\stackrel{{\tau }_1}{\to }(1,2,3).$$ Donc $\sigma {\tau }_1{\tau }_2{\tau }_1=\mathrm{id}$, soit $\sigma ={\tau }_1{\tau }_2{\tau }_1$. Vérification directe : $1\stackrel{{\tau }_1}{\to }2\stackrel{{\tau }_2}{\to }3\stackrel{{\tau }_1}{\to }3$, et $3\stackrel{{\tau }_1}{\to }3\stackrel{{\tau }_2}{\to }2\stackrel{{\tau }_1}{\to }1$, et $2\mapsto 2$ : c'est bien $(13)$ ✓. Trois transpositions, donc impaire — conforme à $\epsilon ((13))=-1$ ✓. (L'énoncé a été vérifié par énumération exhaustive de ${\mathcal{S}}_n$ pour $n⩽6$ : les $720$ permutations sont toutes atteintes.)

Ce que l'exercice installe. Deux choses. D'abord, ${\mathcal{S}}_n$ est engendré par $n-1$ éléments seulement — un système de générateurs minimal, dont les relations donnent la présentation de Coxeter du groupe symétrique. Ensuite, la démonstration est l'algorithme du tri à bulles, et le nombre d'échanges qu'il effectue est exactement $I(\sigma )$ : c'est pourquoi son coût est en $\Theta (n^2)$ dans le pire cas — le pire cas étant précisément le renversement de l'exercice 1, avec ses $\frac{n(n-1)}{2}$ inversions. On obtient au passage une deuxième preuve que $\epsilon (\sigma )=(-1{)}^{I(\sigma )}$.