Travaux pratiques
Même question pour le degré 7 :
L[27]:=permgroup(7,{[[1,2,3,4,5,6,7]]}):
L[28]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[2,7],[3,6],[4,5]]}):
L[29]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[2,3,5],[4,7,6]]}):
L[30]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[2,4,3,7,5,6]]}):
L[31]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[2,3],[4,7]]}):
L[32]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[1,2,3]]}):
L[33]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[1,2]]}):
Voyez-vous d’autres groupes que A n et S n ? Tester sur les deux derniers
exemples suivants :
L[34]:=permgroup(11,{[[1,2,3,4,5,6,7,8,9,10,11]],[[3,7,11,8],
[4,10,5,6]]}):
L[35]:=permgroup(12,{[[1,2,3,4,5,6,7,8,9,10,11]],
[[3,7,11,8],[4,10,5,6]],[[1,12],[2,11],[3,6],[4,8],[5,9],
[7,10]]}):
C’est un fait assez surprenant : les seuls groupes finis qui sont au moins
4-transitifs sont, à part les groupes A n et S n , les quatre groupes de Mathieu
M 11 , M 12 , M 23 et M 24 . Les deux premiers ont été notés L 34 et L 35 dans la
liste précédente ; les deux autres sont d’ordre 23 et 24, d’où des temps de
calcul très longs.
Énumérations de Polya
Soient A, B deux ensembles finis et G un groupe de permutations agissant sur
A. On considère l’action suivante de G sur l’ensemble B A des fonctions f : A → B :
un élément g agit par (g · f )(a) = f (g · a). La formule d’énumération de Polya
nous dit que l’ensemble O des orbites sous G de B A est de cardinal
N =
1
Card(G)
g∈G
Card(B)
cg ,
où c g désigne le nombre de cycles dans la décomposition de g en produits de
cycles à supports disjoints. C’est un corollaire immédiat de la formule de Burnside
(remarquer que f est laissée fixe par g si et seulement si f est constante sur le
support de chaque cycle de g).
Afin de répondre à des problèmes classiques de dénombrement, on introduit
une version à poids de cette formule. La fonction de poids est une application
113
Même question pour le degré 7 :
L[27]:=permgroup(7,{[[1,2,3,4,5,6,7]]}):
L[28]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[2,7],[3,6],[4,5]]}):
L[29]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[2,3,5],[4,7,6]]}):
L[30]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[2,4,3,7,5,6]]}):
L[31]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[2,3],[4,7]]}):
L[32]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[1,2,3]]}):
L[33]:=permgroup(7,{[[1,2,3,4,5,6,7]],[[1,2]]}):
Voyez-vous d’autres groupes que A n et S n ? Tester sur les deux derniers
exemples suivants :
L[34]:=permgroup(11,{[[1,2,3,4,5,6,7,8,9,10,11]],[[3,7,11,8],
[4,10,5,6]]}):
L[35]:=permgroup(12,{[[1,2,3,4,5,6,7,8,9,10,11]],
[[3,7,11,8],[4,10,5,6]],[[1,12],[2,11],[3,6],[4,8],[5,9],
[7,10]]}):
C’est un fait assez surprenant : les seuls groupes finis qui sont au moins
4-transitifs sont, à part les groupes A n et S n , les quatre groupes de Mathieu
M 11 , M 12 , M 23 et M 24 . Les deux premiers ont été notés L 34 et L 35 dans la
liste précédente ; les deux autres sont d’ordre 23 et 24, d’où des temps de
calcul très longs.
Énumérations de Polya
Soient A, B deux ensembles finis et G un groupe de permutations agissant sur
A. On considère l’action suivante de G sur l’ensemble B A des fonctions f : A → B :
un élément g agit par (g · f )(a) = f (g · a). La formule d’énumération de Polya
nous dit que l’ensemble O des orbites sous G de B A est de cardinal
N =
1
Card(G)
g∈G
Card(B)
cg ,
où c g désigne le nombre de cycles dans la décomposition de g en produits de
cycles à supports disjoints. C’est un corollaire immédiat de la formule de Burnside
(remarquer que f est laissée fixe par g si et seulement si f est constante sur le
support de chaque cycle de g).
Afin de répondre à des problèmes classiques de dénombrement, on introduit
une version à poids de cette formule. La fonction de poids est une application
113