Lemme de Burnside : exemples et applications
Le lemme de Burnside... Outre le fait qu'il n'est pas dû à Burnside et qu'on peut le considérer autrement qu'un lemme, ce résultat obscur de la théorie des groupes permet de faire des choses hallucinantes ! Si si ! Il permet par exemple de compter le nombre de colliers que l'on peut faire avec 3 perles rouges, 3 perles bleues et 5 perles vertes. Il permet aussi de compter le nombre de colliers que l'on peut faire avec 6 perles jaunes, 3 perles bleues, une perle verte et une perle rouge.
Il permet en fait de répondre à n'importe quel problème de dénombrement avec des perles ! (et certains problèmes sans perle : combien y a-t-il de façons de partager un paquet de Vache qui rit (aux isométries près) entre 3 personnes, combien existe-t-il de sudokus réellement différents, etc.). Le lemme de Burnside est l'exemple typique de l'énoncé abstrait d'un domaine abstrait qui trouve des applications concrètes dans des domaines concrets (pour peu que l'on aime fabriquer des colliers).
Exemple I-2
Pour réaliser de tels dénombrements, il faut seulement s'intéresser de près à la théorie des groupes agissant sur un ensemble. Au diable la théorie, passons directement à la pratique : pour cela, il nous faut un groupe et un ensemble. Pour ce premier exemple, prenons l'ensemble des colliers rouges et bleus à 5 perles :
Sept colliers bicolores à 5 perles, parmi les 32 existants
Cet ensemble contient 25 (=32) éléments (chaque perle pouvant être de deux couleurs).
Quand on regarde les exemples, on voit certains colliers sont les mêmes, à une rotation près (par exemple, le 3ème se déduisent du deuxième par une rotation d'un cinquième de tour). Puisqu'il nous faut également un groupe, c'est naturellement que l'on prend celui des rotations du pentagone.
Il existe 5 rotations (r1, r2, r3, r4 et r5) qui transforment ce pentagone en lui-même : elles forment le groupe des rotations du pentagone. Appelons ce groupe Z/5Z.
L'ensemble des 5 rotations du pentagone forment un groupe (la succession de deux rotations est toujours une rotation, et il existe une rotation neutre).
Le groupe agit sur l'ensemble : sous l'action de la rotation r2 (2 cinquièmes de tour), le collier est transformé en un collier différent. Certains colliers ne sont pas transformé sous l'effet d'une rotation (les colliers d'une seule couleur)
La question est donc de trouver le nombre de colliers différents en tenant compte que certains sont identiques (moyennant l'action du groupe Z/5Z sur l'ensemble des colliers). Pour chaque élément du groupe, certains colliers restent inchangés : par exemple, sous l'effet de la rotation r1 (un cinquième de tour), le collier tout rouge est inchangé. Le lemme de Burnside dit alors la chose suivante : le nombre que l'on cherche est la moyenne des nombres de colliers inchangés.
Procédons donc au calcul :
- la rotation r1 : elle ne fixe que deux colliers : le tout rouge et le tout bleu. (2 colliers)
- la rotation r2 : idem (2 colliers)
- la rotation r3 : idem (2 colliers)
- la rotation r4 : idem (2 colliers)
- la rotation r5 (qui est en fait une rotation neutre) : aucun collier n'est transformé par cette rotation. Elle fixe donc les 32 colliers.
La moyenne est donc : (2+2+2+2+32)/5 = 8
Il y a donc 8 colliers différents !
Exemple I-3
Deuxième exemple, un peu plus parlant : combien y a t-il de façons de partager équitablement une boîte de Vache qui rit entre 3 personnes, sachant que deux partages sont équivalents s'ils se déduisent l'un de l'autre par une rotation ou une symétrie.
On a donc besoin d'un ensemble : ça sera celui des partages de Vache qui rit entre 3 personnes (Cyan, Magenta et Jaune). Cyan prend deux parts parmi les six (2 parmi 6 = 15 possibilités), Magenta prend deux parts parmi les 4 restantes (2 parmi 4 = 6 possibilités), Jaune prend les deux dernières (1 possibilité). Au total, il y a donc 15 × 6 × 1 = 90 partages différents.
Quatre partages de Vache qui rit, parmi les 90 existants. Les deux premiers sont équivalents (par une rotation), les deux derniers également (par une symétrie axiale).
Il nous faut également un groupe. On va prendre le groupe D6, le groupe des isométries de l'hexagone. Il contient 12 éléments : l'identité (Id), 5 rotations (r1, r2, r3, r4 et r5, respectivement de 1, 2, 3, 4 et 5 sixièmes de tour) et 6 symétries axiales (s1, s2, s3, s4, s5 et s6).
Les 12 isométries du groupe D6.
De la même façon que précédemment, les isométries agissent sur les partages, et en laissent certains fixes. Voyons dans le détail :
- Id laisse fixe l'ensemble des partages (90 partages)
- r1 et r5 (rotations) n'en fixent aucun (2×0 partages)
- r2 et r4 (rotations) n'en fixent aucun (2×0 partages)
- r3 (symétrie centrale) laisse fixe les partages où les parts sont opposés (6 partages)
- s1, s3 et s5 (symétries axiales) laisse fixe les partages où les parts sont symétriques, l'axe ne coupe pas de parts (3×6 partages)
- s2, s4 et s6 (symétries axiales) laisse fixe les partages où les parts sont symétriques, l'axe coupant une paire de parts (3×6 partages)
Au final, il y a donc (90+2×0+2×0+6+3×6+3×6)/12 = 11 partages possibles !
Application I-4
On pourrait multiplier les exemples utilisant les groupes d'isométries des polygones ou polyèdres réguliers ("combien y a-t-il de façons de peindre les faces d'un cube de façon à ce que 3 faces soient rouges, 2 jaunes et 1 bleue ?"), mais on peut également répondre à l'aide de Burnside à cette question primordiale : "combien existe-t-il de sudokus réellement différents" ?
Un dénombrement minutieux (*) permet de montrer qu'il en existe 6670903752021072936960., mais on sait qu'il en existe en réalité beaucoup moins que ça : peut-on réellement considérer deux grilles de sudokus différentes si l'une est le reflet de l'autre dans un miroir ?
Deux grilles de sudokus sont donc équivalentes si on peut passer de l'une à l'autre en faisant une (ou plusieurs) des opérations suivantes :
- permutation des nombres
- permutation de deux colonnes au sein d'un même pile (bloc de 3 colonnes)
- permutation de deux blocs de colonnes
- permutation de deux lignes au sein d'un même bande (groupe de 3 lignes)
- permutation de deux blocs de lignes
- transposition (inversion des lignes et des colonnes)
- rotation
- symétrie axiale
En mettant de côté la permutation des nombres, les opérations légales ne sont que des permutations des 81 cases du sudoku.
Combien existe-t-il de grilles de sudokus équivalentes ? Le lemme de Burnside approche !
Il nous faut donc un ensemble. On ne va pas prendre les 6670903752021072936960 grilles différentes : c'est beaucoup trop. Quitte à permuter les nombres, on peut toujours se ramener à une grille dont la première région est "1-2-3/4-5-6/7-8-9". On dira que deux grilles sont semblables si on peut passer de l'une à l'autre en permutant les chiffres.
Puisqu'il existe 9! = 362880 permutations de 9 chiffres, on peut se ramener à l'ensemble des 18383222420692992 grilles de sudoku non semblables.
Il nous faut également un groupe, celui des permutations légales de la grille de Sudoku. Avec le logiciel adéquat, on peut montrer qu'il existe 3359232 opérations légales. En tenant compte des classes de conjugaison (certaines opérations se comportent de la même façon - dans l'exemple précédent, c'était le cas de r1 et r5, ou de s1, s3 et s5 ), on peut se ramener à l'étude 275 (classes de conjugaisons de) permutations de la grille de Sudoku.
La grille de sudoku est invariante (à une similitude près) sous l'opération "permutation [...] bande"
Pour chacune de ces 275 opérations, il faut trouver le nombre de grilles fixées (à une similitude près)
- Pour l'opération Id, 18383222420692992 grilles sont fixées.
- Pour l'opération "permutation des colonnes 1, 2 et 3", aucune grille n'est fixée.
- Pour l'opération "permutation circulaire des colonnes au sein de chaque pile, puis permutation circulaire des lignes au sein de la troisième bande", un dénombrement minutieux montre que 21233664 grilles sont fixées (à une similitude près).
- etc.
En appliquant alors le lemme de Burnside, on trouve qu'il existe 5472730538 grilles de sudokus réellement différentes !
Alors ?! Qui a dit que la théorie des groupes n'avait pas d'applications concrètes ?...
Sources :
Les colliers de G. Polyà, un exposé bien plus rigoureux qui parle de formule de Burnside et du théorème de Polyà.
(*) Mathematics of Sudoku I, où Felgenhauer et Jarvis montrent qu'il existe 6.7×1021 grilles de sudoku.