Introduction : Compter sous la Symétrie
En combinatoire, on est souvent confronté à des problèmes de dénombrement qui semblent simples à première vue, mais qui se compliquent lorsqu’on introduit une notion de symétrie. Par exemple, combien de colliers différents peut-on faire avec un certain nombre de perles de différentes couleurs ? Deux colliers sont considérés comme identiques si l’on peut obtenir l’un à partir de l’autre par une simple rotation. Compter toutes les possibilités puis essayer d’éliminer les doublons est une tâche ardue et sujette à erreurs.
La formule de Burnside (également connue sous le nom de lemme de Burnside ou formule de Cauchy-Frobenius) est un outil d’une puissance remarquable qui résout élégamment ce type de problème. Elle utilise la théorie des actions de groupe pour donner une méthode directe et infaillible pour compter le nombre d’objets « vraiment » distincts, c’est-à-dire le nombre d’orbites.
Soit $G$ un groupe fini agissant sur un ensemble fini $X$. Le nombre d’orbites de cette action, noté $|X/G|$, est donné par la formule : $$ |X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g| $$ où $X^g = \{ x \in X \mid g \star x = x \}$ est l’ensemble des points de $X$ qui sont fixés par l’élément $g$.
En d’autres termes, le nombre de configurations distinctes (orbites) est la moyenne du nombre de configurations laissées inchangées par chaque symétrie (élément du groupe).
Exemple Détaillé : Coloriage des Sommets d’un Carré
Reprenons un exemple classique : combien y a-t-il de façons distinctes de colorier les 4 sommets d’un carré avec 2 couleurs (disons Noir et Blanc), si l’on considère que deux coloriages sont identiques s’ils peuvent être obtenus l’un de l’autre par rotation ?
Étape 1 : Identifier l’ensemble $X$ et le groupe $G$
- L’ensemble $X$ est l’ensemble de tous les coloriages possibles sans tenir compte de la symétrie. Chaque sommet peut être Noir ou Blanc, donc $|X| = 2^4 = 16$.
- Le groupe $G$ est le groupe des symétries que l’on autorise. Ici, ce sont les rotations du carré. Ce groupe est cyclique d’ordre 4, $G = \{R_0, R_{90}, R_{180}, R_{270}\}$, où $R_k$ est la rotation de $k$ degrés. On a $|G|=4$.
Le groupe $G$ agit sur l’ensemble $X$. Notre but est de trouver le nombre d’orbites de cette action.
Étape 2 : Pour chaque symétrie $g \in G$, compter ses points fixes $|X^g|$
Un « point fixe » ici est un coloriage qui reste inchangé après l’application d’une rotation.
-
$g = R_0$ (rotation de 0°) : C’est l’identité. Elle ne bouge rien. Tous les 16 coloriages sont donc fixés par $R_0$.
$|X^{R_0}| = 16$. -
$g = R_{90}$ (rotation de 90°) : Pour qu’un coloriage soit inchangé par une rotation de 90°, il faut que le sommet 1 ait la même couleur que le sommet 2, qui doit avoir la même couleur que le 3, qui doit avoir la même couleur que le 4. Bref, tous les sommets doivent avoir la même couleur. Il n’y a que deux tels coloriages : tout Noir ou tout Blanc.
$|X^{R_{90}}| = 2$. -
$g = R_{180}$ (rotation de 180°) : Un coloriage est fixé si les paires de sommets opposés ont la même couleur. Le sommet 1 doit avoir la même couleur que le 3, et le sommet 2 la même que le 4. Nous avons 2 choix pour la paire {1,3} et 2 choix pour la paire {2,4}, soit $2 \times 2 = 4$ coloriages possibles.
$|X^{R_{180}}| = 4$. -
$g = R_{270}$ (rotation de 270°) : Le raisonnement est le même que pour $R_{90}$. Pour que le coloriage soit fixe, tous les sommets doivent avoir la même couleur.
$|X^{R_{270}}| = 2$.
Étape 3 : Appliquer la formule
Nous avons tous les ingrédients. Appliquons la formule de Burnside : $$ |X/G| = \frac{1}{|G|} \left( |X^{R_0}| + |X^{R_{90}}| + |X^{R_{180}}| + |X^{R_{270}}| \right) $$ $$ |X/G| = \frac{1}{4} (16 + 2 + 4 + 2) = \frac{24}{4} = 6 $$ Conclusion : Il existe exactement 6 façons distinctes de colorier les sommets d’un carré avec deux couleurs, à rotation près.
Conclusion : Un Outil Puissant
La formule de Burnside est un exemple spectaculaire de la manière dont la théorie abstraite des actions de groupe peut être appliquée pour résoudre des problèmes de dénombrement concrets. Elle fournit une méthode systématique qui évite les doubles comptages fastidieux. Cette formule est la base d’un résultat encore plus général et puissant, le théorème de l’énumération de Pólya, qui permet non seulement de compter le nombre de configurations, mais aussi de les classer selon leurs propriétés (par exemple, combien de colliers ont 3 perles rouges et 2 perles bleues).