Théorème de dénombrement de Pólya

Modèle:Homon Le théorème de dénombrement de Pólya est un théorème de combinatoire sur le nombre d'orbites d'une action d'un groupe fini sur les « coloriages » d'un ensemble fini, dont la démonstration est une version « pondérée » de celle du lemme de Burnside. Il a été publié pour la première fois par Modèle:Lien en 1927Modèle:,. En 1937, George Pólya l'a redécouvert indépendamment et l'a beaucoup popularisé en l'appliquant à de nombreux problèmes de dénombrement, en particulier pour compter les composés chimiques.

Le théorème de dénombrement de Pólya peut aussi être intégré à la Modèle:Lien et à la Modèle:Lien.

Version simplifiée, sans poids

Soient X un ensemble fini et G un groupe de permutations de X (ou un groupe fini agissant sur X). On peut se représenter l'ensemble X comme un arrangement de perles et G comme un groupe de permutations que l'on choisit, sur ces perles. Par exemple, si X est un collier de n perles disposées en cercle, on peut choisir pour G le groupe cyclique CModèle:Ind ; si X est un « bracelet » de n perles (en un cercle que l'on peut retourner), alors on peut choisir le groupe diédral DModèle:Ind. Supposons de plus que C est un ensemble fini de t couleurs – les couleurs des perles – de telle sorte que [[Exponentiation ensembliste|l'ensemble CModèle:Exp des applications de X dans C]] est l'ensemble des coloriages de l'arrangement X. Alors, l'action de G sur l'ensemble X des arrangements induit une action sur l'ensemble CModèle:Exp des arrangements colorés, par (g.f)(x) = f(gModèle:Exp.x). Le lemme de Burnside permet de calculer le nombre d'orbites sous G d'arrangements colorés, en notant, pour chaque élément g du groupe, Modèle:Math(g) le nombre de cycles de la permutation de X associée, et en utilisant qu'un coloriage est fixe par g si et seulement s'il est constant sur chacun de ces cycles :

$|C^X/G|=\frac{1}{|G|}\sum _{g\in G}|\text{Fix}(g)|=\frac{1}{|G|}\sum _{g\in G}{t}^{j(g)}.$

On retrouvera ce résultat comme corollaire du théorème de dénombrement de Pólya.

Version complète, avec poids

Dans la version générale, à chaque couleur c est associée une variable yModèle:Ind (il peut y en avoir une infinité) et le « poids » w(f) d'un coloriage f, c'est-à-dire d'une application de l'ensemble fini X dans l'ensemble C des couleurs, est le monôme produit des yModèle:IndModèle:Exp, où chaque exposant nModèle:Ind est le nombre d'éléments de X de couleur c.

Tous les coloriages d'une même orbite sous G ont même poids, ce qui permet de définir l'inventaire des orbites de coloriages comme la série formelle suivante :

$W=\sum _{f\in Z}w(f)$

où Z est constitué d'exactement un coloriage (n'importe lequel) par orbite.

Le théorème de Pólya fait aussi intervenir le polynôme indicateur de cycles de l'action de G sur X :

$Z_G(t_1,t_2,\dots ,t_n)=\frac{1}{|G|}\sum _{g\in G}{t}_1^{j_1(g)}{t}_2^{j_2(g)}\dots t_n^{j_n(g)},$

où n est le cardinal de X et pour chaque Modèle:Math de 1 à n, Modèle:Math(g) est le nombre de Modèle:Math-cycles de la permutation de X associée à g.

L'énoncé du théorème est alors : Modèle:Bloc emphase

où, pour chaque Modèle:Math de 1 à n, Modèle:Math désigne la série formelle

$T_i=\sum _{c\in C}{y}_c^i.$

Lorsque l'ensemble C des couleurs est fini, de cardinal t, les séries formelles W et Modèle:Math sont simplement des polynômes et la « version simplifiée » ci-dessus s'en déduit par évaluation des deux membres, en remplaçant tous les yModèle:Ind par 1 :

$|C^X/G|=Z_G(t,t,\dots ,t)=\frac{1}{|G|}\sum _{g\in G}{t}^{j_1(g)+j_2(g)+\dots +j_n(g)}=\frac{1}{|G|}\sum _{g\in G}{t}^{j(g)}.$

Exemples

Graphes à 3 ou 4 sommets

Un graphe non orienté, sur m sommets fixés, peut être interprété comme une coloration de l'ensemble X des $n=(\genfrac{}{}{0ex}{}{m}{2})$ paires de sommets, par un ensemble de deux couleurs : par exemple Modèle:Nobr les arêtes noires étant celles présentes dans le graphe. Le théorème de Pólya peut être utilisé pour calculer le nombre de graphes sur ces m sommets à isomorphisme près, c'est-à-dire le nombre d'orbites des coloriages de X sous l'action du groupe symétrique G = SModèle:Ind, qui permute les sommets donc les paires de sommets.

Si un coloriage f correspond à un graphe à p arêtes, son poids w(f) est le monôme yModèle:IndModèle:Exp yModèle:IndModèle:Exp, que l'on peut représenter plus simplement par yModèle:Exp (par évaluation, en remplaçant yModèle:Ind par 1 et en notant y pour yModèle:Ind).

Pour m = 3, les 6 éléments du groupe G = SModèle:Ind agissent sur les n = 3 paires à colorier avec comme indicateur de cycles :

$Z_G(t_1,t_2,t_3)=\frac{t_1^3+3t_1{t}_2+2t_3}{6}$

donc d'après le théorème de Pólya, l'inventaire des orbites (vu comme polynôme en y par évaluation, comme les w(f) ci-dessus) est

