formule de Burnside

Coloriez les quatre sommets d’un carré en noir ou en jaune. Il existe 16 coloriages si le carré reste immobile. Pourtant, certains deviennent identiques dès que l’on tourne ou retourne le carré : ils forment une même famille, appelée orbite.

La formule de Burnside évite de comparer les 16 coloriages deux à deux. Pour chaque symétrie, elle compte ceux que cette symétrie ne change pas, puis fait la moyenne de ces nombres. Cette moyenne vaut exactement le nombre de coloriages réellement différents à symétrie près.

La formule de Burnside, aussi appelée lemme de Burnside, est un résultat de dénombrement pour une action d’un groupe fini G sur un ensemble fini E. Deux éléments de E appartiennent à la même orbite lorsqu’une transformation de G envoie l’un sur l’autre. Compter les orbites revient donc à compter les objets de E à l’action de G près.

Pour chaque transformation g du groupe, l’ensemble Fix(g) réunit les éléments de E que g laisse inchangés. Si k désigne le nombre d’orbites et |G| le nombre d’éléments du groupe, alors :

La somme compte les couples formés d’une transformation et d’un objet qu’elle fixe. Sa division par |G| donne toujours un entier, car cette moyenne est exactement le nombre d’orbites. L’action n’a pas besoin d’être fidèle ni libre : certaines transformations peuvent agir de la même façon, et certains objets peuvent avoir des symétries propres.

Si un groupe fini G agit sur un ensemble fini E, on compte, pour chaque élément g de G, le nombre |Fix(g)| d’éléments de E laissés inchangés. Le nombre k d’orbites est alors :

Autrement dit, on additionne les nombres de points fixes de toutes les transformations, identité comprise, puis on divise par le nombre de transformations du groupe.

La formule, sous cette forme, exige un ensemble E fini et un groupe G fini dont l’action sur E est définie. Il faut connaître toutes les transformations de G, compter leurs points fixes dans le même ensemble E et inclure l’identité. Le résultat obtenu est le nombre d’orbites de cette action précise.

Si G est infini, la somme indexée par ses éléments n’est plus nécessairement finie ; si E est infini, l’identité fixe déjà une infinité d’objets. Le dénombrement fini classique ne s’applique donc plus tel quel dès que la finitude de G ou des ensembles de points fixes nécessaires n’est pas assurée : il faut alors employer un résultat adapté au cadre considéré, avec des hypothèses supplémentaires. Si l’on oublie une symétrie du carré, les transformations retenues ne forment pas nécessairement le groupe voulu et le dénombrement répond à une autre question.

Colorions les quatre sommets d’un carré avec deux couleurs. L’ensemble E contient 2⁴ = 16 coloriages. Le groupe G comprend huit symétries : l’identité, trois rotations et quatre réflexions. Deux coloriages sont considérés comme identiques lorsqu’une de ces symétries transforme l’un en l’autre. Le schéma regroupe les huit nombres de points fixes utilisés dans la moyenne.

1. L’identité fixe les 16 coloriages. Chacun des deux quarts de tour impose une couleur commune aux quatre sommets, donc fixe 2 coloriages. Le demi-tour impose une couleur par paire de sommets opposés, donc en fixe 2² = 4.

2. Chacune des deux réflexions selon une diagonale fixe deux sommets et échange les deux autres : elle fixe 2³ = 8 coloriages. Chacune des deux réflexions selon les médianes échange deux paires de sommets : elle en fixe 2² = 4.

3. La formule donne :Il existe donc 6 coloriages distincts à symétrie près.

4. Un contrôle direct retrouve ces six orbites : aucun sommet noir, un noir, deux noirs adjacents, deux noirs opposés, trois noirs, ou quatre noirs. Chaque coloriage appartient à exactement l’un de ces six cas.

Pour compter des coloriages à symétrie près, on décrit d’abord le groupe géométrique réellement autorisé. Si seules les rotations sont admises, les réflexions doivent être exclues : les orbites obtenues peuvent alors différer.

Lorsque l’ensemble est petit, énumérer directement les orbites peut être plus rapide et fournit un bon contrôle. Burnside devient particulièrement utile quand les objets sont nombreux mais que les transformations se regroupent en quelques types ayant le même nombre de points fixes.

Si l’on veut seulement le nombre total d’objets et que chaque objet a une orbite de taille |G|, une division par |G| suffit. Dès qu’un objet possède une symétrie propre, cette division naïve échoue ; la moyenne des points fixes est alors le bon geste.

La division du nombre d’objets par le nombre de symétries n’est valable que lorsque chaque orbite contient |G| objets. Dans l’exemple du carré, les coloriages uniformes restent fixes sous les huit symétries : leurs orbites n’ont qu’un élément, et 16/8 = 2 ne donne pas les 6 orbites.

La formule orbite-stabilisateur décrit une orbite particulière : sa taille est |G| divisée par le nombre de transformations qui fixent l’objet choisi. Burnside additionne au contraire les points fixes de toutes les transformations pour compter toutes les orbites en une seule moyenne.

Identité oubliée. Elle fixe toujours les |E| éléments. Dans le carré, retirer son apport 16 donnerait 32/7, qui n’est pas le nombre d’orbites ; il faut moyenner sur les huit éléments du groupe complet.

Mauvais groupe de symétries. Compter avec quatre rotations ou avec les huit symétries du carré ne définit pas la même équivalence. Il faut décider si un reflet est autorisé avant de calculer les points fixes.

Points fixes mal interprétés. Fix(g) contient les objets entiers que g laisse inchangés, pas les positions géométriques immobiles. Une réflexion diagonale du carré fixe deux sommets, mais elle fixe 8 coloriages, car les deux sommets échangés doivent seulement porter la même couleur.

Action non fidèle. Deux éléments distincts de G peuvent produire la même transformation sur E. Ils restent deux termes de la moyenne : les fusionner sans remplacer le groupe par son image modifie à la fois la somme et le diviseur.

La fiche Action de groupe précise comment des transformations agissent sur un ensemble et organisent ses éléments en orbites.

Une autre lecture de la formule consiste à compter de deux façons les couples (g, x) tels que la transformation g fixe l’objet x. Ce double comptage explique pourquoi la moyenne des points fixes coïncide avec le nombre d’orbites.