William Burnside aurait mis en évidence une formule combinatoire intéressante dans le cadre de ses travaux en théorie des groupes. Le lemme peut s’énoncer de la manière suivante :
On considère un ensemble E d’objets et un groupe G de permutations agissant sur E. Deux objets de E sont dits différents lorsqu’aucune des permutations du groupe ne transforme l’un des objets en l’autre. Le nombre d’objets « différents » est alors la moyenne des nombres d’objets qui restent invariants lorsqu’on applique toutes les transformations de G.
Le résultat se vérifie facilement dans un certain nombre de cas simples, comme le décompte de dominos (voir ci-après). Mais son utilisation est surtout pertinente dans les cas où un dénombrement direct demande l’examen de trop de cas distincts.
Des dominos aux coloriages
Dans un jeu de dominos, chaque case porte de 0 à 6 points. Deux dominos ne sont pas considérés comme différents si l’un des deux est obtenu à partir de l’autre par la rotation R de 180 degrés. On compte donc sept dominos différents dont une ou deux cases portent 0 point (elles sont vides), six dominos différents dont une ou deux cases portent 1 point (mais dont aucune case ne porte 0 point), et ainsi ...
Lire la suite