Travaux pratiques
8. Écrire une fonction orbitesG renvoyant, en fonction de l’entier k et du groupe
de permutations G, la liste des orbites pour l’action diagonale sur X k
n . En
testant sur la liste des L i , quel nombre minimal d’orbites trouve-t-on pour
l’action sur X 3
n ? Justifier qu’une action 3-transitive donne lieu à 5-orbites,
puis donner la liste des groupes de permutations 3-transitifs de degré inférieur
ou égal à 5.
Parmi ces derniers, lesquels opèrent 4-transitivement ? Démontrer au papiercrayon que S n agit n-transitivement et que A n agit (n−2)-transitivement pour
tout n.
9. Soit Π(k) l’ensemble des partitions de {1, . . . , k} et π : X k
n → Π(k) l’application définie par x → π x , où π x désigne la partition correspond à la relation
d’équivalence i ∼ j ⇔ x i = x j . Démontrer que o → π o := π x (x ∈ o), définit
une application surjective de l’ensemble O des orbites pour l’action diagonale
sur X k
n vers Π(k), et que cette application est injective lorsque l’action est
k-transitive. En déduire que le nombre d’orbites distinctes pour une action
k-transitive sur X k
n est égal au nombre p(k) de partitions de {1, . . . , k}.
Il existe différentes façons de calculer p(k) :
(a) Soit p(k, j) le nombre de partitions de l’ensemble {1, . . . , k} en j sousensembles (disjoints) ; on a p(k, k) = p(k, 1) = 1 et
p(k, j) = jp(k − 1, j) + p(k − 1, j − 1)
(on distingue selon que k est tout seul ou appartient à l’un des j ensembles
de la partition de {1, . . . , k − 1}). Cette relation permet de calculer p(k, j)
par récurrence, puis p(k) =
k
j=1 p(k, j).
(b) Soit on utilise la formule
p(k) =
k
j=1
k−j
r=0
(−1)
r j k
r!j!
·
Calculer p(k) jusqu’à k = 10, par les deux méthodes. Pour la première, on
n’oubliera pas d’ajouter option remember au début de la procédure récursive
que l’on écrira, ce qui diminue les temps de calcul.
Formule de Burnside
Soit G un groupe fini opérant sur un ensemble fini X et soit N le nombre
d’orbites. Pour g ∈ G, on note r(g) le nombre de points fixes de g dans X, i.e. le
111
8. Écrire une fonction orbitesG renvoyant, en fonction de l’entier k et du groupe
de permutations G, la liste des orbites pour l’action diagonale sur X k
n . En
testant sur la liste des L i , quel nombre minimal d’orbites trouve-t-on pour
l’action sur X 3
n ? Justifier qu’une action 3-transitive donne lieu à 5-orbites,
puis donner la liste des groupes de permutations 3-transitifs de degré inférieur
ou égal à 5.
Parmi ces derniers, lesquels opèrent 4-transitivement ? Démontrer au papiercrayon que S n agit n-transitivement et que A n agit (n−2)-transitivement pour
tout n.
9. Soit Π(k) l’ensemble des partitions de {1, . . . , k} et π : X k
n → Π(k) l’application définie par x → π x , où π x désigne la partition correspond à la relation
d’équivalence i ∼ j ⇔ x i = x j . Démontrer que o → π o := π x (x ∈ o), définit
une application surjective de l’ensemble O des orbites pour l’action diagonale
sur X k
n vers Π(k), et que cette application est injective lorsque l’action est
k-transitive. En déduire que le nombre d’orbites distinctes pour une action
k-transitive sur X k
n est égal au nombre p(k) de partitions de {1, . . . , k}.
Il existe différentes façons de calculer p(k) :
(a) Soit p(k, j) le nombre de partitions de l’ensemble {1, . . . , k} en j sousensembles (disjoints) ; on a p(k, k) = p(k, 1) = 1 et
p(k, j) = jp(k − 1, j) + p(k − 1, j − 1)
(on distingue selon que k est tout seul ou appartient à l’un des j ensembles
de la partition de {1, . . . , k − 1}). Cette relation permet de calculer p(k, j)
par récurrence, puis p(k) =
k
j=1 p(k, j).
(b) Soit on utilise la formule
p(k) =
k
j=1
k−j
r=0
(−1)
r j k
r!j!
·
Calculer p(k) jusqu’à k = 10, par les deux méthodes. Pour la première, on
n’oubliera pas d’ajouter option remember au début de la procédure récursive
que l’on écrira, ce qui diminue les temps de calcul.
Formule de Burnside
Soit G un groupe fini opérant sur un ensemble fini X et soit N le nombre
d’orbites. Pour g ∈ G, on note r(g) le nombre de points fixes de g dans X, i.e. le
111