Exemples
® Soit le 12-cycle c = (1 2 3 4 5 6 7 8 9 10 11 12). On a c
12 = id, donc c
11 = c
−1 ,
c
2 = (1 3 5 7 9 11)(2 4 6 8 10 12) et c
10 = (c
2 )
−1
c
3 = (1 4 7 10)(2 5 8 11)(3 6 9 12) et c
9 = (c
3 )
−1
c
4 = (1 5 9)(2 6 10)(3 7 11)(4 8 12) et c
8 = (c
4 )
−1
c
5 = (1 6 11 4 9 2 7 12 5 10 3 8)
et c
7 = (c
5 )
−1
c
6 = (1 7)(2 8)(3 9)(4 10)(5 11)(6 12) .
Les entiers positifs compris entre 1 et 12 et premiers à 12 sont 1, 5, 7 et 11 :
si k un entier compris entre 1 et 11, la permutation c
k n’est un cycle que si
k ∈ {1, 5, 7, 11}. Si k est l’un des entiers 2, 3, 4, 6, 8, 9 ou 10, la permutation c
k
se décompose en deux, trois, quatre ou six cycles de longueur 6, 4, 3 ou 2.
® Soit p un nombre premier, c’est-à-dire que p est un entier au moins égal à 2 dont les
seuls diviseurs positifs sont 1 et p. Si c est un p-cycle, alors pour tout entier k non
multiple de p, c
k est un p-cycle. En effet, 1 est le seul diviseur commun à p et k.
2.4 Le rôle des transpositions
Rappelons qu’une transposition est par définition un 2-cycle (a b).
a) Si des éléments sont écrits dans un ordre, on peut en échanger deux quelconques par une
succession d’échanges entre éléments consécutifs.
Par exemple, pour échanger 1 et 4 dans la succession 1, 2, 3, 4, nous pouvons
effectuer les échanges suivants :
échange 1 2 3 4
(1 2)
2 1 3 4
(1 3)
2 3 1 4
(1 4)
2 3 4 1
(4 3)
2 4 3 1
(4 2)
4 2 3 1
On a l’égalité (1 4) = (4 2)(4 3)(1 4)(1 3)(1 2) et dans cette composée, chaque
transposition échange deux éléments qui étaient consécutifs.
b) Tout cycle est un composé de transpositions.
On a en effet l’égalité (a 1 a 2 · · · a p ) = (a 1 a 2 )(a 2 a 3 ) · · · (a p−1 a p ).
Nous avons montré que toute permutation est une composée de cycles (l’identité
étant égale à la composée τ τ , où τ est une transposition quelconque). On en déduit :
Proposition. Toute permutation est une composée de transpositions.
76 – PERMUTATIONS
® Soit le 12-cycle c = (1 2 3 4 5 6 7 8 9 10 11 12). On a c
12 = id, donc c
11 = c
−1 ,
c
2 = (1 3 5 7 9 11)(2 4 6 8 10 12) et c
10 = (c
2 )
−1
c
3 = (1 4 7 10)(2 5 8 11)(3 6 9 12) et c
9 = (c
3 )
−1
c
4 = (1 5 9)(2 6 10)(3 7 11)(4 8 12) et c
8 = (c
4 )
−1
c
5 = (1 6 11 4 9 2 7 12 5 10 3 8)
et c
7 = (c
5 )
−1
c
6 = (1 7)(2 8)(3 9)(4 10)(5 11)(6 12) .
Les entiers positifs compris entre 1 et 12 et premiers à 12 sont 1, 5, 7 et 11 :
si k un entier compris entre 1 et 11, la permutation c
k n’est un cycle que si
k ∈ {1, 5, 7, 11}. Si k est l’un des entiers 2, 3, 4, 6, 8, 9 ou 10, la permutation c
k
se décompose en deux, trois, quatre ou six cycles de longueur 6, 4, 3 ou 2.
® Soit p un nombre premier, c’est-à-dire que p est un entier au moins égal à 2 dont les
seuls diviseurs positifs sont 1 et p. Si c est un p-cycle, alors pour tout entier k non
multiple de p, c
k est un p-cycle. En effet, 1 est le seul diviseur commun à p et k.
2.4 Le rôle des transpositions
Rappelons qu’une transposition est par définition un 2-cycle (a b).
a) Si des éléments sont écrits dans un ordre, on peut en échanger deux quelconques par une
succession d’échanges entre éléments consécutifs.
Par exemple, pour échanger 1 et 4 dans la succession 1, 2, 3, 4, nous pouvons
effectuer les échanges suivants :
échange 1 2 3 4
(1 2)
2 1 3 4
(1 3)
2 3 1 4
(1 4)
2 3 4 1
(4 3)
2 4 3 1
(4 2)
4 2 3 1
On a l’égalité (1 4) = (4 2)(4 3)(1 4)(1 3)(1 2) et dans cette composée, chaque
transposition échange deux éléments qui étaient consécutifs.
b) Tout cycle est un composé de transpositions.
On a en effet l’égalité (a 1 a 2 · · · a p ) = (a 1 a 2 )(a 2 a 3 ) · · · (a p−1 a p ).
Nous avons montré que toute permutation est une composée de cycles (l’identité
étant égale à la composée τ τ , où τ est une transposition quelconque). On en déduit :
Proposition. Toute permutation est une composée de transpositions.
76 – PERMUTATIONS