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

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Théorème 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[modifier | modifier le code]

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, alors G est par définition le groupe cyclique Cn, alors que si X est un « bracelet » de n perles (en un cercle que l'on peut retourner), alors G est par définition le groupe diédral Dn. Supposons de plus que C est un ensemble fini de t couleurs – les couleurs des perles – de telle sorte que l'ensemble CX 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 CX 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|=\frac1{|G|}\sum_{g\in G}|\text{Fix}(g)|=\frac1{|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[modifier | modifier le code]

Dans la version générale, à chaque couleur c est associée une variable yc (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 ycnc, où chaque exposant nc 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)

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)=\frac1{|G|}\sum_{g\in G}t_1^{j_1(g)}t_2^{j_2(g)}\ldots t_n^{j_n(g)},

n est le cardinal de X et pour chaque i de 1 à n, ji(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, Ti 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 Ti 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 yc par 1 :

|C^X/G|=Z_G(t,t,\ldots,t)=\frac1{|G|}\sum_{g\in G}t^{j_1(g)+j_2(g)+\ldots+j_n(g)}=\frac1{|G|}\sum_{g\in G}t^{j(g)}.

Exemples[modifier | modifier le code]

Graphes à 3 ou 4 sommets[modifier | modifier le code]

Un graphe non orienté, sur m sommets fixés, peut être interprété comme une coloration de l'ensemble X des n=\binom m2 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 = Sm, 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 ynoirp yblancn – p, que l'on peut représenter plus simplement par yp (par évaluation, en remplaçant yblanc par 1 et en notant y pour ynoir).

Pour m = 3, les 6 éléments du groupe G = S3 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_1t_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{align}
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{align}

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 = S4 agit sur les n = 6 paires avec comme indicateur :


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

donc

\begin{align}
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{align}

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[modifier | modifier le code]

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_ny^n

tn est le nombre de classes d'arbres à n nœuds internes si n est un entier naturel (et tn = 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 S3 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 S3 pour son action naturelle est

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

La formule de Pólya donne, après évaluation en remplaçant chaque yc par ynn 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 tn par récurrence :

t_{n+1}=\frac16\left(\sum_{a+b+c=n}t_at_bt_c+3\sum_{a+2b=n}t_at_b+2\sum_{3a=n}t_a \right).

Les premières valeurs de tn sont

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (suite A000598 de l'OEIS).

Cubes colorés[modifier | modifier le code]

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 + 6 t_1^2 t_4 + 3 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2^3}{24}.

Il y a donc

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

coloriages.

Démonstration[modifier | modifier le code]

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

\begin{align}
\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{align}

ce qui fournit l'égalité

W=\frac1{|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 X1, … , Xk 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}^nT_i^{j_i(g)},

ji(g) désigne, à nouveau, le nombre de cycles de g de longueur i.

En prenant la moyenne sur G on obtient donc bien

W=\frac1{|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[modifier | modifier le code]

(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)

  1. (en) J. Howard Redfield, « The Theory of Group-Reduced Distributions », Amer. J. Math., vol. 49, no 3,‎ 1927, p. 433-455 (DOI 10.2307/2370675)
  2. (en) Frank Harary (en) et Ed Palmer, « The Enumeration Methods of Redfield », Amer. J. Math., vol. 89, no 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, no 1,‎ 1937, p. 145-254 (DOI 10.1007/BF02546665),
    trad. (en) G. Pólya et R. C. Read (en), Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer,‎ 1987 (ISBN 978-0-387-96413-3)

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Rubik's Cube

Liens externes[modifier | modifier le code]