Burnside's lemma and orbit counting

Let a finite group act on a finite set of positioned structures. Two structures are equivalent when one group element sends one to the other; the equivalence classes are the orbits. For a necklace where turning over is forbidden, rotations form the relevant cyclic group. If flipping the necklace is allowed, reflections must be included, giving a dihedral action. A color permutation is yet another possible equivalence and should not be assumed unless the problem explicitly identifies color names.

The stabilizer of a structure consists of symmetries that leave that entire structure unchanged. Orbit-stabilizer says that an orbit size equals the group order divided by its stabilizer size. Thus naive division by group order is correct only for a free action, where every stabilizer is trivial. A monochromatic necklace is an immediate counterexample to freeness: every rotation fixes it. Distinct positioned representations can therefore collapse by different multiplicities when symmetry is forgotten.

Count pairs consisting of a group element and a structure that it fixes. Summing first over group elements gives the sum of fixed-set sizes. Summing first over structures gives the sum of stabilizer sizes. Within one orbit, every stabilizer has the same size, and orbit-stabilizer shows that the orbit contributes exactly the group order to this second sum. Each orbit therefore contributes the same amount even though the orbit sizes themselves differ.

Dividing the pair count by the group order yields Burnside's lemma. This proof explains why averaging fixed structures works and why one must include the identity element: it fixes every positioned structure and supplies a potentially large term. The average is an integer because it counts orbits, not because each fixed-set size is divisible by the group order. Checking integrality is a useful arithmetic test, though it does not by itself prove that the chosen action models the intended equivalence.

A permutation of positions fixes a coloring exactly when every position cycle is monochromatic. If r named colors are allowed without restrictions, each cycle chooses a color independently, producing r raised to the number of cycles fixed colorings. Different cycles may choose the same color. A rotation by a positions on a ring of m positions has greatest-common-divisor(m,a) cycles, including m cycles for the identity rotation. This follows from the period of repeated addition modulo m.

Restrictions can change the cycle count argument. If exactly two positions must be red, assigning red to a cycle contributes its whole cycle length, so not every independent cycle-color choice is allowed. Likewise requiring every color to appear introduces an additional surjectivity condition. Burnside's formula remains valid, but each fixed-set count must incorporate the restriction. The formula handles symmetry; it does not replace the separate combinatorial work required to characterize the structures fixed by each group element.