Par conséquent, la transposition (i j) appartient à T.
• Finalement, toutes les transpositions appartiennent à T. Or nous savons
que les transpositions engendrent S n . On en déduit que T = S n et donc que
les transpositions (i i + 1), avec i ∈ {1,. . . ,n − 1}, engendrent S n .
3. Cette fois-ci, nous ne disposons que de deux éléments : le cycle (1 2 . . . n) et la
transposition (1 2). La formule de la première question appliquée avec ces deux
éléments nous donne
(1 2 . . . n) ◦ (1 2) ◦ (1 2 . . . n)
−1
= (2 3).
En continuant ainsi, nous pouvons obtenir toutes les transpositions (i i + 1), avec
i ∈ {1,. . . ,n − 1}. Nous savons, d’après la question précédente, que ces transpositions engendrent S n .
Cependant, nous avons eu besoin pour écrire la formule d’utiliser la permutation
(1 2 . . . n)
−1
= (1 n n − 1 . . . 2).
Comment obtenir cette permutation en utilisant seulement (1 2 . . . n) et (1 2) ? Le
cycle dont nous disposons, (1 2 . . . n) , correspond à des décalages de 1 dans les
indices. Le cycle que nous voulons obtenir, (1 n n − 1 . . . 2), correspond à des
décalages de n − 1, mais est du même type. Nous allons donc prendre la puissance
(n − 1)-ième du premier cycle afin d’obtenir des décalages de n − 1 et le second
cycle. Nous rédigerons tout cela par récurrence.
Notons σ = (1 2 . . . n) . Montrons par récurrence que, quel que soit
k ∈ N ∗ , la proposition
H k : « ∀i ∈ {1,. . . ,n}, σ k (i) = i + k mod n »
est vraie.
• La proposition H 1 est vraie par définition de σ.
• Soit k ∈ N ∗ tel que la proposition H k soit vraie. On a alors
∀i ∈ {1,. . . ,n}, σ
k
(i) = i + k mod n.
Soit i ∈ {1,. . . ,n}. Notons j l’unique élément de {1,. . . ,n} tel que
j = i + k mod n. Nous avons alors σ k (i) = j. On a
σ k+1 (i) = σ(σ k (i))
= σ( j)
= j + 1 mod n
= i + k + 1 mod n.
© Dunod. La photocopie non autorisée est un délit.
249
Chapitre 10 • Algèbre générale
9782100547678-Fresl-C10.qxd 5/07/10 8:47 Page 249
• Finalement, toutes les transpositions appartiennent à T. Or nous savons
que les transpositions engendrent S n . On en déduit que T = S n et donc que
les transpositions (i i + 1), avec i ∈ {1,. . . ,n − 1}, engendrent S n .
3. Cette fois-ci, nous ne disposons que de deux éléments : le cycle (1 2 . . . n) et la
transposition (1 2). La formule de la première question appliquée avec ces deux
éléments nous donne
(1 2 . . . n) ◦ (1 2) ◦ (1 2 . . . n)
−1
= (2 3).
En continuant ainsi, nous pouvons obtenir toutes les transpositions (i i + 1), avec
i ∈ {1,. . . ,n − 1}. Nous savons, d’après la question précédente, que ces transpositions engendrent S n .
Cependant, nous avons eu besoin pour écrire la formule d’utiliser la permutation
(1 2 . . . n)
−1
= (1 n n − 1 . . . 2).
Comment obtenir cette permutation en utilisant seulement (1 2 . . . n) et (1 2) ? Le
cycle dont nous disposons, (1 2 . . . n) , correspond à des décalages de 1 dans les
indices. Le cycle que nous voulons obtenir, (1 n n − 1 . . . 2), correspond à des
décalages de n − 1, mais est du même type. Nous allons donc prendre la puissance
(n − 1)-ième du premier cycle afin d’obtenir des décalages de n − 1 et le second
cycle. Nous rédigerons tout cela par récurrence.
Notons σ = (1 2 . . . n) . Montrons par récurrence que, quel que soit
k ∈ N ∗ , la proposition
H k : « ∀i ∈ {1,. . . ,n}, σ k (i) = i + k mod n »
est vraie.
• La proposition H 1 est vraie par définition de σ.
• Soit k ∈ N ∗ tel que la proposition H k soit vraie. On a alors
∀i ∈ {1,. . . ,n}, σ
k
(i) = i + k mod n.
Soit i ∈ {1,. . . ,n}. Notons j l’unique élément de {1,. . . ,n} tel que
j = i + k mod n. Nous avons alors σ k (i) = j. On a
σ k+1 (i) = σ(σ k (i))
= σ( j)
= j + 1 mod n
= i + k + 1 mod n.
© Dunod. La photocopie non autorisée est un délit.
249
Chapitre 10 • Algèbre générale
9782100547678-Fresl-C10.qxd 5/07/10 8:47 Page 249