Exercice 16

1. La relation est réflexive, avec le produit vide $\mathrm{id}$. Elle est symétrique : si $\sigma = t_{1}\cdots t_{m}$ avec $t_{i} \in \mathcal{T}$ et $\sigma(i) = j$, alors $\sigma^{-1} = t_{m}\cdots t_{1}$ est encore un produit d'éléments de $\mathcal{T}$, chaque transposition étant son propre inverse, et $\sigma^{-1}(j) = i$. Elle est transitive : si $\sigma(i) = j$ et $\sigma'(j) = k$, le produit $\sigma'\sigma$ convient pour $i \sim k$. $$\boxed{\sim \text{ est une relation d'équivalence sur } [\![1\,;n]\!]}$$

2. On raisonne par récurrence sur $k$. Si $k = 0$, le seul produit est $\mathrm{id}$, et les classes sont les $n$ singletons. Soit $k \geqslant 1$, $\mathcal{T}$ un ensemble de $k$ transpositions, $\tau = (a\ b)$ l'une d'elles, et $\mathcal{T}' = \mathcal{T} \setminus \{\tau\}$, de relation associée $\sim'$. Par hypothèse de récurrence, $\sim'$ a au moins $n - k + 1$ classes.

On considère la partition $\mathcal{P}$ de $[\![1\,;n]\!]$ obtenue à partir des classes de $\sim'$ en réunissant la classe de $a$ et celle de $b$ ; elle a au moins $n - k$ parties. Chaque élément de $\mathcal{T}'$ envoie toute classe de $\sim'$ dans elle-même, par définition de $\sim'$, donc envoie toute partie de $\mathcal{P}$ dans elle-même. La transposition $\tau$ fixe tous les éléments autres que $a$ et $b$, et envoie la partie contenant $a$ et $b$ dans elle-même. Par conséquent, tout produit d'éléments de $\mathcal{T}$ envoie chaque partie de $\mathcal{P}$ dans elle-même : si $i \sim j$, alors $i$ et $j$ sont dans la même partie de $\mathcal{P}$. Chaque classe de $\sim$ est donc contenue dans une partie de $\mathcal{P}$, et chaque partie, non vide, en contient au moins une. $$\boxed{\text{le nombre de classes de } \sim \text{ est au moins } \operatorname{card}\mathcal{P} \geqslant n - k}$$

3. Si $\mathcal{T}$ engendre $\mathfrak{S}_{n}$, alors pour tous $i \neq j$, la transposition $(i\ j)$ est un produit d'éléments de $\mathcal{T}$ qui envoie $i$ sur $j$ : la relation $\sim$ n'a qu'une classe. La question 2 donne $1 \geqslant n - k$. $$\boxed{\operatorname{card}\mathcal{T} \geqslant n - 1, \text{ et ce minimum est atteint, par exemple par } (1\ 2), (2\ 3), \dots, (n - 1\ \ n)}$$ L'exemple est celui de l'exercice 9, question 2 ; la famille $(1\ 2)$, …, $(1\ n)$ de la question 1 convient aussi.

À retenir. On peut dessiner les $k$ transpositions comme les arêtes d'un graphe sur les sommets $1$, …, $n$ ; les classes de $\sim$ sont les « morceaux » connexes de ce dessin. Chaque arête réunit au plus deux morceaux, d'où la minoration, et il faut au moins $n - 1$ arêtes pour relier $n$ sommets.