Générateurs du groupe symétrique $\mathcal{S}_n$

1. Génération par les transpositions adjacentes

   Toute permutation $s \in \mathcal{S}_n$ se décompose en un produit de transpositions. Il suffit donc de montrer que toute transposition $(i\ j)$ avec $i < j$ s'écrit comme un produit de transpositions adjacentes $\tau_k = (k\ k+1)$.
   On procède par récurrence sur la distance $d = j - i$ :
   • Initialisation : Si $d = 1$, alors $(i\ j) = (i\ i+1) = \tau_i$, qui est une transposition adjacente.
   • Hérédité : Supposons que toute transposition $(i\ j)$ avec $j - i = k \geqslant 1$ s'écrive comme produit de transpositions adjacentes. Considérons une transposition $(i\ i+k+1)$.
     On utilise la relation de conjugaison : \[ (i\ i+k+1) = (i+k\ i+k+1)(i\ i+k)(i+k\ i+k+1) \]
   • Le terme $(i+k\ i+k+1)$ est la transposition adjacente $\tau_{i+k}$. Le terme $(i\ i+k)$ correspond à une distance $k$, il est donc produit de transpositions adjacentes par hypothèse de récurrence.
   Par principe de récurrence, les $\tau_i$ permettent de générer toutes les transpositions, et engendrent par conséquent $\mathcal{S}_n$.



2. Génération par $(1\ 2)$ et le $n$-cycle $(1\ 2\ \cdots\ n)$

   Posons $\tau = (1\ 2)$ et $c = (1\ 2\ \cdots\ n)$. Soit $H = \langle \tau, c \rangle$ le sous-groupe engendré.
   Rappelons la propriété de conjugaison d'un cycle par une permutation $\sigma$ : \[ \sigma (a\ b) \sigma^{-1} = (\sigma(a)\ \sigma(b)) \]
   • En conjuguant $\tau$ par le cycle $c$, on obtient : \[ c \tau c^{-1} = c (1\ 2) c^{-1} = (c(1)\ c(2)) = (2\ 3) = \tau_2 \]
   • En itérant ce procédé, on obtient pour tout $1 \leqslant k \leqslant n-2$ : \[ c^k \tau c^{-k} = c^k (1\ 2) c^{-k} = (k+1\ k+2) = \tau_{k+1} \]
   Le sous-groupe $H$ contient donc toutes les transpositions adjacentes $\tau_1, \tau_2, \dots, \tau_{n-1}$.
   D'après la question précédente, ces éléments engendrent $\mathcal{S}_n$. On en déduit que $H = \mathcal{S}_n$.