Burnside Necklace Symmetry

Burnside's Lemma (or the Cauchy-Frobenius lemma) provides a powerful way to count the number of distinct configurations of an object under a group of symmetries, like a necklace under rotation or a bracelet under both rotation and reflection. It tells us that the number of orbits (distinct colorings) is exactly the average number of configurations fixed by the group elements.

Worked Example

Let's consider coloring a necklace of length n = 4 with q = 2 colors (say, 0 and 1) under Rotations only. There are 2^4 = 16 total possible basic colorings. The group of rotations has 4 elements: rotation by 0, 1, 2, and 3 positions. We count how many colorings remain unchanged (fixed) when each rotation is applied:

Rotation by 0 (identity): All 16 colorings are fixed.
Rotation by 1: Only colorings where all beads are the same color are fixed. (0000 and 1111). That's 2 fixed colorings.
Rotation by 2: Colorings must have the pattern ABAB. (0000, 1111, 0101, 1010). That's 4 fixed colorings.
Rotation by 3: Similar to rotation by 1, only 2 fixed colorings.

The sum of fixed colorings is 16 + 2 + 4 + 2 = 24. The group order is 4. By Burnside's Lemma, the number of distinct orbits is 24 / 4 = 6.

Experiment

You can interactively explore the relationship between the group action, stabilizers, and orbits using the module:

Open the Burnside Necklace Symmetry module.
Set the Length to 6.
Set the Colors to 2.
Change the Symmetry to "Rotations and reflections" to see how reflections group configurations that were previously distinct into a single "bracelet".
Adjust the Coloring index to select a specific coloring. Observe its stabilizer size and the resulting orbit size. The product of the orbit size and stabilizer size always equals the group order (Orbit-Stabilizer Theorem).

Limitations

This module uses brute-force exhaustive evaluation to count fixed colorings by iterating over all q^n possible colorings and applying every group permutation. Because of this exponential growth, the module intentionally restricts the length n to a maximum of 6 and the number of colors to 3. For larger values, applying Pólya Enumeration Theorem, which uses the cycle index polynomial of the symmetry group, provides a much more efficient analytical approach without enumerating every state.

References

For more details on Burnside's Lemma, Pólya Enumeration Theorem, and generating cycle index polynomials, refer to the mathematical notes on:

Burnside's Lemma and Pólya's Enumeration Theorem

Burnside Necklace Symmetry