Proposition15.8
Let a group \(G\) act on a finite set \(\cgC\text{.}\) Then for all \(C\in \cgC\text{,}\) \begin{equation*} \sum_{C'\in\langle C\rangle} |\stab_G(C')| = |G|. \end{equation*}
Burnside's lemma 1 relates the number of equivalence classes of the action of a group on a finite set to the number of elements of the set fixed by the elements of the group. Before stating and proving it, we need some notation and a proposition. If a group \(G\) acts on a finite set \(\cgC\text{,}\) let \(\sim\) be the equivalence relation induced by this action. (As before, the action of \(\pi\in G\) on \(\cgC\) will be denoted \(\pi^*\text{.}\)) Denote the equivalence class containing \(C\in \cgC\) by \(\langle C\rangle\). For \(\pi\in G\text{,}\) let \(\fix_\cgC(\pi)=\{C\in \cgC\colon \pi^*(C) = C\}\text{,}\) the set of colorings fixed by \(\pi\text{.}\) For \(C\in\cgC\text{,}\) let \(\stab_G(C)=\{\pi\in G\colon \pi(C) = C\}\) be the stabilizer of \(C\) in \(G\text{,}\) the permutations in \(G\) that fix \(C\text{.}\)
To illustrate these concepts before applying them, refer back to Table 15.2. Using that information, we can determine that \(\fix_\cgC(r_2) = \{C_1,C_{10},C_{11},C_{16}\}\text{.}\) Determining the stabilizer of a coloring requires finding the rows of the table in which it appears. Thus, \(\stab_{D_8}(C_7) = \{\iota,h\}\) and \(\stab_{D_8}(C_{11}) = \{\iota,r_2,p,n\}\text{.}\)
Let a group \(G\) act on a finite set \(\cgC\text{.}\) Then for all \(C\in \cgC\text{,}\) \begin{equation*} \sum_{C'\in\langle C\rangle} |\stab_G(C')| = |G|. \end{equation*}
With Proposition 15.8 established, we are now prepared for Burnside's lemma.
Let a group \(G\) act on a finite set \(\cgC\text{.}\) If \(N\) is the number of equivalence classes of \(\cgC\) induced by this action, then \begin{equation*} N = \frac{1}{|G|} \sum_{\pi\in G} |\fix_\cgC(\pi)|. \end{equation*}
Before we proceed to the proof, note that the calculation in Burnside's lemma for the example of \(2\)-coloring the vertices of a square is exactly the calculation we performed at the end of Section 15.1.
Burnside's lemma helpfully validates the computations we did in the previous section. However, what if instead of a square we were working with a hexagon and instead of two colors we allowed four? Then there would be \(4^6=4096\) different colorings and the dihedral group of the hexagon has \(12\) elements. Assembling the analogue of Table 15.2 in this situation would be a nightmare! This is where the genius of Pólya's approach comes into play, as we see in the next section.