38 Groupe symétrique
1 Permutations. 1
2 Cycles. 2
3 Transpositions. 3
4 Théorèmes de décomposition. 3
5 Signature. 4
Exercices 5
Dans tout ce chapitre, n sera un entier naturel non nul.
1 Permutations.
Dé nition 1.
Une bijection de J1, nK dans lui même est appelée une permutation de J1, nK.
L'ensemble des permutations de J1, nK sera noté Sn .
On peut représenter une permutation σ ∈ Sn à l'aide du tableau
1 2 ··· n
σ(1) σ(2) · · · σ(n)
Exemple 2.
Soient
1 2 3 4 5 0 1 2 3 4 5
σ= et σ = .
2 5 4 3 1 2 3 4 1 5
Calculer σ ◦ σ 0 , σ 0 ◦ σ , σ 2 et σ −1 .
Proposition 3.
1. (Sn , ◦) est un groupe, appelé groupe symétrique.
2. Sn est ni et son cardinal vaut n!
3. Ce groupe n'est pas abélien dès que n ≥ 3.
Notation multiplicative : pour σ, σ 0 ∈ Sn , on pourra noter σσ 0 la permutation σ ◦ σ 0 .
1 MP2I PV
Dé nition 4 (Un peu de vocabulaire sur les permutations).
Soit σ ∈ Sn .
1. Si x ∈ J1, nK, l'ensemble σ k (x), k ∈ N est appelé orbite de x.
2. On dit que x est un point xe de σ si σ(x) = x.
Les points xes sont ainsi les éléments de J1, nK dont l'orbite est un singleton.
3. On appelle support de σ l'ensemble des éléments de J1, nK qui ne sont pas un point xe.
4. Deux permutations σ et σ 0 sont dites conjuguées s'il existe α ∈ Sn tel que σ 0 = ασα−1 .
2 Cycles.
Dé nition 5.
Soit p un entier supérieur à 2.
Une permutation γ est appelée un p-cycle s'il existe p éléments distincts a1 , . . . , ap de J1, nK tels
que
γ γ γ γ
a1 7→ a2 7→ a3 · · · 7→ ap 7→ a1
et ∀b ∈ J1, nK \ {a1 , · · · , ap } γ(b) = b.
On note alors
γ = (a1 a2 · · · ap ).
Notation.
Soit γ = (a1 a2 . . . ap ) un p-cycle. Il y a p façons de décrire γ comme un p-cycle :
γ = (a1 a2 . . . ap ) = (a2 . . . ap a1 ) = (a3 . . . ap a1 a2 ) = . . . = (ap a1 . . . ap−1 ).
On peut aussi écrire les choses ainsi : pour tout entier a dans le support de γ ,
γ = a γ(a) γ 2 (a) · · · γ p−1 (a) .
Exemple 6 (Calculs sur un cycle).
Soit γ = (a1 . . . ap ) un p-cycle. Déterminer γ −1 et γ p .
Exemple 7 (Conjugué d'un cycle).
Soit γ = (a1 . . . ap ) un cycle et σ ∈ Sn . Montrer que
σγσ −1 = (σ(a1 ) σ(a2 ) . . . σ(ap )) .
Ce calcul peut être utilisé pour démontrer que tous les p-cycles sont conjugués.
2
Proposition 8.
Deux cycles de supports disjoints commutent.
3 Transpositions.
Dé nition 9.
Une permutation τ qui est un 2-cycle sera appelée une transposition.
Une transposition est donc une permutation de la forme (a, b) où {a, b} est une paire de J1, nK.
Proposition 10 (Involutivité).
Si τ est une transposition, alors
τ 2 = id et τ −1 = τ.
Lemme 11 (Décomposition d'un cycle en produit de transpositions).
Soit γ = (a1 . . . ap ) un p-cycle. Alors
γ = (a1 a2 )(a2 a3 ) . . . (ap−1 ap ) ou γ = (a1 ap )(a1 ap−1 ) . . . (a1 a2 )
4 Théorèmes de décomposition.
Théorème 12 (Décomposition en produit de cycles à supports disjoints).
Soit σ ∈ Sn . Il existe γ1 , . . . , γr r cycles à supports disjoints tels que
σ = γ1 γ2 · · · γr .
Les γi commutent. Cette décomposition est unique à l'ordre des facteurs près.
Exemple 13 (Une décomposition).
On considère la permutation
1 2 3 4 5 6 7 8
σ= .
5 4 1 7 8 6 2 3
1. Décomposer σ en produit de cycles à supports disjoints.
2. Déterminer σ 4 , σ 12 et σ 666
3
Corollaire 14.
Toute permutation est un produit de transpositions.
La décomposition n'est pas unique et les transpositions ne commutent pas nécessairement.
Exemple 15 (une décomposition).
Décomposer en produit de transpositions la permutation
1 2 3 4 5 6 7
σ= .
7 5 1 2 4 6 3
5 Signature.
Dé nition 16.
Soit σ ∈ Sn .
1. Une paire {i, j} de J1, nK est une inversion pour σ si i − j et σ(i) − σ(j) sont de signe
opposé.
2. Le nombre d'inversions de σ est noté Inv(σ).
3. On appelle signature de σ le nombre ε(σ) = (−1)Inv(σ) .
Exemple 17.
Après avoir calculé son nombre d'inversions, donner la signature de
1 2 3 4 5 6
σ= .
3 2 1 4 6 5
Proposition 18.
1. L'identité a pour signature 1.
2. Les transpositions ont pour signature −1.
Proposition 19 (La signature écrite comme un produit).
Y σ(i) − σ(j)
∀σ ∈ Sn ε(σ) = ,
i−j
{i,j}
le produit étant indexé par l'ensemble de toutes les paires {i, j} (donc i 6= j ) de J1, nK.
4
Théorème 20.
La signature est l'unique application ε : Sn → {−1, 1} telle que
1. ∀σ, σ 0 ∈ Sn ε(σσ 0 ) = ε(σ)ε(σ 0 ).
2. Pour toute transposition τ ∈ Sn , ε(τ ) = −1.
Corollaire 21.
La signature est l'unique morphisme de groupes non trivial de (Sn , ◦) dans (C∗ , ×).
Exercices
38.1 Écrire explicitement S1 , S2 et S3 .
38.2 Sous-groupe alterné
Notons An l'ensemble des permutations de signature égale à 1.
Justi er qu'il s'agit là d'un sous-groupe de Sn et que si n ≥ 2, |An | = 2.
n!
38.3 (*) Théorème de Cayley
Soit G un groupe ni de cardinal n.
1. Pour a ∈ G, on pose
G → G
τa : .
x 7→ ax
l'opérateur de translation à gauche associé à a. Véri er que pour tout a dans G, τa est un automorphisme
de G.
2. Véri er que
G → SG
Φ:
a 7→ τa
est un morphisme de groupes injectif.
3. En déduire que G est isomorphe à un sous-groupe de Sn .
38.4 (*)Centre de Sn
On note Z(Sn ) le centre de Sn , c'est-à-dire l'ensemble des permutations qui commutent avec toutes les autres.
1. Que vaut Z(S2 ) ?
2. Montrer que Z(Sn ) est trivial dès que n ≥ 3.
38.5 (*)Nombre de points xes d'une permutation aléatoire
On choisit uniformément et au hasard une permutation de J1, nK. On note Y le nombre de ses points xes.
Après avoir explicité un espace probabilisé sur lequel Y peut être dé ni comme une variable aléatoire, donner
l'espérance et la variance de Y .
On a déjà croisé cette idée fondamentale : un cardinal s'écrit comme...
