Par définition, la transformation c permute circulairement les entiers a 1 , . . . , a p :
c : a 1 → a 2 → · · · → a p−1 → a p → a 1
et laisse fixe tous les autres entiers.
Définitions
La permutation c définie ci-dessus s’appelle un p-cycle et se note c = (a 1 a 2 · · · a p ).
L’ensemble {a 1 , . . . , a p } est le support du cycle c et l’entier p est la longueur du
cycle. Un 2-cycle s’appelle une transposition.
Exemples 1
® Soient a et b deux éléments différents de {1, 2, . . . , n}. La transposition c = (a b)
échange les entiers a et b en laissant fixes tous les autres entiers. On a c
2 =c◦c=id E .
La transposition (b a) échange aussi les entiers a et b en laissant fixes les autres,
donc on a (a b) = (b a).
® La permutation c = (3 2 5) est un 3-cycle de S 6 : il est défini par c(1) = 1, c(2) = 5,
c(3)=2, c(4)=4, c(5)=3 et c(6)=6. Remarquons que l’on a aussi c=(2 5 3)=(5 3 2).
Puisqu’on a c
2 (3)=c◦c(3)=c(2)=5, c
2 (2)=c(5)=3, c
2 (5)=c(3)=2, la permutation
c
2 est déterminée par
c
2 : 3 → 5 → 2 → 3
et c
2 (k) = k si k ∈ {1, 4, 6} ;
cela montre que c
2 est le 3-cycle (3 5 2).
On a aussi c
3 (3) = c(5) = 3, c
3 (2) = c(3) = 2, c
3 (5) = c(2) = 5 et c
3 (k) = k si
k ∈ {1, 4, 6}, donc c
3 = id E . Cette égalité s’écrit c ◦ c
2 = id E , donc il vient c
−1 = c
2 .
Exemple 2. L’inverse du p-cycle (a 1 a 2 · · · a p ) est le p-cycle (a p · · · a 2 a 1 ).
Soit c = (a 1 a 2 · · · a p ) un p-cycle. Les itérés de a 1 par c sont successivement
a 2 , . . . , a p , a 1 , a 2 , . . . et plus précisément, nous avons c
i (a 1 ) = a i+1 pour 1 i p − 1
et c
p (a 1 ) = a 1 . Si k est un entier compris entre 1 et p, alors a k = c
k−1 (a 1 ), donc
c
p (a k ) = c
p
◦ c
k−1 (a 1 ) = c
p+k−1 (a 1 ) = c
k−1
◦ c
p (a 1 ) = c
k−1 (a 1 ) = a k .
Ainsi la permutation c
p laisse fixe les entiers a k , et comme elle laisse fixe les autres
entiers, on en déduit que c
p est l’identité. Il s’ensuit c
−1 = c
p−1 = (a p · · · a 2 a 1 ).
Proposition. Si c = (a 1 a 2 · · · a p ) est un p-cycle appartenant à S n , alors c
p = id E
et p est le plus petit entier k > 0 tel que c
k = id E .
Composés de permutations
Notation. Si s et s
sont des permutations de E , la composée s◦s
se note simplement
ss
.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 71
c : a 1 → a 2 → · · · → a p−1 → a p → a 1
et laisse fixe tous les autres entiers.
Définitions
La permutation c définie ci-dessus s’appelle un p-cycle et se note c = (a 1 a 2 · · · a p ).
L’ensemble {a 1 , . . . , a p } est le support du cycle c et l’entier p est la longueur du
cycle. Un 2-cycle s’appelle une transposition.
Exemples 1
® Soient a et b deux éléments différents de {1, 2, . . . , n}. La transposition c = (a b)
échange les entiers a et b en laissant fixes tous les autres entiers. On a c
2 =c◦c=id E .
La transposition (b a) échange aussi les entiers a et b en laissant fixes les autres,
donc on a (a b) = (b a).
® La permutation c = (3 2 5) est un 3-cycle de S 6 : il est défini par c(1) = 1, c(2) = 5,
c(3)=2, c(4)=4, c(5)=3 et c(6)=6. Remarquons que l’on a aussi c=(2 5 3)=(5 3 2).
Puisqu’on a c
2 (3)=c◦c(3)=c(2)=5, c
2 (2)=c(5)=3, c
2 (5)=c(3)=2, la permutation
c
2 est déterminée par
c
2 : 3 → 5 → 2 → 3
et c
2 (k) = k si k ∈ {1, 4, 6} ;
cela montre que c
2 est le 3-cycle (3 5 2).
On a aussi c
3 (3) = c(5) = 3, c
3 (2) = c(3) = 2, c
3 (5) = c(2) = 5 et c
3 (k) = k si
k ∈ {1, 4, 6}, donc c
3 = id E . Cette égalité s’écrit c ◦ c
2 = id E , donc il vient c
−1 = c
2 .
Exemple 2. L’inverse du p-cycle (a 1 a 2 · · · a p ) est le p-cycle (a p · · · a 2 a 1 ).
Soit c = (a 1 a 2 · · · a p ) un p-cycle. Les itérés de a 1 par c sont successivement
a 2 , . . . , a p , a 1 , a 2 , . . . et plus précisément, nous avons c
i (a 1 ) = a i+1 pour 1 i p − 1
et c
p (a 1 ) = a 1 . Si k est un entier compris entre 1 et p, alors a k = c
k−1 (a 1 ), donc
c
p (a k ) = c
p
◦ c
k−1 (a 1 ) = c
p+k−1 (a 1 ) = c
k−1
◦ c
p (a 1 ) = c
k−1 (a 1 ) = a k .
Ainsi la permutation c
p laisse fixe les entiers a k , et comme elle laisse fixe les autres
entiers, on en déduit que c
p est l’identité. Il s’ensuit c
−1 = c
p−1 = (a p · · · a 2 a 1 ).
Proposition. Si c = (a 1 a 2 · · · a p ) est un p-cycle appartenant à S n , alors c
p = id E
et p est le plus petit entier k > 0 tel que c
k = id E .
Composés de permutations
Notation. Si s et s
sont des permutations de E , la composée s◦s
se note simplement
ss
.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 71