## Burnside’s Lemma

Burnside’s Lemma points the way to an efficient method for counting the number of orbits.

Define

$\mathrm{Fix}_\Omega (g) = \{ \alpha \in \Omega : g(\alpha) = \alpha \},$

that is, the set of all colourings fixed by a given symmetry. For example, if $$s$$ is the reflection that takes 123456 to 654321, then $$\mathrm{Fix}_\Omega(s)$$ is the set of all colourings that are palindromes when written out using our notation, such as RGBBGR.

This definition looks similar to some of our previous definitions, and it feels like they should be closely related. In fact, they are:

Lemma: (Burnside) Let $$n$$ be the number of orbits. Then:

$n = \frac{1}{|G|} \sum_{g\in G} |\mathrm{Fix}_\Omega(g)|$

Proof: Let the orbits be $$\Omega_1 ,..., \Omega_n$$, which partition $$\Omega$$. Then for any $$g \in G$$, the sets $$\mathrm{Fix}_{\Omega_1} (g) ,..., \mathrm{Fix}_{\Omega_n} (g)$$ partition $$\mathrm{Fix}_\Omega(g)$$, thus:

$\array { \sum_{g \in G} |\mathrm{Fix}_{\Omega}(g)| &=& \sum_{g \in G} \sum_k |\mathrm{Fix}_{\Omega_k}(g)| \\ &=& |\{ (g, \alpha) : g\in G, \alpha \in \Omega, g(\alpha) = \alpha \} | \\ &=& \sum_k \sum_{\alpha\in\Omega_i} |G_\alpha| }$

Applying $$|G_\alpha| |Orb_G(\alpha)| = |G|$$ completes the proof.∎

Burnside’s lemma makes our 6-bead puzzle much easier. Before, we had to consider every one of the $$3^6$$ colourings, and see which ones represent the same pattern.

Example: We can solve the 6-bead 3-colour necklace puzzle by considering each one of its 12 symmetries. For each symmetry $$g$$, we simply add $$|\mathrm{Fix}_\Omega(g)|$$ to a running total, then divide the result by 12.

The identity transformation fixes all colourings: $$|\mathrm{Fix}_\Omega(1)| = 3^6$$.

Rotation by 1 or 5 beads will be noticed unless the necklace is all the same colour, thus $$|\mathrm{Fix}_\Omega(r)| = |\mathrm{Fix}_\Omega(r^5)| = 3$$.

Rotation by 2 or 4 beads leaves the colouring unchanged if every second bead is the same colour, giving $$|\mathrm{Fix}_\Omega(r^2)| = |\mathrm{Fix}_\Omega(r^4)| = 3^2$$. Similarly, $$|\mathrm{Fix}_\Omega(r^3)| = 3^3$$.

As we saw above, the reflection $$s$$ fixes palindromes. We are free to choose the colours of the first 3 beads, and they determine the colour of the other 3 beads, so we have: $$|\mathrm{Fix}_\Omega(s)| = 3^3$$.

Reflection followed by rotation by 1 or 5 beads fixes colourings with a single bead coupled with a palindromic colouring of length 5, yielding $$|\mathrm{Fix}_\Omega(rs)| = |\mathrm{Fix}_\Omega(r^5s)| = 3^4$$. Similarly, $$|\mathrm{Fix}_\Omega(r^2s)| = |\mathrm{Fix}_\Omega(r^4s)| = 3^3$$, and $$|\mathrm{Fix}_\Omega(r^3s)| = 3^4$$.

The total of these set sizes is:

$3^6 + 2(3) + 2(3^2) + 3^3 + 3^3 + 2(3^4) + 2(3^3) + 3^4 = 1104$

and dividing by 12 gives the answer 92: there are 92 3-colour 6-bead necklaces.

The cycle index polynomial condenses the above into one succinct equation.

Ben Lynn blynn@cs.stanford.edu