I am reading "Introduction to Combinatorial Mathematics" by C. L. Liu.
The following theorem is in this book:
Theorem 5-2 (Burnside)
The number of equivalence classes into which a set $S$ is divided by the equivalence relation induced by a permutation group $G$ of $S$ is given by $$\frac{1}{|G|}\sum_{\pi\in G} \phi(\pi)$$ where $\phi(\pi)$ is the number of elements that are invariant under the permutation $\pi$.
The following two sentences are from the proof of this theorem in this book:
For any element $s$ in $S$, let $\eta(s)$ denote the number of permutations under which $s$ is invariant. Then $$\sum_{\pi\in G} \phi(\pi)=\sum_{s\in S} \eta(s)$$ because both $\sum_{\pi\in G} \phi(\pi)$ and $\sum_{s\in S} \eta(s)$ count the total number of invariances under all the permutations in $G$.
Why is the formula $\frac{1}{|G|}\sum_{\pi\in G} \phi(\pi)$ more useful than $\frac{1}{|G|}\sum_{s\in S} \eta(s)$?
In this book, the author wrote an application of Burnside's Lemma:
Example 5-2
Find the number of distinct strings of length $2$ that are made up of blue beads and yellow beads. The two ends of a string are not marked, and two strings are, therefore, indistinguishable if interchanging the ends of one will yield the other. Let $b$ and $y$ denote blue and yellow beads, respectively. Let $bb,by,yb,$ and $yy$ denote the four different strings of length $2$ when equivalence between strings is not taken into consideration. The problem is to find the number of equivalence classes into which the set $S=\{bb,by,yb,yy\}$ is divided by the equivalence relation induced by the permutation group $G=\{\pi_1,\pi_2\}$, where $$\pi_1=\begin{pmatrix}bb & by & yb & yy\\bb & by & yb & yy\end{pmatrix}\text{ }\pi_2=\begin{pmatrix}bb & by & yb & yy\\bb & yb & by & yy\end{pmatrix}.$$
The permutation $\pi_1$ merely indicates that every string is equivalent to itself, and the permutation $\pi_2$ indicates the equivalence between strings when the two ends of a string are interchanged. According to Burnside's theorem, the number of distinct strings is $$\frac{1}{2} (4+2)=3.$$
If we use the formula $\frac{1}{|G|}\sum_{s\in S} \eta(s)$, then we count as follows:
$$\frac{1}{2} (2+1+1+2)=3.$$
In this example, I don't think the formula $\frac{1}{|G|}\sum_{\pi\in G} \phi(\pi)$ is more useful than $\frac{1}{|G|}\sum_{s\in S} \eta(s)$.
But when we write Burnside's Lemma, we write $\frac{1}{|G|}\sum_{\pi\in G} \phi(\pi)$, but we don't write $\frac{1}{|G|}\sum_{s\in S} \eta(s)$.
I don't know why.
Best Answer
Simply, $\sum_{g\in G}\left|\text{Fix}(g)\right|$ is easier to compute than $\sum_{s\in S}\left|\text{Stab}(s)\right|$, because $G$ is typically much smaller than $S$.
Let's say you want to compute the number of inequivalent colorings of a cube up to rotation, where each face can be colored in one of $10$ colors. Letting $G$ be the group of symmetries of the cube, and $S$ be the set of colorings of a fixed cube ignoring symmetry, then $G$ acts on $S$, and we want to find the number of orbits of this action. We can compute this using either $$ \frac1{|G|}\sum_{g\in G}\left|\text{Fix}(g)\right|\quad \text{or}\quad \frac 1{|G|}\sum_{s\in S}\left|\text{Stab}(s)\right| $$ Note that $|G|=24$, while $|S|=10^6$. Would you rather compute a sum of $24$ numbers, or a sum of a million numbers?