Burnside's Lemma

Burnside's lemma (also called the Cauchy-Frobenius lemma) counts the number of distinct objects under a group of symmetries: $$|X/G| = \frac{1}{|G|} \sum_{g \in G} |\text{Fix}(g)|$$ where $|X/G|$ is the number of distinct objects (orbits), $G$ is the symmetry group, and $\text{Fix}(g)$ is the set of objects unchanged by symmetry $g$. Intuition: "Count the average number of colorings fixed by each symmetry." If you have a necklace with $n$ beads and $k$ colors, the symmetries are rotations (and possibly reflections). For each rotation, count how many colorings look the same after that rotation. Average over all rotations. When to use: "How many distinct necklaces / bracelets / colorings are there, up to rotation / reflection?" Any time the problem says "considered the same under symmetry." Alternative approach: For simple cases, you can enumerate by hand or use inclusion-exclusion. Burnside is the systematic version. Example: How many distinct 4-bead necklaces with 2 colors? Symmetry group is rotations $\{0°, 90°, 180°, 270°\}$. - 0° rotation: all $2^4 = 16$ fixed - 90° rotation: all beads same color → $2$ fixed - 180° rotation: beads pair up → $2^2 = 4$ fixed - 270° rotation: same as 90° → $2$ fixed Answer: $\frac{16 + 2 + 4 + 2}{4} = 6$.