Previous: TP: rudiments de cryptographieTP: rudiments de cryptographie Up: Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'OrsayOption Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay Next: TP: Algorithme de WiedemannTP: Algorithme de Wiedemann
Document disponible au format: PDF, Text, LaTeX, LyX.

Groupe symétrique et groupes de permutations



Définition 1   Soit E un ensemble. On appelle groupe symétrique de E l'ensemble des applications bijectives de E sur E muni de la composition d'applications. On le note Sn.
Un cas particulier courant est le cas où E est l'ensemble fini {1,...,n}, n étant un entier naturel strictement positif; on note alors SE le groupe symétrique de cet ensemble. Les éléments de SE sont appelés permutations et Snest appelé groupe des permutations d'ordre n, ou groupe symétrique d'ordre n.

Maintenant, si est un ensemble E a n éléments, alors on sait que SEest isomorphe à Sn. En conséquence, il suffit de connaitre les propriétés du groupe Sn pour en déduire celles du groupe SE.

Proposition 2   Le groupe Snest d'ordre n!.
Quelques permutations particulières: Représentation des permutations:

1  Produit de deux permutations



Proposition 1   Dans un produit στ, on peut considérer que τ permute les positions de σ, et que σpermute les valeurs de τ.

Deux cycles disjoints commutent.

