TP

Contenu

TP#

Consignes / Instructions

Choisissez à la carte parmi les deux thèmes ci-dessous (Énumération de Pólya et Systèmes générateurs forts), et préparez une mini présentation de quelques minutes.

Vous déposerez sur cirrus vos présentations.

Énumération de Pólya#

Le fichier groupe_symetrique.py vous donne un point de départ pour les différentes fonctions que vous aurez à implanter dans ce TP. Le fichier groupe_symetrique_correction.py contient une correction partielle.

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).

Note

Pour refabriquer un de ces dessins, on peut utiliser:

G = graphs.CycleGraph(8)

G.plot(vertex_colors={"red": [0,2,3,4,5], "blue": [1,6,7]})

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

Exercice préliminaire

Vérifier, en les dessinant tous à la main, qu’il y a $8$ colliers à $n=5$ perles rouges ou bleues. Préciser combien d’entre eux ont $0,1,2,\dots$ perles rouges.

Comparer vos colliers avec les listes produites par IntegerVectorsModPermutationGroup

C5 = CyclicPermutationGroup(5)

I = IntegerVectorsModPermutationGroup(C5, max_part=1)
I.list()

I.cardinality()

I = IntegerVectorsModPermutationGroup(CyclicPermutationGroup(5), max_part=1, sum=3)
I.list()

I.cardinality()

Soit $E$ un ensemble fini (ici $E:=\left\{ 1,\dots,5\right\}$), et $F$ un autre ensemble (ici $F:=\left\{ Rouge,Bleu\right\}$), 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 $S_E$ (ici le groupe cyclique $G:=C_{5}=\left\langle (1,\dots,5)\right\rangle$). Ce groupe agit sur l’ensemble des fonctions $F^{E}$ par $\sigma\cdot f:=f\circ\sigma^{-1}$, où $\sigma\in G$ et $f\in F^{E}$. Deux fonctions $f$ et $g$ sont dites isomorphes s’il existe une permutation $\sigma$ dans $G$ telle que $f=\sigma.g$ (ici, deux colliers sont isomorphes s’ils sont identiques à rotation près).

Notre objectif est de compter le nombres de classes d’isomorphie. Cela peut être fait via le Lemme de Burnside. 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 $F^{E}$ le poids $w\left(f\right)=\prod_{e\in E}w(f(e))$. Ce poids est constant sur une classe d’isomorphie $\overline{f}$, ce qui permet de définir $w\left(\overline{f}\right)$. Considérons maintenant la somme $\sum_{\overline{f}}w\left(\overline{f}\right)$ des poids de toutes les classes d’isomorphie. Si $w\left(c\right)=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:

\[ \sum_{\overline{f}}w\left(\overline{f}\right) = 1+q+2q^{2}+2q^{3}+q^{4}+q^{5}, \]

qui indique en particulier qu’il y a deux colliers avec respectivement deux ou trois perles rouges, et un collier avec respectivement zéro, une, 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:

