Nous voyons qu’il est possible d’obtenir par cette méthode toutes les transpositions
du type (1 k), avec k ∈ {2,. . . ,n} . Rédigeons ce premier résultat. Nous procéderons
par récurrence.
Notons T le sous-ensemble de S n formé de toutes les permutations que l’on
peut obtenir en composant les transpositions (i i + 1), avec
i ∈ {1,. . . ,n − 1}. Montrons par récurrence que, quel que soit
k ∈ {2,. . . ,n} , la proposition
H k : « la transposition (1 k) appartient à T »
est vraie.
La proposition H 2 est vraie car la transposition (1 2) appartient à T.
• Soit k ∈ {2,. . . ,n − 1} tel que la proposition H k est vraie. La transposition (1 k) appartient alors à T. Nous avons
(k k + 1) ◦ (1 k) ◦ (k k + 1) = (1 k + 1).
Par conséquent, la transposition (1 k + 1) appartient à T et la proposition
H k+1 est vraie.
• Finalement, quel que soit k ∈ {2,. . . ,n} , la transposition (1 k) appartient
à T.
Nous devons maintenant obtenir toutes les transpositions manquantes. Soient
i, j ∈ {2,. . . ,n} avec j i + 2. Comment obtenir la transposition (i j) ? D’après le
résultat que nous venons de démontrer, nous savons échanger 1 avec n’importe quel
autre élément. Il est donc naturel de chercher à passer par 1 pour échanger i et j.
Nous échangerons donc d’abord 1 et i, puis 1 et j. On obtient
(1 j) ◦ (1 i) = (1 i j).
Nous avons bien réussi à envoyer i sur j, mais j est envoyé sur 1. Nous allons donc
envoyer 1 sur i à la fin. Nous obtenons
(1 i) ◦ (1 j) ◦ (1 i) = (i j).
Remarquons que cette formule est encore du type considéré à la première question.
Nous utiliserons cette observation dans la rédaction.
• Montrons que toutes les transpositions de S n appartiennent à T. Soient
i, j ∈ {1,. . . ,n} avec i < j. Si i = 1, cela découle du résultat précédent.
Supposons que i 2. Posons σ = (1 i). On a σ(1) = i et σ( j) = j, car
i = / j. D’après la question 1., on a donc
σ ◦ (1 j) ◦ σ
−1
= (1 i) ◦ (1 j) ◦ (1 i) = (i j).
248
Partie 3 • Algèbre
9782100547678-Fresl-C10.qxd 5/07/10 8:47 Page 248
du type (1 k), avec k ∈ {2,. . . ,n} . Rédigeons ce premier résultat. Nous procéderons
par récurrence.
Notons T le sous-ensemble de S n formé de toutes les permutations que l’on
peut obtenir en composant les transpositions (i i + 1), avec
i ∈ {1,. . . ,n − 1}. Montrons par récurrence que, quel que soit
k ∈ {2,. . . ,n} , la proposition
H k : « la transposition (1 k) appartient à T »
est vraie.
La proposition H 2 est vraie car la transposition (1 2) appartient à T.
• Soit k ∈ {2,. . . ,n − 1} tel que la proposition H k est vraie. La transposition (1 k) appartient alors à T. Nous avons
(k k + 1) ◦ (1 k) ◦ (k k + 1) = (1 k + 1).
Par conséquent, la transposition (1 k + 1) appartient à T et la proposition
H k+1 est vraie.
• Finalement, quel que soit k ∈ {2,. . . ,n} , la transposition (1 k) appartient
à T.
Nous devons maintenant obtenir toutes les transpositions manquantes. Soient
i, j ∈ {2,. . . ,n} avec j i + 2. Comment obtenir la transposition (i j) ? D’après le
résultat que nous venons de démontrer, nous savons échanger 1 avec n’importe quel
autre élément. Il est donc naturel de chercher à passer par 1 pour échanger i et j.
Nous échangerons donc d’abord 1 et i, puis 1 et j. On obtient
(1 j) ◦ (1 i) = (1 i j).
Nous avons bien réussi à envoyer i sur j, mais j est envoyé sur 1. Nous allons donc
envoyer 1 sur i à la fin. Nous obtenons
(1 i) ◦ (1 j) ◦ (1 i) = (i j).
Remarquons que cette formule est encore du type considéré à la première question.
Nous utiliserons cette observation dans la rédaction.
• Montrons que toutes les transpositions de S n appartiennent à T. Soient
i, j ∈ {1,. . . ,n} avec i < j. Si i = 1, cela découle du résultat précédent.
Supposons que i 2. Posons σ = (1 i). On a σ(1) = i et σ( j) = j, car
i = / j. D’après la question 1., on a donc
σ ◦ (1 j) ◦ σ
−1
= (1 i) ◦ (1 j) ◦ (1 i) = (i j).
248
Partie 3 • Algèbre
9782100547678-Fresl-C10.qxd 5/07/10 8:47 Page 248