Un théorème qui compte les colorations ou configurations combinatoires non équivalentes sous un groupe de permutations fini en substituant des variables de comptage de couleurs dans le polynôme indice de cycles du groupe.

Principe

Encoder la décomposition cyclique de chaque élément du groupe en un monôme formel (l'indice de cycles) ; substituer des sommes ou des polynômes représentant les choix de couleurs pour obtenir une fonction génératrice dont les coefficients comptent les configurations distinctes à action de groupe près.

Démonstration

Pour compter les colorations distinctes d'un collier à n perles sous rotation, calculer l'indice de cycles du groupe de rotation et substituer x_k = nombre de choix de couleur pour un cycle de longueur k, ce qui donne le nombre de colorations non équivalentes.

Mauvaise application

Utiliser la substitution de l'indice de cycles avec des poids ou dépendances de couleur qui violent l'hypothèse d'attribution indépendante de couleur aux positions cycliques, ou appliquer le théorème quand l'action ne se ramène pas à une permutation de positions décrite par des cycles.

Conséquence

Produit des fonctions génératrices en forme fermée ou des décomptes explicites pour des classes combinatoires symétriques, prend en charge les colorations pondérées et le dénombrement de motifs de type chimique, et généralise la moyenne de Burnside en un outil algébrique puissant.

Inversion

Vu inversement, l'expansion des coefficients de l'indice de cycles substitué récupère les contributions de points fixes pour chaque élément du groupe — le lemme de Burnside apparaît comme une spécialisation de Pólya avec des substitutions simples.

Limite

Nécessite un groupe de permutations fini agissant sur un ensemble fini de positions et l'indépendance des choix de couleur sur les cycles ; il n'adresse pas directement les symétries continues ou les actions avec contraintes dépendant de la position sans adaptation.

Tension sémantique

Tension entre les techniques algébriques de fonctions génératrices (indice de cycles) et la classification combinatoire constructive ; les méthodes d'indice de cycles échangent un énumération explicite contre un encodage algébrique qui peut obscurcir l'intuition combinatoire tout en permettant des calculs généraux.

Synthèse

Le théorème de Pólya élève la moyenne de Burnside à un cadre algébrique : l'indice de cycles rassemble la structure cyclique et la substitution traduit les choix de couleurs en une fonction génératrice qui compte les configurations inequivalentes.