$\begin{array}{cc}W& =Z_{S_3}(y+1,y^2+1,y^3+1)\\ & =\frac{(y+1{)}^3+3(y+1)(y^2+1)+2(y^3+1)}{6}\\ & =y^3+y^2+y+1,\end{array}$

donc pour chaque p de 0 à 3, il y a exactement une classe d'isomorphisme de graphes à 3 sommets et p arêtes.

De même, pour m = 4, G = SModèle:Ind agit sur les n = 6 paires avec comme indicateur :

$Z_G(t_1,t_2,t_3,t_4)=\frac{t_1^6+9t_1^2{t}_2^2+8t_3^2+6t_2{t}_4}{24},$

donc

$\begin{array}{cc}W& =Z_{S_4}(y+1,y^2+1,y^3+1,y^4+1)\\ & =\frac{(y+1{)}^6+9(y+1{)}^2(y^2+1{)}^2+8(y^3+1{)}^2+6(y^2+1)(y^4+1)}{24}\\ & =y^6+y^5+2y^4+3y^3+2y^2+y+1.\end{array}$

Il y a donc, parmi les classes d'isomorphismes de graphes sur 4 sommets :

• 1 classe de graphes à p arêtes pour p = 6, 5, 1, 0,
• 2 classes de graphes à p arêtes pour p = 4, 2,
• 3 classes de graphes à 3 arêtes.

Arbres enracinés ternaires

On cherche à compter les classes d'isomorphismes d'arbres (enracinés) Modèle:Lien, c'est-à-dire dans lesquels chaque nœud interne a exactement trois fils (des feuilles ou des sous-arbres). On considère pour cela la série génératrice

$T(y)=\sum t_n{y}^n$

où Modèle:Math est le nombre de classes d'arbres à Modèle:Math nœuds internes si Modèle:Math est un entier naturel (et Modèle:Math = 0 sinon).

$t_0=1$

car le seul arbre sans nœud interne est l'arbre trivial, c'est-à-dire réduit à sa racine.

La classe d'un arbre ternaire non trivial est une orbite de l'action de SModèle:Ind sur un ensemble coloré X à trois éléments (les trois fils de la racine), chaque couleur étant elle-même une classe d'isomorphisme d'arbres ternaires. L'[[Indicateur de cycles#Types d'actions|indicateur de cycle de SModèle:Ind pour son action naturelle]] est

$Z_{S_3}(t_1,t_2,t_3)=\frac{t_1^3+3t_1{t}_2+2t_3}{6}.$

La formule de Pólya donne, après évaluation en remplaçant chaque yModèle:Ind par yModèle:Exp où n est le nombre de nœuds internes des arbres de la classe c, la formule récursive

$T(y)=1+y\frac{T(y{)}^3+3T(y)T(y^2)+2T(y^3)}{6}$

qui permet de calculer les Modèle:Math par récurrence :

$t_{n+1}=\frac{1}{6}(\sum _{a+b+c=n}{t}_a{t}_b{t}_c+3\sum _{a+2b=n}{t}_a{t}_b+2\sum _{3a=n}{t}_a).$

Les premières valeurs de Modèle:Math sont

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (Modèle:OEIS).

Cubes colorés

De combien de façons peut-on colorier les 6 faces d'un cube avec t couleurs, à rotation près ? L'indicateur de cycles du groupe des rotations du cube est

$Z_G(t_1,t_2,t_3,t_4)=\frac{t_1^6+6t_1^2{t}_4+3t_1^2{t}_2^2+8t_3^2+6t_2^3}{24}.$

Il y a donc

$Z_G(t,t,t,t)=\frac{t^6+3t^4+12t^3+8t^2}{24}$

coloriages.

Démonstration

La preuve commence, comme pour le lemme de Burnside, par une interversion dans une double sommation puis une partition par orbites :

$\begin{array}{cc}\sum _{g\in G}\sum _{f\in \text{Fix}(g)}w(f)& =\sum _{f\in C^X}\sum _{g\in S{t}_f}w(f)\\ & =\sum _{f\in C^X}|S{t}_f|w(f)\\ & =\sum _{f\in Z}\sum _{h\in Gf}|S{t}_h|w(h)\\ & =\sum _{f\in Z}\sum _{h\in Gf}\frac{|G|}{|Gf|}w(f)\\ & =|G|\sum _{f\in Z}w(f),\end{array}$

ce qui fournit l'égalité

$W=\frac{1}{|G|}\sum _{g\in G}\sum _{f\in \text{Fix}(g)}w(f).$

Or pour un élément g fixé dans G, dont les cycles XModèle:Ind, … , XModèle:Ind partitionnent X,

$\sum _{f\in \text{Fix}(g)}w(f)=\sum _{c_1,\dots ,c_k\in C}{y}_{c_1}^{|X_1|}\dots y_{c_k}^{|X_k|}=\left(\sum _{c\in C}{y}_c^{|X_1|}\right)\dots \left(\sum _{c\in C}{y}_c^{|X_k|}\right)=\prod _{i=1}^n{T}_i^{j_i(g)},$

où Modèle:Math(g) désigne, à nouveau, le nombre de cycles de g de longueur Modèle:Math.

En prenant la moyenne sur G on obtient donc bien

$W=\frac{1}{|G|}\sum _{g\in G}{T}_1^{j_1(g)}\dots T_n^{j_n(g)}=Z_G(T_1,\dots ,T_n).$

Voir aussi

Article connexe

Rubik's Cube

Liens externes

• Thomas Chomette, « Les colliers de G.Polyà », CultureMATH
• Modèle:En Hector Zenil et Oleksandr Pavlyk, « Applying the Pólya-Burnside Enumeration Theorem », Wolfram Demonstrations Project
• Modèle:MathWorld
• Modèle:En Marko Riedel, Pólya's enumeration theorem and the symbolic method.