Pólya Theory - Burnside's Lemma

Burnside’s Lemma

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

Define

{Fix}_{Ω} (g) = {α \in Ω : g (α) = α},

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 ${Fix}_{Ω} (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} ∣ {Fix}_{Ω} (g) ∣

Proof: Let the orbits be $Ω_{1}, . . ., Ω_{n}$ , which partition $Ω$ . Then for any $g \in G$ , the sets ${Fix}_{Ω_{1}} (g), . . ., {Fix}_{Ω_{n}} (g)$ partition ${Fix}_{Ω} (g)$ , thus:

\begin{matrix} \sum_{g \in G} ∣ {Fix}_{Ω} (g) ∣ & = & \sum_{g \in G} \sum_{k} ∣ {Fix}_{Ω_{k}} (g) ∣ \\ = & ∣ {(g, α) : g \in G, α \in Ω, g (α) = α} ∣ \\ = & \sum_{k} \sum_{α \in Ω_{i}} ∣ G_{α} ∣ \end{matrix}

Applying $∣ G_{α} ∣ ∣ {Orb}_{G} (α) ∣ = ∣ G ∣$ completes the proof.