Une technique de comptage qui calcule le nombre d'orbites distinctes (configurations non équivalentes) d'un ensemble fini sous l'action d'un groupe fini en faisant la moyenne du nombre de points fixes des éléments du groupe.

Principe

Un groupe partitionne un ensemble en orbites ; le nombre d'orbites est égal à la moyenne, sur les éléments du groupe, du nombre d'éléments fixés par chaque élément du groupe. Cela réduit l'énumération des classes d'équivalence au calcul des ensembles de points fixes pour chaque symétrie.

Démonstration

Pour compter les colorations des sommets d'un carré à rotation et réflexion près, on énumère chaque symétrie du groupe diédral, on compte les colorations invariantes par chaque symétrie, on moyenne ces nombres et on obtient le nombre de colorations distinctes sous l'action du groupe complet.

Mauvaise application

Appliquer le lemme lorsque les opérations de symétrie considérées ne forment pas un groupe, omettre des éléments du groupe, ou l'utiliser avec des groupes infinis ou des ensembles infinis sans justification conduit à des décomptes erronés.

Conséquence

Fournit une recette algorithmique simple pour compter des configurations non équivalentes ; quand les couleurs ou poids sont uniformes, il donne des comptes d'orbites exacts et sert de base à des raffinements comme le théorème de Pólya pour des objets colorés avec multiplicités.

Inversion

Inverser le point de vue—déduire les comptes de points fixes à partir des comptes d'orbites connus—requiert une structure supplémentaire ; les seuls comptes d'orbites ne déterminent généralement pas de façon unique la distribution des points fixes par élément du groupe.

Limite

Suppose un groupe fini agissant sur un ensemble fini ; il ne traite pas directement des groupes continus, des ensembles infinis ou des actions où le calcul des points fixes est infaisable, bien que des versions mesurables ou intégrales existent dans d'autres contextes.

Tension sémantique

La tension porte sur la simplicité de la moyenne de Burnside et le théorème de Pólya, qui encapsule l'idée de Burnside avec des fonctions génératrices et des polynômes d'indice de cycles pour compter des objets colorés avec multiplicité ; les deux sont reliés mais répondent à des besoins computationnels différents.

Synthèse

Le lemme de Burnside est une règle de comptage sensible aux symétries : pour chaque élément du groupe compter les configurations qu'il fixe, faire la moyenne de ces nombres sur le groupe et ainsi déterminer le nombre de configurations non équivalentes sous l'action du groupe.