Théorème de dénombrement de Pólya
# 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^,.$ 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 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^{nc},$ 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_3$ 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_4$ 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_3$ 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_3$ 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^n$ 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

### 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_1,$ … , $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}).$

