entiers i et j tels que a i = a j et i < j. Puisque a i = s
i (a 0 ) et a j = s
j (a 0 ), on a
s
i (a 0 ) = s
j (a 0 ), donc a 0 = s
−i
s
j (a 0 )
= s
j−i (a 0 ) et j − i > 0.
On en déduit qu’il existe un plus petit entier p > 0 tel que a p = a 0 . Si p = 1, alors
s(a 0 ) = a 0 et a 0 est un point fixe de s.
Supposons p 2. Les p premiers itérés de a 0 sont a 0 , a 1 , . . . , a p−1 , et comme on a
a p = a 0 , il vient a p+i = s
p+i (a 0 ) = s
i
s
p (a 0 )
= s
i (a p ) = s
i (a 0 ) = a i pour tout entier i.
La suite a 0 , a 1 , a 2 , . . . des itérés de a 0 est donc périodique de période p. La permutation s transforme les entiers a 0 , a 1 , . . . , a p−1 en envoyant chacun des p − 1 premiers
sur le suivant et en envoyant a p−1 sur a p = a 0 . Les entiers a 0 , . . . , a p−1 sont donc
transformés par s exactement comme par le p-cycle (a 0 a 1 · · · a p−1 ).
Remarquons que si l’on itère a 0 par s
−1 , on obtient successivement a p−1 , . . . , a 1 , a 0 :
l’ensemble iter(a) = {a 0 , a 1 , . . . , a p−1 } des itérés de a 0 est donc aussi l’ensemble de
tous les éléments s
k (a 0 ), où k parcourt Z.
Exemple.
i s(i)
1
3
2
6
3
8
4
2
5
5
6
4
7
1
8
7
9 10
10 9
Soit s la permutation de {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} définie par
le tableau ci-contre.
Dans les graphiques ci-dessous, les flèches permettent de visualiser les
itérés d’un élément :
® les itérés de 1 sont 1, s(1) = 3, s(3) = 8 et s(8) = 7 ;
® les itérés de 2 sont : 2, s(2) = 6 et s(6) = 4 ;
® les éléments 9 et 10 sont échangés ;
® on a s(5) = 5, autrement dit 5 est un point fixe de s.
cycle (1 3 8 7)
cycle (2 6 4) transposition (9 10)
9
1 0
1
3
7
8
2
4
6
Reprenons le cas général d’une permutation s de E . Nous avons montré que l’ensemble
des itérés d’un élément a ∈ E est aussi iter(a) = {s
k (a) | k ∈ Z}.
Si b ∈ E , on a l’équivalence b = s
k (a) ⇐⇒ a = s
−k (b) : b est donc un itéré de a si et
seulement si a est un itéré de b. Si b est un itéré de a, alors tout itéré de b est un itéré
de a et réciproquement, donc les éléments a et b ont même ensemble d’itérés.
On en déduit que si des ensembles iter(a) et iter(a
) ont en commun un élément x,
alors ces ensembles sont égaux. En effet, x étant un itéré de a, on a iter(x) = iter(a),
et de même on a iter(x) = iter(a
) ; il s’ensuit iter(a) = iter(a
).
Les différents ensembles iter(a), iter(b), . . . sont donc des parties de E deux à deux
disjointes et leur réunion est E .
Rappelons ce que nous avons montré avant l’exemple : si un élément a possède q itérés, où q 2, alors pour tout u ∈ iter(a), on a iter(a) = {u,s(u),. . .,s
q−1 (u)} et tous les
éléments de iter(a) sont transformés par s selon le q-cycle c =
u s(u) · · · s
q−1 (u)
.
Théorème. Soit s une permutation de E différente de l’identité.
® Il existe des cycles c 1 , . . . , c m , dont les supports sont des parties deux à deux disjointes
et tels que s = c 1 c 2 · · · c m .
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 73
i (a 0 ) et a j = s
j (a 0 ), on a
s
i (a 0 ) = s
j (a 0 ), donc a 0 = s
−i
s
j (a 0 )
= s
j−i (a 0 ) et j − i > 0.
On en déduit qu’il existe un plus petit entier p > 0 tel que a p = a 0 . Si p = 1, alors
s(a 0 ) = a 0 et a 0 est un point fixe de s.
Supposons p 2. Les p premiers itérés de a 0 sont a 0 , a 1 , . . . , a p−1 , et comme on a
a p = a 0 , il vient a p+i = s
p+i (a 0 ) = s
i
s
p (a 0 )
= s
i (a p ) = s
i (a 0 ) = a i pour tout entier i.
La suite a 0 , a 1 , a 2 , . . . des itérés de a 0 est donc périodique de période p. La permutation s transforme les entiers a 0 , a 1 , . . . , a p−1 en envoyant chacun des p − 1 premiers
sur le suivant et en envoyant a p−1 sur a p = a 0 . Les entiers a 0 , . . . , a p−1 sont donc
transformés par s exactement comme par le p-cycle (a 0 a 1 · · · a p−1 ).
Remarquons que si l’on itère a 0 par s
−1 , on obtient successivement a p−1 , . . . , a 1 , a 0 :
l’ensemble iter(a) = {a 0 , a 1 , . . . , a p−1 } des itérés de a 0 est donc aussi l’ensemble de
tous les éléments s
k (a 0 ), où k parcourt Z.
Exemple.
i s(i)
1
3
2
6
3
8
4
2
5
5
6
4
7
1
8
7
9 10
10 9
Soit s la permutation de {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} définie par
le tableau ci-contre.
Dans les graphiques ci-dessous, les flèches permettent de visualiser les
itérés d’un élément :
® les itérés de 1 sont 1, s(1) = 3, s(3) = 8 et s(8) = 7 ;
® les itérés de 2 sont : 2, s(2) = 6 et s(6) = 4 ;
® les éléments 9 et 10 sont échangés ;
® on a s(5) = 5, autrement dit 5 est un point fixe de s.
cycle (1 3 8 7)
cycle (2 6 4) transposition (9 10)
9
1 0
1
3
7
8
2
4
6
Reprenons le cas général d’une permutation s de E . Nous avons montré que l’ensemble
des itérés d’un élément a ∈ E est aussi iter(a) = {s
k (a) | k ∈ Z}.
Si b ∈ E , on a l’équivalence b = s
k (a) ⇐⇒ a = s
−k (b) : b est donc un itéré de a si et
seulement si a est un itéré de b. Si b est un itéré de a, alors tout itéré de b est un itéré
de a et réciproquement, donc les éléments a et b ont même ensemble d’itérés.
On en déduit que si des ensembles iter(a) et iter(a
) ont en commun un élément x,
alors ces ensembles sont égaux. En effet, x étant un itéré de a, on a iter(x) = iter(a),
et de même on a iter(x) = iter(a
) ; il s’ensuit iter(a) = iter(a
).
Les différents ensembles iter(a), iter(b), . . . sont donc des parties de E deux à deux
disjointes et leur réunion est E .
Rappelons ce que nous avons montré avant l’exemple : si un élément a possède q itérés, où q 2, alors pour tout u ∈ iter(a), on a iter(a) = {u,s(u),. . .,s
q−1 (u)} et tous les
éléments de iter(a) sont transformés par s selon le q-cycle c =
u s(u) · · · s
q−1 (u)
.
Théorème. Soit s une permutation de E différente de l’identité.
® Il existe des cycles c 1 , . . . , c m , dont les supports sont des parties deux à deux disjointes
et tels que s = c 1 c 2 · · · c m .
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 73