## § Clean way to write burnside lemma

Burnside lemma says that $|Orb(G)| \equiv 1/|G| \sum_{g \in G} fix(g)$. We prove this as follows:
\begin{aligned} &\sum_{g \in G} fix(g) \\ &= \sum_{g \in G} |\{x : g(x) = x \}| \\ &= |\{(g, x) : g(x) = x \}| \\ &= \sum_{x \in X}|\{x : g(x) = x \}| \\ &= \sum_{x \in X} Stab(x) \end{aligned}
• From orbit stabilizer, we know that $|Orb(x)||Stab(x)| = |G|$.
• Since $|Orb(x)$ is the total cardinality of the orbit, each element in the orbit contributes $1/|Orb(x)|$ towards cardinality of the full orbit.
• Thus, the sum over an orbit $\sum_{x \in Orb(x)} 1/|Orb(x)|$ will be 1.
• Suppose a group action has two orbits, $O_1$ and $O_2$. I can write the sum $\sum_{x \in g} 1/|Orb(x)|$ as: $\sum_{x \in O_1} 1/|O_1| + \sum_{x \in O_2} 1/|O_2|$, which is equal to 2.
• I can equally write the sum as $\sum_{o \in Orbits} \sum_{x \in o} 1/|o|$. But this sum is equal to $\sum_{o \in Orbits} \sum_{x \in o} 1/|Orb(x)|$.
• This sum sums over the entire group, so it can be written as $\sum_{x \in G} 1/|Orb(x)|$.
• In general, the sum over the entire group $\sum_{x \in g} 1/|Orb(x)|$ will be the number of orbits, since the same argument holds for each orbit .
\begin{aligned} &= \sum_{x \in X} Stab(x) \\ &= \sum_{x \in X} |G|/|Orb(x)| \\ &= |G| \sum_{o \in orbits} \sum_{x \in o} 1/|o| \\ &= |G| \texttt{num.orbits} \\ \end{aligned}
So we have derived:
\begin{aligned} &\sum_{g \in G} fix(g) = |G| \texttt{num.orbits} \\ &1/|G| (\sum_{g \in G} fix(g)) = \texttt{num.orbits} \\ \end{aligned}
If we have a transformation that fixes many things, ie, $fix(g)$ is large, then this $g$ is not helping "fuse" orbits of $x$ together, so the number of orbits will increase.