◀ Group ActionsCycle Index ▶
Contents

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. It turns out they are indeed closely related:

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. Now, we instead consider every one of the symmetries, and count the number of colourings they fix.

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 💡