Toute permutation se décompose de manière unique comme un produit de cycles (à l'ordre près).
Le type cyclique d'une permutation est la partition de n donnée par les longueurs de ses cycles.

Exercice 1   Comment calculer l'inverse d'une permutation? Complexité?

Complexité du calcul de la décomposition en cycles? du type cyclique?

Que se passe-il lorsque l'on conjugue une permutation τ donnée sous forme de décomposition en cycle par une permutation (στσ−1).

Quelles sont les classes de conjugaisons?


2  Générateurs du groupe symétrique



Proposition 1   Snest engendré par les cycles.

Sn est engendré par les transpositions.

Sn est engendré par les transpositions élémentaires.

Sn est engendré par la transposition (1,2) et le cycle (1,...,n).


2.1  Présentation par générateurs et relations?

Générateurs: τi=(i,i+1).

Relations: Le permutohèdre:



Comptage des permutations par niveau et q-factorielle.

3  Sous-groupes du groupe symétrique (groupes de permutations)

Exemples: groupe trivial, groupes des symétries d'un polyhèdre, groupe cyclique Cn, groupe Dihedral Dn, groupe alterné An.

3.1  Applications:

3.2  Systèmes générateurs forts:

Problème: Un groupe de permutation est typiquement très gros. Exemple: Sn engendré par les transpositions.

Idée: On considère la tour de groupes { id}=G0⊂ G1⊂⋯⊂ Gn=G, où Gi est le sous groupe des éléments de G qui fixent {i+1,...,n}. Pour décrire G, il suffit alors de décrire chacune des inclusions. Un système générateur fort est composé des représentants des cosets de Gi/Gi−1 pour chaque i.

Définition de base B. g dans le groupe est caractérisé par g(b) pour b dans la base.

Exercice 2   Vérifier que {5,4,3}est une base pour A5.

Donner une borne sur la taille d'un système générateur fort. Comparer avec la taille du groupe.
Algorithme de Schreier-Sims.

Exercice 3   Utiliser l'algorithme de Schreier-Sims pour retrouver un SGS pour le groupe des symétries du [5]cube, sachant qu'il est engendré par (0,1,3,7,6,4)(2,5) et (0,1,3,2)(4,5,7,6).
La connaissance d'un système générateur fort permet de résoudre les problèmes ci-dessus. On peut calculer incrémentalement et efficacement un système générateur fort à partir d'un système générateur quelconque.

Algorithmes dérivés de complexité quasi-linéaire. On peut manipuler des groupes de permutations d'ordre plusieurs centaines de miliers.

Exemple avec xgap:
 GraphicSubgroupLattice(SymmetricGroup(3));

4  TP: Énumération de Pólya

La formule d'énumération de Pólya permet de dénombrer des objets discrets considérés modulo certaines symétries. Un des cas les plus simples concerne le dénombrement des colliers à n perles rouges ou bleues, considérés à une rotation près. Par exemple, voilà trois colliers à n=8 perles. Les deux premiers sont identiques, mais pas le troisième (on pourrait autoriser le retournement, mais on ne le fera pas dans un premier temps pour simplifier).



Nous allons énoncer cette formule dans le cas général, en l'illustrant au fur et à mesure sur cet exemple.

Mais d'abord un exercice préliminaire:

Exercice 4   Vérifier, en les dessinant tous à la main, qu'il y a 8 colliers à 5 perles rouges ou bleues. Préciser combien il y en a avec 0,1,2,... perles rouges.
Soit E un ensemble fini (ici E:={1,...,5}), et F un autre ensemble (ici F:={Rouge,Bleu}), typiquement fini ou dénombrable. Les objets discrets qui nous intéressent sont les fonctions de E dans F (ici les colliers où on a fixé la première perle). Pour modéliser des symétries sur E (ici on veut considérer que deux colliers qui sont identiques à rotation près sont identiques), on introduit un sous-groupe G du groupe symétrique SE (ici le groupe cyclique G:=C5=⟨(1,...,5)⟩). Ce groupe agit sur l'ensemble des fonctions FE par σ⋅ f:=f∘σ−1, où σ∈ G et f∈ FE. Deux fonctions f et g sont dites isomorphes s'il existe une permutation σ dans G telle que f=σ.g (ici, deux colliers sont isomorphes s'ils sont identiques à rotation près).

Notre objectif est de compter le nombres de classes d'isomorphies. Cela peut être fait via le Lemme de Burnside http://en.wikipedia.org/wiki/Burnside's_lemma. Nous allons directement énoncer une version raffinée de cette formule, due à Pólya, afin de compter les colliers selon leur nombre de perles rouges. Pour cela, nous allons associer à chaque élément c de F un poids w(c) multiplicatif, et associer à chaque fonction f dans FE le poids w(f)=Πe∈ Ew(f(e)). Ce poids est constant sur une classe d'isomorphie f, ce qui permet de définir w(f). Considérons maintenant la somme Σfw(f) des poids de toutes les classes d'isomorphie. Si w(c)=1 pour tout c dans F, cette somme donne le nombre de classes d'isomorphies, c'est-à-dire 8 dans notre exemple. Si w(Rouge)=1 et w(Bleu)=q, on obtient:

 
Σ
f
w ⎛
⎝
f
⎞
⎠		 =1+q+2q2+2q3+q4+q5,


qui indique en particulier qu'il y a deux colliers avec respectivement deux ou trois perles rouges, et un collier avec respectivement une, deux, quatre, ou cinq perles rouges. On notera que le rôle joué par les éléments de F (ici les couleurs rouges et bleues) sont parfaitement symétriques; cela rend relativement naturelle l'introduction des polynômes symétriques suivantes:

pk:=
 
Σ
c∈ F
w(c)k


qui énumèrent les objets de F répétés k fois.

Nous pouvons maintenant énoncer la fameuse formule de Pólya. La seule information dont l'on a besoin sur le groupe est en fait le type cyclique l(c) de chacun de ses éléments:

 
Σ
f
w ⎛
⎝
f
⎞
⎠		 =
1
| G |
 
Σ
σ∈ G
 
Π
k∈ l(σ)
pk


Proof. À faire ...


Indication pour l'ensemble des exercices: MuPAD et Maple contiennent un certain nombre de fonctions prédéfinies pour manipuler les permutations; n'hésitez pas à les réutiliser pour gagner du temps. Pour MuPAD, voir ?combinat::permutations et ?Dom::PermutationGroup (en fait, pour ceux qui savent chercher, la formule de Pólya est directement implantée). Pour Maple, voir ?permutations, ?group.

Exercice 5   Écrire une fonction p(k,poids) qui calcule pk à partir de la liste des poids des éléments de F.

On pourra, au choix, représenter une permutation par une liste (comme [2,3,4,5,1]), ou par la liste de ces cycles (ici [[1,2,3,4,5]]).

Écrire une fonction typeCyclique(sigma) qui calcule le type cyclique d'une permutation sigma.

Lister les permutations de C5.

Tester la formule ci-dessus pour poids=[1,1], et poids=[1,q].

Compter le nombre de colliers bicolores à 10 perles selon leur nombre de perles rouges.

Compter le nombre de colliers à 10 perles de trois couleurs.


Exercice 6   Variante sur l'exercice précédent: on veut maintenant aussi considérer comme identiques deux colliers qui ne diffèrent que d'un retournement. Compter le nombre de tels colliers à 3 perles bleues et 2 perles rouges.

Indication: considérer le groupe dihédral D5 des symétries du pentagone. Il est engendré par le cycle (1,2,3,4,5) et la symétrie axiale (1)(2,5)(3,4).

On pourra soit lister à la main les éléments de D5, soit écrire ou réutiliser trois fonctions:


Exercice 7   Compter le nombre de cubes réèlements différents que l'on peut obtenir en peignant leurs faces en trois couleurs.

Indication: numéroter les faces, et considérer le groupe des symétries du cube. Puis donner les générateurs de ce groupe sous forme de produit de cycles, et utiliser les fonctions ci-dessus pour lister tous les éléments du groupe.


Exercice 8   Construire à la main les 11 graphes simples non orientés sur 4 sommets non étiquetés. Puis recalculer leur nombre grâce à la formule de Pólya. Compter le nombre de graphes simples à 5,6,7,8,9,10,… sommets.

Indication: un graphe simple non orienté sur n sommets peut être considéré comme une fonction allant de l'ensemble des paires { i,j} de {1,...,n} dans {0,1} (1 s'il y a une arête entre i et j, et 0 sinon).

Dans un premier temps, pour n≤6,7, on peut numéroter les paires { i,j} de 1 à (
n
2
). Le groupe G est le groupe des permutation des arêtes induites par les n! permutations des sommets dans Sn. On peut donc rechercher quelles permutations des arêtes sont induites par l'échange des sommets 1 et 2 et par la permutation cyclique (1,2,3,...,n) des sommets; le groupe G est alors engendré par ces deux permutations, et l'on peut poursuivre comme dans l'exercice précédent.

Pour aller plus loin, on peut regrouper dans la formule de Pólya les permutations ayant le même type cyclique. Pour cela, il faut pouvoir compter le nombre de permutations dans Sn ayant un type cyclique donné, et pouvoir calculer le type cyclique d'une permutation des arêtes dans G, connaissant le type cyclique de la permutation des sommets correspondant dans Sn.


5  TP: Systèmes fort de générateurs



Exercice 9   Construire à la main un système générateur fort pour le groupe trivial Idn, le groupe cyclique C4, le groupe alterné A4, le groupe dihédral D8, et pour le groupe des symétries du cube.


Exercice 10   En s'inspirant des algorithmes 6.6 et 6.8 de [5], implanter des procédures qui, étant donné un système fort de générateurs d'un groupe G, permettent de:
  1. Calculer la taille du groupe
  2. Calculer la liste des éléments du groupe
  3. Tester si une permutation donnée appartient au groupe
Vérifier au fur et à mesure vos procédures sur les exemples ci-dessus.


Exercice 11   Implanter l'algorithme 6.9 de [5] permettant de calculer un système fort de générateurs d'un groupe de permutation donné par des générateurs quelconques. Vérifier votre implantation sur les exemples ci-dessus.


Exercice 12   Modifier la procédure de listage des éléments du groupe pour qu'elle applique une fonction quelconque donnée en paramètre sur chacun des éléments du groupe sans construire explicitement la liste des éléments du groupe (comme dans l'algorithme RUN()).

