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)