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