Utiliser cette procédure pour calculer la statistique des types cycliques des éléments du groupe.

Calculer le nombre de graphes à isomorphie près sur 5, 6, 7, 8? sommets.

Un multigraphe est un graphe dans lequel il peut y avoir un nombre quelconque d'arêtes entre deux sommets. Calculer la série génératrice par nombre d'arêtes des graphes sur 4,5,6 sommets. Indication: ici, F est composé des entiers {0,1,2,...} auxquels on peut attribuer les poids {1,q,q2,...}; on peut alors mettre pk:=1k+qk+q2k+⋯ sous la forme pk=1/1−qk.

References

[1]
The Symmetric Group, Bruce Sagan

[2]
The Art of Computer Programming, Sorting algorithms, Donald E. Knuth

[3]
http://en.wikipedia.org/wiki/Symmetric_group

[4]
Permutation Group Algorithms, Ákos Seress http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0511060165

[5]
Combinatorial Algorithms: Generation, Enumeration, and search, Donald L. Kreher et Douglas Stinson http://www.math.mtu.edu/~kreher/cages.html

[6]
Le système de calcul formel GAP http://www-groups.dcs.st-and.ac.uk/~gap/

[7]
Le système de calcul formel Magma http://magma.maths.usyd.edu.au/magma/
Valid HTML 4.0! Previous: TP: rudiments de cryptographieTP: rudiments de cryptographie Up: Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'OrsayOption Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay Next: TP: Algorithme de WiedemannTP: Algorithme de Wiedemann
Groupe symétrique et groupes de permutations / Option Algèbre et Calcul Formel / Nicolas M. Thiéry
Dernière modification: Jeu 24 Mai 2007 9:53:56