📂Abstract Algebra

Burnside's Lemma Derivation

Overview

Burnside’s lemma is a representative application to the actions of a group and the isotropy subgroups that can be immediately used in combinatorics and other fields.

Formula ¹

For a finite group $G$ and a finite set $X$ that is a $G$-set, let $r$ be the number of orbits of $X$ under $G$. $$r |G| = \sum_{g \in G} \left| X_{g} \right|$$

Derivation

Let the cardinality of the set $\left\{ (g,x) \in G \times X | gx = x \right\}$ be $N$ then $$X_{g} = \left\{ x \in X \ | \ gx = x \right\}$$ and, for $G_{x} = \left\{ g \in G \ | \ gx = x \right\}$, the following holds. $$N = \sum_{g \in G} |X_{g}| = \sum_{x \in X} |G_{x}|$$

Properties of the Isotropy Subgroup: If $X$ is a $G$-set, then $|Gx| = ( G : G_{x})$. If $G$ is a finite group, then $|Gx|$ is a divisor of $|G|$.

Since $|G| = |G_{x} | |Gx|$, from $\displaystyle N = \sum_{x \in X} |G_{x}|$ $$N = \sum_{x \in X} {{|G|} \over {|Gx|}} = |G| \sum_{x \in X} {{1} \over {|Gx|}}$$ For any orbit $\mathscr{O}$, $|Gx|$ has the same value for $x \in \mathscr{O}$, $$\sum_{x \in \mathscr{O}} {{1} \over {| Gx | }} = 1$$ The number of orbits is $r$, so $N = |G| r$ and summarizing, we obtain the following. $$r |G| = \sum_{g \in G} \left| X_{g} \right|$$

■

Examples

Circular Table Problem

Calculate the number of ways $7$ people can be seated around a circular table.

---

The number of ways to arrange $7$ people in a row is $7!$.

The ‘action’ of rotating counter-clockwise is in total $7$ ways. Therefore, the number of ways is $$r = {{1} \over {|G|}} \sum_{g \in G} | X_{g} | = {{1} \over {7}} 7! = 720$$

Bead Problem

Calculate the number of ways to thread $7$ distinct beads on a string.

---

The number of ways to arrange $7$ beads in a row is $7!$. The action of rotating counter-clockwise and flipping the string of beads is in total $7 \times 2 = 14$ ways. Therefore, $$r = {{1} \over {|G|}} \sum_{g \in G} | X_{g} | = {{1} \over {14}} 7! = 360$$