Counting necklaces
Choose how many beads and how many colours. The demo draws every different necklace. Two necklaces are the same if you can turn one round to get the other. Before you look at the count, guess it: with 6 beads and 2 colours there are 64 ways to colour numbered beads, and each necklace can sit in 6 positions. Is the answer 64 ÷ 6? Then tap a row of the table underneath to see how the exact count is found.
The Burnside table
| Move | Loops | Left alone |
|---|---|---|
| Total |
What's going on
Number the beads and there are (colours)beads colourings. Turning the necklace by one bead, two beads and so on gives the same necklace, so each necklace shows up several times in that list. The trouble is that it is not always the same number of times. Take 6 beads. The all-blue necklace shows up once. The necklace that alternates blue, orange shows up twice. Most show up once for every position. So dividing by the number of positions gives the wrong answer, and often not even a whole number.
Burnside's count fixes this. For each move, count the colourings that the move leaves looking exactly the same (the "Left alone" column). Add those counts and divide by the number of moves. The result is the number of different necklaces, exactly.
How to count the colourings a move leaves alone. Tap a row. The small picture shows where each bead goes. The beads fall into loops. Turn 6 beads by 2, for example: bead 1 goes to where bead 3 was, bead 3 to bead 5, and round again. The colouring looks the same afterwards only when every bead in a loop has the same colour. So you pick one colour per loop, and the count is (colours)loops. Turning n beads by r places makes gcd(n, r) loops.
Tick the box to let flips count as well. A flip turns the necklace over, as you can with a real one. Now there are twice as many moves and usually fewer necklaces. With 6 beads and 2 colours the count drops from 14 to 13: find the two necklaces that are mirror images of each other.