Exercice 9

Par la proposition 3, toute permutation est un produit de transpositions ; il suffit donc, dans chaque cas, d'écrire toute transposition comme un produit d'éléments de la famille.

1. Soit $a \neq b$ dans $[\![2\,;n]\!]$. Par l'exercice 8, avec $\sigma = (1\ a)$, qui est son propre inverse, on obtient $$\boxed{(1\ a)(1\ b)(1\ a) = (a\ b)}$$ car $\sigma(1) = a$ et $\sigma(b) = b$. Les transpositions qui contiennent $1$ sont dans la famille, et les autres sont de la forme $(a\ b)$ ci-dessus : toutes sont des produits d'éléments de la famille.

2. On montre par récurrence sur $k \in [\![2\,;n]\!]$ que $(1\ k)$ est un produit des transpositions $(i\ \ i + 1)$. C'est vrai pour $k = 2$. Si c'est vrai pour $k - 1$, avec $k \geqslant 3$, l'exercice 8 appliqué avec $\sigma = (k - 1\ \ k)$, qui fixe $1$ et envoie $k - 1$ sur $k$, donne $$\boxed{(k - 1\ \ k)(1\ \ k - 1)(k - 1\ \ k) = (1\ k)}$$ et $(1\ k)$ est encore un produit de transpositions $(i\ \ i + 1)$. La question 1 conclut.

3. On a $c^{k}(i) = i + k$ dès que $i + k \leqslant n$. Pour $k \in [\![0\,;n - 2]\!]$, l'exercice 8 donne donc $$\boxed{c^{k}tc^{-k} = \big(c^{k}(1)\ \ c^{k}(2)\big) = (k + 1\ \ k + 2)}$$ Comme $c^{n} = \mathrm{id}$, on a $c^{-k} = c^{n - k}$, qui est un produit de facteurs égaux à $c$. Les transpositions $(1\ 2)$, …, $(n - 1\ \ n)$ sont donc des produits de $t$ et de $c$, et la question 2 conclut.

Piège. La définition de l'énoncé n'autorise que des produits d'éléments de la famille, pas de leurs inverses. Pour une transposition, cela ne change rien ; pour le cycle $c$, il faut remarquer que $c^{-1} = c^{n - 1}$.

À retenir. La question 2 dit que l'on peut ranger n'importe quelle suite par des échanges successifs de termes voisins : c'est le tri que représente la figure des croisements du cours, où chaque croisement est l'échange de deux voisins.