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{.}$
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.