\[ p_{k} := \sum_{c\in 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:

\[ \sum_{\overline{f}}w\left(\overline{f}\right) = \frac{1}{\left|G\right|}\sum_{\sigma\in G}\; \prod_{k\in l(\sigma)}p_{k} \]

Précision: dans le produit $\prod_{k\in l(\sigma)} p_k$, on tient compte des cycles de longueur 1 ainsi que des répétitions: si $\sigma$ a trois cycles de longueur $k$, alors $p_k$ est élevé à la puissance trois.

Indication pour l’ensemble des exercices

Sage (comme MuPAD ou Maple) contient un certain nombre de fonctions prédéfinies pour manipuler les groupes de permutations (voir PermutationGroup()), dont la formule de Pólya; à vous de choisir ce que vous réimplantez ou pas selon ce que vous avez le plus besoin de comprendre.

Exercice: comptage de colliers#

Écrire une fonction p(k,poids) qui calcule $p_{k}$ à partir de la liste des poids des éléments de $F$.
La formule de Pólya requiers de calculer le type cyclique d’une permutation.
- Option 1: (Sage >= 7.5) utilisez directement la méthode sigma.cycle_type() et passer directement à la suite.
- Option 2: Implanter une fonction type_cyclique(sigma) qui calcule le type cyclique d’une permutation $sigma$ à partir de la méthode cycle_tuples() des permutations.
- Option 3: Implanter l’algorithme de recherche des cycles, mais en stockant uniquement leur taille.
  Indications:

G = DihedralGroup(10)
g = G.an_element(); g

g.parent().domain()

 et utiliser un ensemble ({meth}`set`) pour noter les éléments
 du domaine déjà croisés.

Lister les permutations de $C_{5}$.
Écrire la formule ci-dessus pour poids=[1,1].
Écrire une fonction Polya(G, poids) implantant la formule ci-dessus pour un groupe $G$ et des poids quelconques.
Compter le nombre de colliers bicolores à dix perles selon leur nombre de perles rouges.
Compter le nombre de colliers à dix perles de trois couleurs.

Exercice: comptage de colliers (suite)#

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 à trois perles bleues et deux perles rouges.

Indication: considérer le groupe diédral $D_{5}$ des symétries du pentagone.

Exercice: colorations du cube#

Compter le nombre de cubes que l’on peut obtenir en peignant leurs faces en au plus trois couleurs.

Indications:

Numéroter les faces, considérer le groupe des isométries positives du cube, comme groupe de permutations de ses faces.
Déterminer les générateurs de ce groupe (par exemple sous forme de produit de cycles).
Construire le groupe dans Sage en utilisant PermutationGroup().
Poursuivre comme ci-dessus.

Exercice: énumération des graphes (plus avancé)#

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,\ldots$ sommets.

Indications

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,\dots,n\}$ dans $\{0,1\}$ ($1$ s’il y a une arête entre $i$ et $j$, et $0$ sinon).
On numérote les paires $\{i,j\}$ de $1$ à $\binom{n}{2}$. Le groupe $G$ est le groupe des permutation des paires induites par les $n!$ permutations des sommets dans $S_n$. On peut donc rechercher quelles permutations des paires sont induites par l’échange des sommets $1$ et $2$ et par la permutation cyclique $(1,2,3,\dots,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.
Au delà de $n=7$ le calcul devient long à cause de la somme sur le groupe. 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 $S_n$ 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 $S_n$.

Exercice: énumération des multigraphes (plus avancé)#

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 $\left\{0,1,2,\dots\right\}$ auxquels on peut attribuer les poids $\left\{ 1,q,q^{2},\dots\right\}$; on peut alors mettre $p_{k}:=1^{k}+q^{k}+q^{2k}+\cdots$ sous la forme $p_{k}=\frac{1}{1-q^{k}}$.

Exercice (plus avancé)#

Consulter la documentation et le code de la méthode {meth}`cycle_index$ des groupes de permutations. C’est l’un de vos prédécesseurs qui l’a implantée!
Utilisez-la pour recalculer les exemples précédents.
Est-elle plus ou moins performante que votre implantation?
Comment fonctionne-t-elle?

Systèmes générateurs forts#

On supposera pour simplifier que l’on travaille avec un groupe de permutations $G$ de $\{1,\dots,n\}$ et que la base est $n,n-1,\dots,1$.

On représentera un système générateur fort de $G$ sous la forme d’une liste $l$ telle que $l[i-1]$ contient des représentants des classes de $G_i/G_{i-1}$. Ces représentants seront représenté sous la forme d’un dictionnaire associant à chaque élément $y$ de l’orbite de $i$ sous $G_i$ une permutation $\sigma_{i,y}$ de $G_i$ telle que $\sigma_{i,y}(i)=y$.

Pour le groupe symétrique $S_3$, cela donnerait:

S = SymmetricGroup(3)
sgf = [ {1: S.one()},
        {1: S([(1,2)]), 2: S.one()},
        {1: S([(1,3)]), 2: S([(2,3)]), 3: S.one()} ]

Exercice

Construisez dans Sage les systèmes générateurs forts des groupes $C_4$, $D_4$, $A_4$, et du groupe des symétries du cube.

Comparez avec le système générateur fort calculé par Sage (en fait GAP).

Exercice: Utilisation des systèmes générateurs forts

Implanter des procédures qui, étant donné un système générateur fort d’un groupe $G$, permettent de:

Calculer la taille du groupe.
Calculer la liste des éléments du groupe.
Indication: récursion
Variante (avancée): implanter un itérateur
Tester si une permutation donnée appartient au groupe.

Exercice: Calcul des systèmes générateurs forts

Implanter l’algorithme de Schreier-Sims pour calculer un système générateur fort d’un groupe de permutations donné par des générateurs.

Indication

Implanter d’abord une méthode transversal(generateurs, i) qui calcule l’orbite de $i$ sous l’action des générateurs avec, pour chaque élément $j$ de l’orbite, une permutation envoyant $i$ sur $j$.