Accueil🇫🇷Chercher

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 Cn ; si X est un « bracelet » de n perles (en un cercle que l'on peut retourner), alors on peut choisir 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 :

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 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 :

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 :

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 :

où, pour chaque i de 1 à n, Ti désigne la série formelle

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 :

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 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 :

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

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 :

donc

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

tn est le nombre de classes d'arbres à n nœuds internes si n est un entier naturel (et tn = 0 sinon).

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

La formule de Pólya donne, après évaluation en remplaçant chaque yc par yn n est le nombre de nœuds internes des arbres de la classe c, la formule récursive

qui permet de calculer les tn par récurrence :

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

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

Il y a donc

coloriages.

Démonstration

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

ce qui fournit l'égalité

Or pour un élément g fixé dans G, dont les cycles X1, … , Xk partitionnent X,

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

En prenant la moyenne sur G on obtient donc bien

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).
  1. (en) J. Howard Redfield, « The Theory of Group-Reduced Distributions », Amer. J. Math., vol. 49, no 3, , p. 433-455 (DOI 10.2307/2370675)
  2. (en) Frank Harary et Ed Palmer, « The Enumeration Methods of Redfield », Amer. J. Math., vol. 89, no 2, , 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, , 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, (ISBN 978-0-387-96413-3)

Voir aussi

Article connexe

Rubik's Cube

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.