Chapitre 17

G ROUPE SYMÉTRIQUE
Mohamed TARQI

Table des matières

1 Structure de groupe 1
1.1 Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Permutations particulières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Les transpositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Les cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Décomposition d’une permutation 3

2.1 Décomposition en produit de cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Décomposition en produit de transpositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Signature d’une permutation. Groupe alterné 5

3.1 Signature d’une permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Groupe alterné . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

•••••••••••

1 Structure de groupe
1.1 Définitions et propriétés
Définition 1.1 Soit E un ensemble fini. On appelle permutation de E une bijection de E . On note S (E ) l’ensemble des
permutations de E . Si E = [[1, n]], on note S n l’ensemble des permutations de [[1, n]].

En général, une permutation est notée σ, %,..., id désigne la permutation identique. La composée σ ◦ % sera notée
tout simplement σ%.

Exemple :
µ ¶
1 2 3 4 5 6
1. Sur [[1, 6]], σ = représente la permutation σ définie par :
3 5 1 2 4 6

σ(1) = 3, σ(2) = 5, σ(3) = 1, σ(4) = 2, σ(5) = 4, σ(6) = 6.

µ ¶
−1 1 2 3 4 5 6 −1
σ , sa bijection réciproque, est définie par : σ = .
3 4 1 5 2 6
µ ¶ µ ¶ µ ¶
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
2. La composition de σ = et ρ = et la permutation ρσ = .
3 5 1 2 4 6 5 1 4 3 6 2 4 6 5 1 3 2

Proposition 1.1 L’ensemble des permutations d’un ensemble fini est fini, en particulier card S n = n!.

Démonstration : Voir chapitre "ensembles finis et dénombrement". u

t

Théorème et définition 1.1 L’ensemble des permutations de [[1, n]], muni de la loi de composition des appli-
cations est un groupe. On l’appelle groupe symétrique.

1
C HAPITRE 17 G ROUPE SYMÉTRIQUE

µ ¶
a b c x ... y
Remarque : Le groupe (S n , ◦) est non commutatif pour n ≥ 3, par exemple , pour σ = et % =
b c a x ... y
µ ¶
a b c x ... y
on a : σ% 6= %σ.
b a c x ... y

Définition 1.2 On appelle support de la permutation σ d’un ensemble E l’ensemble { x ∈ E /σ( x) 6= x}. On le note suppσ.

Remarque : Si σ et % sont à supports disjoints, alors σ% = %σ. En effet, si x ∉ suppσ, σ( x) ∈ supp% et donc %σ( x) = σ( x)
et σ%( x) = σ( x), donc %σ = σ%.

1.2 Permutations particulières

1.2.1 Les transpositions
Définition 1.3 On appelle transposition τ i j de i et j la permutation définie par :
τ i j ( i ) = j, τ i j ( j) = i et τ i j ( k) = k, ∀k 6= i et k 6= j.

Elle permute uniquement les deux termes i et j.

Remarques :
1. Une permutation σ est une transposition si, et seulement si, son support se réduit à deux éléments.
2. Pour toute transposition τ i, j , τ−i,1j = τ i, j .

1.2.2 Les cycles

