(mathematics):

(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  \
       ---  >   | FixX(g) |
       |G| /
           ---
           g∈G
where FixX(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*----*3
We 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 | FixX(g) |:
    FixX(1) = X => | FixX(1) | = 16
    FixX(π) = { single-colour necklaces } => | FixX(&pi) | = 2
    FixX2) = { alternating-colour and single-colour necklaces }
            => | FixX2) | = 4
    FixX3) = FixX(π) => | FixX3) | = 2
Hence by Burnside's Lemma, the number of orbits is
    (1/4) [ 16 + 2 + 4 + 2 ] = 6
Therefore there are exactly 6 distinct necklaces with 4 beads selected from 2 colours.

Log in or register to write something here or to contact authors.