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

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 John Howard Redfield (en) en 1927[1]^,[2]. En 1937, George Pólya l'a redécouvert indépendamment[3] 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 combinatoire symbolique (en) et à la théorie combinatoire des espèces de structures (en).

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 C_n ; si X est un « bracelet » de n perles (en un cercle que l'on peut retourner), alors on peut choisir le groupe diédral D_n. Supposons de plus que C est un ensemble fini de t couleurs – les couleurs des perles – de telle sorte que l'ensemble C^X 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 C^X des arrangements colorés, par (g.f)(x) = f(g^–1.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, $j$ (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 y_c (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 y_c^n_c, où chaque exposant n_c 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},\ldots ,t_{n})={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{j_{1}(g)}t_{2}^{j_{2}(g)}\ldots t_{n}^{j_{n}(g)},

où n est le cardinal de X et pour chaque $i$ de 1 à n, $j i$ (g) est le nombre de $i$ -cycles de la permutation de X associée à g.

L'énoncé du théorème est alors :

W=Z_{G}\left(T_{1},\ldots ,T_{n}\right)

où, pour chaque $i$ de 1 à n, $T i$ 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 $T i$ 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 y_c par 1 :

|C^{X}/G|=Z_{G}(t,t,\ldots ,t)={\frac {1}{|G|}}\sum _{g\in G}t^{j_{1}(g)+j_{2}(g)+\ldots +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={\binom {m}{2}}$ paires de sommets, par un ensemble de deux couleurs : par exemple C = { noir, blanc }, 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 = S_m, 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 y_noir^p y_blanc^{n – p}, que l'on peut représenter plus simplement par y^p (par évaluation, en remplaçant y_blanc par 1 et en notant y pour y_noir).

Pour m = 3, les 6 éléments du groupe G = S₃ 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{aligned}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{aligned}}

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 = S₄ 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{aligned}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{aligned}}

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) ternaires (en), 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ù $t n$ est le nombre de classes d'arbres à $n$ nœuds internes si $n$ est un entier naturel (et $t n$ = 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 S₃ 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 cycle de S₃ 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 y_c par yⁿ 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 $t n$ par récurrence :

t_{n+1}={\frac {1}{6}}\left(\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}\right).

Les premières valeurs de $t n$ sont

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (suite A000598 de l'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{aligned}\sum _{g\in G}\sum _{f\in {\text{Fix}}(g)}w(f)&=\sum _{f\in C^{X}}\sum _{g\in St_{f}}w(f)\\&=\sum _{f\in C^{X}}|St_{f}|w(f)\\&=\sum _{f\in Z}\sum _{h\in Gf}|St_{h}|w(h)\\&=\sum _{f\in Z}\sum _{h\in Gf}{\frac {|G|}{|Gf|}}w(f)\\&=|G|\sum _{f\in Z}w(f),\end{aligned}}

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 X₁, … , X_k partitionnent X,

\sum _{f\in {\text{Fix}}(g)}w(f)=\sum _{c_{1},\ldots ,c_{k}\in C}y_{c_{1}}^{|X_{1}|}\ldots y_{c_{k}}^{|X_{k}|}=\left(\sum _{c\in C}y_{c}^{|X_{1}|}\right)\ldots \left(\sum _{c\in C}y_{c}^{|X_{k}|}\right)=\prod _{i=1}^{n}T_{i}^{j_{i}(g)},

où $j i$ (g) désigne, à nouveau, le nombre de cycles de g de longueur $i$ .

En prenant la moyenne sur G on obtient donc bien

W={\frac {1}{|G|}}\sum _{g\in G}T_{1}^{j_{1}(g)}\ldots T_{n}^{j_{n}(g)}=Z_{G}(T_{1},\ldots ,T_{n}).

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Pólya enumeration theorem » (voir la liste des auteurs).

(en) J. Howard Redfield, « The Theory of Group-Reduced Distributions », Amer. J. Math., vol. 49, n^o 3,‎ 1927, p. 433-455 (DOI 10.2307/2370675)
(en) Frank Harary et Ed Palmer, « The Enumeration Methods of Redfield », Amer. J. Math., vol. 89, n^o 2,‎ 1967, p. 373-384 (DOI 10.2307/2373127)
(de) G. Pólya, « Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen », Acta Math., vol. 68, n^o 1,‎ 1937, p. 145-254 (DOI 10.1007/BF02546665),
trad. (en) G. Pólya et R. C. Read, Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer, 1987 (ISBN 978-0-387-96413-3)

Voir aussi

Article connexe

Rubik's Cube

Liens externes

Thomas Chomette, « Les colliers de G.Polyà », CultureMATH
(en) Hector Zenil et Oleksandr Pavlyk, « Applying the Pólya-Burnside Enumeration Theorem », Wolfram Demonstrations Project
(en) Eric W. Weisstein, « Polya Enumeration Theorem », sur MathWorld
(en) Marko Riedel, Pólya's enumeration theorem and the symbolic method.

Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) J. Howard Redfield, « The Theory of Group-Reduced Distributions », Amer. J. Math., vol. 49, n^o 3,‎ 1927, p. 433-455 (DOI 10.2307/2370675)

[2] (en) Frank Harary et Ed Palmer, « The Enumeration Methods of Redfield », Amer. J. Math., vol. 89, n^o 2,‎ 1967, p. 373-384 (DOI 10.2307/2373127)

[3] (de) G. Pólya, « Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen », Acta Math., vol. 68, n^o 1,‎ 1937, p. 145-254 (DOI 10.1007/BF02546665),
trad. (en) G. Pólya et R. C. Read, Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer, 1987 (ISBN 978-0-387-96413-3)