Définition 1.4 On dit que σ ∈ S n (n ≥ 2) est un cycle de longueur l s’il existe a1 , a2 ,..., a l distincts de [[1, n]] tels que :
1. σ(a1 ) = a2 , σ(a2 ) = a3 ,..., σ(a l −1 = a l , σ(a l ) = a1
2. Pour tout élément b ∈ [[1, n]]\{a1 , a2 ,..., a l }, σ(b) = b
En général, on pose σ = (a1 , a2 ,..., a l ). Un cycle de longueur n est appelé une permutation circulaire.

Exemples :
µ ¶
1 2 3 4 5 6
1. σ = est le cycle (1, 3, 6, 5).
3 2 6 4 1 5
µ ¶
1 2 3 4 5 6
2. σ = est le cycle (1, 6, 5, 3, 4, 2) ; c’est une permutation circulaire.
6 1 4 2 3 5

Remarques :
1. Le support d’un cycle (a1 , a2 ,..., a l ) est {a1 , a2 ,..., a l }.
2. Si σ = (a1 , a2 ,..., a l ) alors σ−1 = (a l , a l −1 ,..., a1 ).
3. Si σ est un cycle de longueur l alors σl = id .

Définition 1.5 Soit σ une permutation de S n et k un élément de ∈ [[1, n]]. On appelle orbite de k l’ensemble {σ p (k)/ p ∈ N}.
On le note O (k).

Remarque : L’ensemble des orbites forme une partition de ∈ [[1, n]] : ∈ [[1, n]] = O ( k ).
S
k∈[[1,n]]

µ ¶
1 2 3 4 5 6
Exemple : Pour σ = il y a trois orbites : {1, 3, 6}, {2} et {4, 5}.
3 2 6 5 4 1

Proposition 1.2 Les orbites d’une permutation sont de la forme { i, σ( i ),..., σ p ( i )}, formé des éléments dis-
tincts, avec σ p+1 ( i ) déjà trouvé dans l’orbite.

Cours de Mathématiques MP 2/6 Rédigé par: M.Tarqi

C HAPITRE 17 G ROUPE SYMÉTRIQUE

Démonstration : On a nécessairement σ p+ i ( i ) = i , en effet, si σ p+1 ( i ) = σk ( i ) avec k > 0, alors, en composant par

σ−k , on aurait σ p+1−k ( i ) = i , ce qui contredit la définition de p. D’autre part, les autres permutations de puissances
n supérieures à p appartiennent à l’orbite, il suffit de considérer la division de n par p, n = pq + r, 0 ≤ r < p, pour
voir que σn ( i ) = σr ( i ) est déjà dans l’orbite. u
t

2 Décomposition d’une permutation

2.1 Décomposition en produit de cycles
Théorème 2.1 Toute permutation de S n (n ≥ 2) se décompose en produit de cycles à supports deux à deux
disjoints. Cette décomposition est unique à l’ordre prés des facteurs.

Démonstration : Soit σ ∈ S n \{ id }, alors il existe un élément de {1, 2,..., n}, noté a1 tel que σ(a1 ) 6= a1 . Soit E = {α ∈ N
/ σα (a1 ) ∈ {a1 , σ(a),..., σα−1 (a1 )}}, c’est une partie de N non vide ( n ∈ N ). Considérons donc q = inf E .
On a σ q (a1 ) ∈ {a1 ,..., σ q−1 (a1 )} alors σ q (a1 ) = a1 , en effet, si σ q (a1 ) = σk (a1 ) avec (0 < k < q), alors σ q−k (a1 ) = a1 ceci
contredit le choix de q.
Posons S = suppσ\suppc1 où c1 = (a1 , σ(a),..., σ q−1 (a1 )) et soit σ1 la permutation définie par :
½
σ( x) si x ∈ S
σ1 ( x ) =
x si x ∉ S
Alors σ = c1 σ1 , en effet, on a :
• si k ∉ suppσ = S ∪ suppc1 = supps ∪ suppc, alors c1 σ1 (k) = c1 (k) = σ(k) puisque suppσ1 ∩ suppc1 = ;.
• si k ∈ suppc1 il existe (0 ≤ r ≤ q − 1) tel que k = σr (a1 ) et donc :

c 1 σ1 ( k ) = c 1 σ1 σ r ( a 1 )
= c1 σr ( a1 )
= σr+1 ( a1)
= σ( σ k ( a 1 )
= σ( k )

• si k ∈ suppσ1 , c1 σ1 (k) = σ1 c1 (k) = s(k) = σ(k) par construction.

D’où : σ = c1 σ1 , par récurrence sur le cardinal de suppσ, on montre que σ1 est le produit des cycles deux à deux
disjointes. u
t

Remarque : Soit σ = c1 c2 ...c p une permutation décomposée en un produit de cycles à supports disjoints. Pour
tout entier m, on a :
σm = c1m c2m ...c m
p.

Exemple d’application : Considérons la permutation :

¡1 2 3 4 5 6 7¢
σ= 2461735 = (124)(36)(57)

Alors on peut écrire :

¡1 2 3 4 5 6 7¢
σ2006 = (124)2006 (36)2006 (57)2006 = (124)3×668+2 = (124)2 = (142) = 2431567

2.2 Décomposition en produit de transpositions

Proposition 2.1 Les transpositions engendrent le groupe symétrique S n .

Démonstration : Il suffit de prouver que tout cycle se décompose en transposition, cela découle de l’égalité :
(a1 , a2 ,..., a l ) = (a1 , a2 )(a2 , a3 )...(a l −1 , a l ).
u
t

Proposition 2.2 Les transpositions τ i,i+1 (1 ≤ i ≤ n − 1) engendrent le groupe symétrique S n .

Cours de Mathématiques MP 3/6 Rédigé par: M.Tarqi

C HAPITRE 17 G ROUPE SYMÉTRIQUE

Démonstration : Toute permutation étant le produit de transposition, il suffit donc de prouver que toute trans-
position est produit de transpositions de type τ i,i+1 .
En effet, Soit τ = τ p,q une transposition de S n , ( p < q).
On pose :
γ = τ p,p+1 ◦ τ p+1,p+2 ...τ q−2,q−1 ◦ τ q−1,q ◦ τ q−1,q−2 ...τ p+2,p+1 ◦ τ p+1,p

on a :
γ( p) = q, γ( q) = p et γ( k) = k si k ∉ { p, q}

d’où

τ = γ.

Remarque : Il y a (n − 1) générateurs de ce type.

Proposition 2.3 Le groupe S n est engendré par la transposition τ = (1, 2) et le cycle c = (1, 2,..., n).

Démonstration : Montrons d’abord que si σ ∈ S n , c = (a1 , a2 ,...a r ) un cycle, alors

σ cσ−1 = (σ( a1 ), σ( a2 ),..., σ( a r )).

En effet, posons γ = (σ(a1 ),..., σ(a r )), F = {σ(a i ), i = 1,..., r} et E = F ∪ F c = {1, 2,..., n}.
1 er cas : k ∈ F, k = σ(a i ) pour un certain 1 ≤ i ≤ r.
on a :
½
σ( a i+1 ) si 1 ≤ i < r
γ( k) = γ(σ( a i )) =
σ( a1 ) si i = r

et
½
σ( a i+1 ) si 1 ≤ i ≤ r
σ c σ− 1 ( k ) = σ c ( a i ) =
σ( a1 ) si i = r

d’où σ cσ−1 = γ
2 e cas : k ∉ F

k = σ(α), α ∉ {a1 , a2 ,..., a r }

γσ(α) = σ(α) = k

σ cσ−1 ( k) = σ c(α) = σ(α) = k

d’où :
σ c σ− 1 = γ
Montrons maintenant que S n est engendré par τ = (1, 2) et c = (1, 2,..., n), il suffit de vérifier que pour tout 1 ≤ i ≤
n − 1, ( i, i + 1) est une expression de τ et σ

(1, 2) = τ1 c0

cτ c−1 = ( c(1), c(2)) = (2, 3)

c i τ c− i = ( c i (1), c i (2)) = ( i + 1, i + 2), i ≤ n − 2

donc si σ ∈ S n , σ = c i −1 τ c 1 − i . u
Q Q
( i, i + 1) = t
fini fini

Remarque : (τ, c) est le minimum de générateurs de S n , on dit que S n est un groupe dicyclique, les groupes diédraux sont
aussi des groupes dicycliques.

Cours de Mathématiques MP 4/6 Rédigé par: M.Tarqi

C HAPITRE 17 G ROUPE SYMÉTRIQUE

3 Signature d’une permutation. Groupe alterné

3.1 Signature d’une permutation
Théorème et définition 3.1 Soit σ ∈ S n une permutation de S n , il y a égalité entre les quatre quantités sui-
vantes :
1. (−1)T où T est le nombre de transpositions dans une décomposition de σ en un produit de transpo-
sitions.
2. (−1)n−D où D est le nombre d’orbite de σ.
3. (−1) I où I est le nombre d’inversions de σ, c’est-à-dire le nombre de couples ( i, j) avec i < j et σ( i ) >
σ( j ) .
Q σ( i)−σ( j )
4. i− j .
i< j

Cette quantité commune s’appelle signature de la permutation σ, on la note ε(σ).

σ( i)−σ( j )
Remarque : La quantité (4) s’écrit aussi :
Q
i− j
i6= j

Démonstration : Montrons que (1) = (2). Notons ε(σ) la quantité (2). On remarque que, pour toute permutation σ
et toute transposition τ, ε(στ) = −ε(τ). En effet, si τ = τ i j , nous avons deux cas à envisager :
1. i et j sont dans le même orbite de σ { i, σ( i ),..., σ p ( i )}, σk ( i ) = j et σ p+1 ( i ) = i. L’orbite de i par στ est l’ensemble
formé par les éléments suivants : i , στ( i ) = σ( j) = i , (στ)2 ( i ) = στσk+1 ( i ) = σk+2 ( i ) sauf si k + 2 = p + 1....(στ)r ( i ) =
σk+r ( i ) tant que k + r < p + 1...(στ) p−k+1 ( i ) = (στ)(στ) p−k ( i ) = σ p+1 = i .
L’orbite de j contient donc les nombres σr ( i ) avec 1 ≤ r ≤ k. L’orbite initiale est donc scindée en 2. Les autres
orbites sont invariantes par τ. Il y a une orbite de plus. Donc ε(στ) = −ε(τ).
2. i et j sont dans deux orbites différentes de σ. L’orbite de i par σ est { i, σ( i ),..., σ p ( i )} et celle de j est { j, σ( j),..., σk ( j)},
σk ( i ) = j.
L’orbite de i par στ est l’ensemble formé par les éléments suivants : i , στ( i ) = σ( j) = i , (στ)2 ( i ) = στσ( j) = σ2 ( j)
sauf si k = 1....(στ)r ( i ) = σr ( j) sauf si k = r − 1...(στ)k ( i ) = (στ)σk−1 ( j) = σk ( j), (στ)k+1 ( i ) = (στ)σk ( j) = σk+1 ( j) = j,
(στ)k+2 ( i ) = (στ)( j) = σ( i )... (στ)k+1+r ( i ) = σr ( i )...(στ)k+1+ p ( i ) = σ p ( i )
L’orbite de i par στ est constituée de la réunion de deux orbites de i et de j par σ. Les autres orbites sont
invariantes par τ. Il y a donc une orbite de moins. Donc ε(σ) change de signe.
Montrons que (4) = (3). La quantité (3) = (4), en effet, le numérateur et le dénominateur comporte tous les produits
i − j, au signe près, du fait de la bijectivité de σ. En valeur absolue, cette quantité égale à 1, son signe est donnée
par le nombre de couple ( i, j) tel que i < j et σ( i ) > σ( j), c’est-à-dire le nombre d’inversions de σ.
Q σ( i)−σ( j )
Montrons enfin que (1) = (3). Posons ε0 (σ) = i− j , on a :
i6= j

Y σσ0 ( i ) − σσ0 ( j)
ε0 (σσ0 ) =
i6= j i− j
Y σσ0 ( i ) − σσ0 ( j) Y σ0 ( i ) − σ0 ( j)
= 0 0
i6= j σ ( i ) − σ ( j) i6= j i− j
Y σ( I ) − σ( J ) Y σ0 ( i ) − σ0 ( j )
=
i6= j I−J i6= j i− j
= ε 0 ( σ) ε 0 ( σ0 )

en posant I = σ0 ( i ) et J = σ0 ( j).
Enfin, pour une transposition, ε0 (τ) = −1, en effet, si τ = ( i, j) alors il y a 2( j − i ) − 1 inversions, donc par récurrence
sur le nombre de transpositions qui constitue une permutation σ, ε0 (σ) est égale à la formule (1).
Ainsi toutes les formules sont donc égales. u
t

Cours de Mathématiques MP 5/6 Rédigé par: M.Tarqi

C HAPITRE 17 G ROUPE SYMÉTRIQUE

Exemples :
1. L’application σ de [1, n] de [|1, n|] définie par x 7−→ n + 1 − x admet pour inversions tous les couples ( i, j) tels
2 n(n−1)
que ( i < j). Donc ε(σ) = (−1){n = (−1) 2 .
2. ε(a1 , a2 ,..., a l ) = ε[(a1 , a2 )(a2 , a3 )...(a l −1 , a l )] = (−1)l −1 .
µ ¶
1 2 3 4 5 6 7 8 9
3. Si σ = , alors σ = (1345)(279)(6810) = (13)(34)(45)(27)(79)(68) et donc ε(σ) =
3 7 4 5 1 8 9 6 2
10−6
(−1) = 1.

3.2 Groupe alterné

Théorème et définition 3.2 L’application σ 7−→ ε(σ) est un morphisme du groupe (S n , ◦) sur le groupe ({−1, 1}, ×).
Son noyau ( l’ensemble des permutations paires ) est un sous-groupe de S n . On l’appelle le groupe alterné
d’indice n, et il est noté An .

Démonstration : D’après le paragraphe précédent, la formule (1) permet de voir que ε(σσ0 ) = ε(σ)ε(σ0). ε est
donc un morphisme du groupe (S n , ◦) dans le groupe ({−1, 1}, ×). L’image réciproque de 1 par ε est l’ensemble des
permutations paires est un groupe, sous-groupe de groupe symétrique. u
t

Remarque : Il y a autant de permutations paires que des permutations impaires, en effet, fixons τ une permu-
tation impaire ( par exemple une transposition ), alors la transformation σ 7−→ τσ est une bijection de S n qui
transforme une permutation paire en une permutation impaire. En particulier card An = n2! .

Proposition 3.1 Le groupe alterné An est engendré par les 3-cycles.

Démonstration : • Si n = 2 alors S2 = { id, (1, 2)} et A 2 = { id }.

• Si n = 3 alors A 3 = { id, (1, 2, 3), (1, 3, 2)}.
• Soit n ≥ 4 et σ ∈ A n , σ = τ1 τ2 ...τr , les τ i sont des transpositions.
r
Y
ε ( σ) = 1 =⇒ ε (τ i ) = 1
i =1
r
(−1) = (−1)r = 1
Y
=⇒
i =1
=⇒ r = 2s

donc σ = τ1 τ2 ...τ2s−1 τ2s . σ étant un produit de doubles transpositions, donc il suffit de vérifier que chaque double
transposition est un produit de 3-cycles.
Or les deux sortes de doubles transpositions sont ( i, j)( j, k) et ( i, j)(k, l ). On a ( i, j)( j, k) = ( i, j, k) et ( i, j)(k, l ) =
( i, j)( j, k)( j, k)(k, l ) = ( i, j, k)( j, k, l ). D’où le résultat.
u
t

• • • • • • • • ••

Cours de Mathématiques MP 6/6 Rédigé par: M.Tarqi