Dénombrement de Burnside

Actions de groupe, orbites & lemme de Burnside

Idée. Combien d'objets vraiment différents existe-t-il quand on identifie ceux qui se déduisent l'un de l'autre par une symétrie ? Colliers que l'on peut tourner, faces d'un dé, coloriages d'un échiquier… Le lemme de Burnside ramène ce comptage « à symétrie près » à une simple moyenne de points fixes.

Note de niveau (L3). Chapitre démonstratif (les exercices sont des preuves) prolongeant Théorie des groupes (actions, théorème orbite-stabilisateur). Les valeurs de dénombrement sont vérifiées machine sur des instances finies ; les raisonnements se rédigent.

A. Action d'un groupe

Une action (à gauche) d'un groupe $(G,\cdot)$ sur un ensemble $X$ est une application $G\times X\to X$ , $(g,x)\mapsto g\cdot x$ , telle que

e\cdot x=x,\qquad g\cdot(h\cdot x)=(g\,h)\cdot x\qquad(\forall g,h\in G,\ \forall x\in X).

De façon équivalente, c'est un morphisme

G\to\operatorname{Sym}(X)

: chaque

g

agit comme une permutation de

X

Action	Ensemble $X$	$g\cdot x$
naturelle de $S_n$	$\{1,\dots,n\}$	$\sigma\cdot i=\sigma(i)$
rotations $C_n$	$n$ positions d'un collier	décalage circulaire
translation (Cayley)	$G$ lui-même	$g\cdot x=gx$
conjugaison	$G$ lui-même	$g\cdot x=gxg^{-1}$

B. Orbites & stabilisateurs

Pour $x\in X$ :

l'orbite $\mathcal O(x)=\{g\cdot x:g\in G\}$ — les objets « équivalents » à $x$ ;
le stabilisateur $\mathrm{Stab}(x)=\{g\in G:g\cdot x=x\}$ , qui est un sous-groupe de $G$ .

La relation $x\sim y\iff\exists g,\ y=g\cdot x$ est une équivalence : les orbites partitionnent $X$ . Compter les objets à symétrie près, c'est compter les orbites.

\boxed{\ \textbf{Orbite-stabilisateur :}\quad \lvert\mathcal O(x)\rvert\cdot\lvert\mathrm{Stab}(x)\rvert=\lvert G\rvert\quad(G\text{ fini}).\ }

C. Points fixes

Pour $g\in G$ , l'ensemble des points fixes est $\mathrm{Fix}(g)=\{x\in X:g\cdot x=x\}$ . À ne pas confondre avec le stabilisateur : $\mathrm{Stab}(x)$ fixe un point $x$ et fait varier $g$ ; $\mathrm{Fix}(g)$ fixe une transformation $g$ et fait varier $x$ .

D. Lemme de Burnside (Cauchy–Frobenius)

\boxed{\ N=\frac{1}{\lvert G\rvert}\sum_{g\in G}\lvert\mathrm{Fix}(g)\rvert\ }\qquad(N=\text{nombre d'orbites}).

Autrement dit : le nombre d'orbites est la moyenne du nombre de points fixes. Idée de preuve — double comptage de l'ensemble $S=\{(g,x):g\cdot x=x\}$ : compté par $g$ il vaut $\sum_g\lvert\mathrm{Fix}(g)\rvert$ ; compté par $x$ il vaut

\sum_x\lvert\mathrm{Stab}(x)\rvert=\sum_x\dfrac{\lvert G\rvert}{\lvert\mathcal O(x)\rvert}=\lvert G\rvert\cdot N.

E. Recette pour les coloriages

On colorie $n$ objets avec $q$ couleurs ; un groupe $G$ de permutations des objets agit. Une coloration est fixée par $g$ si et seulement si elle est constante sur chaque cycle de $g$ , donc

\lvert\mathrm{Fix}(g)\rvert=q^{\,c(g)}\qquad\big(c(g)=\text{nombre de cycles de }g\big),

et le nombre de coloriages distincts est

\ N=\dfrac{1}{\lvert G\rvert}\displaystyle\sum_{g\in G}q^{\,c(g)}.

Colliers (rotations $C_n$ , et $C_n\cong\mathbb U_n$ — racines $n$ -ièmes de l'unité). La rotation d'un cran à la puissance $k$ découpe les positions en $\gcd(k,n)$ cycles, d'où

N=\frac1n\sum_{k=0}^{n-1}q^{\gcd(k,n)}=\frac1n\sum_{d\mid n}\varphi\!\left(\tfrac{n}{d}\right)q^{d}.

Six colliers circulaires de quatre perles bicolores, représentant les six classes distinctes à rotation près : tout blanc, tout noir, une noire, trois noires, et deux noires adjacentes puis opposées. — **Les $6$ colliers à $4$ perles, $2$ couleurs (rotations $C_4$ ).** Le lemme de Burnside donne $N=\dfrac{16+2+4+2}{4}=6$ : un tout blanc, un tout noir, un à une perle noire, un à trois, et **deux** à deux perles noires (adjacentes ou opposées). C'est exactement la répartition de Pólya $[1,1,2,1,1]$ par nombre de perles noires.