(prerequisite reading: Orbit-stabilizer theorem, group acting on set)

The number of orbits of the group G acting on the finite set X is

(please excuse my crummy ASCII art)

--- 1 \ --- > | Fixwhere Fix_{X}(g) | |G| / --- g∈G

_{X}(g) = { a∈X | g(a) = a } = the subset of X which is "fixed" by g.

### Application

Imagine we have a necklace that we want to put 4 beads on, choosing from a set of 2 colours (exercise: generalise this to n beads from k colours):1*----*2 | | | | 4*----*3We want to find out how many unique necklaces we can create, if we consider two necklaces to be equivalent if we can get from one to the other by simply rotating the necklace.

The group G that we need to consider is thus the rotation group generated by a single permutation π = (1234). Let X be the set of colour schemes; that is, the set of mappings from the 4 bead positions to the 2 colours. It should be clear that the action of an element of G acting on X is simply rotating the colour scheme, and so the orbits of G is therefore the set of distinct necklaces.

Now the group G has 4 elements: 1, π, π

^{2}and π

^{3}. We need to work out the values of | Fix

_{X}(g) |:

FixHence by_{X}(1) = X => | Fix_{X}(1) | = 16 Fix_{X}(π) = { single-colour necklaces } => | Fix_{X}(&pi) | = 2 Fix_{X}(π^{2}) = { alternating-colour and single-colour necklaces } => | Fix_{X}(π^{2}) | = 4 Fix_{X}(π^{3}) = Fix_{X}(π) => | Fix_{X}(π^{3}) | = 2

*Burnside's Lemma*, the number of orbits is

(1/4) [ 16 + 2 + 4 + 2 ] = 6Therefore there are exactly 6 distinct necklaces with 4 beads selected from 2 colours.