Burnside's Lemma

How many different necklaces can you make with 6 beads in 2 colors, if turning a necklace does not change it? There are $2^{6} = 64$ colorings, and the rotations group them into orbits; the question asks for the number of orbits. Dividing by the number of rotations fails, because orbits have different sizes. Burnside's lemma counts them correctly.

Por qué funciona

Burnside's lemma. If a finite group $G$ acts on a finite set $X$, the number of orbits is $$\frac{1}{|G|}\sum_{g \in G} |\mathrm{Fix}(g)|, \qquad \mathrm{Fix}(g) = \{x : g \cdot x = x\}.$$ Proof. Count the pairs $(g, x)$ with $g \cdot x = x$ in two ways. By $g$: $\sum_{g} |\mathrm{Fix}(g)|$. By $x$: $\sum_{x} |G_{x}|$, and by orbit–stabilizer $|G_{x}| = |G|/|G \cdot x|$. So $$\sum_{g} |\mathrm{Fix}(g)| = |G| \sum_{x} \frac{1}{|G \cdot x|}.$$ The points of one orbit $O$ contribute $|O| \cdot \frac{1}{|O|} = 1$, so the last sum is the number of orbits. $\square$

Counting fixed colorings. A coloring is fixed by a symmetry exactly when the symmetry never moves a bead onto a bead of a different color, that is, when each cycle of the symmetry (as a permutation of the beads) is a single color. With $k$ colors and $c$ cycles, $k^{c}$ colorings are fixed. Rotating $n$ beads by $j$ steps has $\gcd(n, j)$ cycles.

Rotating a 6-bead necklace by 2 steps makes 2 cycles (rings of the same color), so $2^{2} = 4$ colorings are fixed. The table averages the fixed counts over all six rotations.

Ejemplo resuelto: Necklaces with 6 beads

Count 6-bead necklaces in 2 colors, up to rotation.

Rotations by $0, 1, 2, 3, 4, 5$ steps have $6, 1, 2, 3, 2, 1$ cycles.
Fixed colorings: $64 + 2 + 4 + 8 + 4 + 2 = 84$.
Number of necklaces: $84/6 = 14$.

Respuesta: $14$.

Ejemplo resuelto: Corners of a square

Color the 4 corners of a square with 2 colors. How many colorings are there up to rotations and reflections ($D_{4}$)?

$e$: $2^{4} = 16$. Quarter turns $r, r^{3}$ (one 4-cycle): $2$ each. Half turn (two 2-cycles): $4$.
Diagonal mirrors (two fixed corners, one 2-cycle): $2^{3} = 8$ each. Side mirrors (two 2-cycles): $4$ each.
Total $16 + 2 + 2 + 4 + 8 + 8 + 4 + 4 = 48$; divide by $8$.

Respuesta: $6$.

Ejemplo resuelto: Painting a cube

Paint each face of a cube one of 2 colors. How many different cubes are there, up to rotation?

The $24$ rotations by type, with their cycles on the faces: identity ($6$ cycles); $6$ quarter turns about face axes ($3$ cycles); $3$ half turns about face axes ($4$); $8$ turns about vertex axes ($2$); $6$ half turns about edge axes ($3$).
Sum: $2^{6} + 6 \cdot 2^{3} + 3 \cdot 2^{4} + 8 \cdot 2^{2} + 6 \cdot 2^{3} = 64 + 48 + 48 + 32 + 48 = 240$.
$240/24 = 10$.

Respuesta: $10$.

Error común

Dividing the total number of colorings by $|G|$: $64/6$ is not even a whole number. That shortcut assumes every orbit has $|G|$ members, which fails whenever some coloring is fixed by a symmetry other than $e$ (the one-color necklaces are fixed by everything). Burnside's average of fixed counts is always a whole number; if yours is not, recount the cycles.

Idea clave

Number of orbits = average number of fixed points: $\frac{1}{|G|}\sum_{g} |\mathrm{Fix}(g)|$. For colorings, a symmetry with $c$ cycles fixes $k^{c}$ of them.

Práctica

Se apoya en

Lleva a

Fuentes y lecturas