Groupe engendré par une permutation
Soit s une permutation de l’ensemble E = {1,2,. . .,n}, différente de l’identité. Rappelons que l’ensemble T = {s
k
| k ∈ Z} est un groupe de transformations de E (page 28).
D’après le théorème, il y a un plus petit entier r > 0 tel que s
r = id E . Il s’ensuit que
les transformations id E = s
0 , s, . . . , s
r−1 sont deux à deux différentes et que s
r+j = s
j
pour tout entier j . On a donc simplement T = {id E , s, . . . , s
r−1
} et le groupe T
possède r éléments.
Soient s
i et s
j des éléments de T , donc s
i s
j = s
i+j . En appelant k le reste de la division de i + j par r, il vient i + j = rq + k et s
i s
j = s
rq+k = (s
r )
q s
k = (id E )
q s
k = s
k , où
k est compris entre 0 et r. Cela permet de calculer dans le groupe T . On détermine
r au moyen de la décomposition en cycles et du théorème précédent.
Exemples
® Pour la permutation s de l’exemple page 73, on a T = {s
i
| 0 i 11} (avec la
convention s
0 = id E ).
® Supposons que s est un p-cycle (a 1 a 2 . . . a p ). Alors on a T = {id E , s, · · · , s
p−1
}.
Dans le groupe T engendré par s, les règles de calcul sont les mêmes que dans
le groupe engendré par une rotation d’angle 2π/p (exemple 3 page 28).
2.3 Puissance d'un cycle
Les permutations les plus utilisées en pratique sont les cycles. En particulier, on est
souvent amené à étudier les puissances c
k d’un cycle c.
Rappelons que si p et q sont des entiers positifs, on a la relation
ppcm(p, q) × pgcd(p, q) = pq
Proposition. Soient c un p-cycle et k un entier strictement positif et non multiple de p.
Posons d = pgcd(p, k). La permutation c
k est composée de d cycles, tous de même longueur
p/d. Pour que c
k soit un cycle, il faut et il suffit que p et k soient premiers entre eux.
Démonstration. Posons c=(a 0 a 1 · · · a p ) et s=c
k . Soit x∈{a 0 ,. . .,a p }. Le cycle des itérés de x
par s a pour longueur le plus petit entier m>0 tel que s
m (x)=x, c’est-à-dire c
km (x)=x. Puisque
c est un p-cycle, l’égalité c
i (x)=x se produit si et seulement si i est multiple de p. On en déduit
s
m (x) = x ⇐⇒ c
km (x) = x ⇐⇒ km est multiple de p
⇐⇒ km est multiple de p et de k
⇐⇒ km est multiple de ppcm(p, k) =
pk
d
⇐⇒ m est multiple de
p
d
.
Ainsi, lorsqu’on décompose c
k en cycles, tous les cycles obtenus ont même longueur p/d ; il
y a donc d cycles. Pour que c
k soit un cycle, il faut et il suffit que d = 1, c’est-à-dire que p
et k soient premiers entre eux.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 75
Soit s une permutation de l’ensemble E = {1,2,. . .,n}, différente de l’identité. Rappelons que l’ensemble T = {s
k
| k ∈ Z} est un groupe de transformations de E (page 28).
D’après le théorème, il y a un plus petit entier r > 0 tel que s
r = id E . Il s’ensuit que
les transformations id E = s
0 , s, . . . , s
r−1 sont deux à deux différentes et que s
r+j = s
j
pour tout entier j . On a donc simplement T = {id E , s, . . . , s
r−1
} et le groupe T
possède r éléments.
Soient s
i et s
j des éléments de T , donc s
i s
j = s
i+j . En appelant k le reste de la division de i + j par r, il vient i + j = rq + k et s
i s
j = s
rq+k = (s
r )
q s
k = (id E )
q s
k = s
k , où
k est compris entre 0 et r. Cela permet de calculer dans le groupe T . On détermine
r au moyen de la décomposition en cycles et du théorème précédent.
Exemples
® Pour la permutation s de l’exemple page 73, on a T = {s
i
| 0 i 11} (avec la
convention s
0 = id E ).
® Supposons que s est un p-cycle (a 1 a 2 . . . a p ). Alors on a T = {id E , s, · · · , s
p−1
}.
Dans le groupe T engendré par s, les règles de calcul sont les mêmes que dans
le groupe engendré par une rotation d’angle 2π/p (exemple 3 page 28).
2.3 Puissance d'un cycle
Les permutations les plus utilisées en pratique sont les cycles. En particulier, on est
souvent amené à étudier les puissances c
k d’un cycle c.
Rappelons que si p et q sont des entiers positifs, on a la relation
ppcm(p, q) × pgcd(p, q) = pq
Proposition. Soient c un p-cycle et k un entier strictement positif et non multiple de p.
Posons d = pgcd(p, k). La permutation c
k est composée de d cycles, tous de même longueur
p/d. Pour que c
k soit un cycle, il faut et il suffit que p et k soient premiers entre eux.
Démonstration. Posons c=(a 0 a 1 · · · a p ) et s=c
k . Soit x∈{a 0 ,. . .,a p }. Le cycle des itérés de x
par s a pour longueur le plus petit entier m>0 tel que s
m (x)=x, c’est-à-dire c
km (x)=x. Puisque
c est un p-cycle, l’égalité c
i (x)=x se produit si et seulement si i est multiple de p. On en déduit
s
m (x) = x ⇐⇒ c
km (x) = x ⇐⇒ km est multiple de p
⇐⇒ km est multiple de p et de k
⇐⇒ km est multiple de ppcm(p, k) =
pk
d
⇐⇒ m est multiple de
p
d
.
Ainsi, lorsqu’on décompose c
k en cycles, tous les cycles obtenus ont même longueur p/d ; il
y a donc d cycles. Pour que c
k soit un cycle, il faut et il suffit que d = 1, c’est-à-dire que p
et k soient premiers entre eux.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 75