How many different necklaces?
Tonight's idea
Thread four beads on a loop, each dark or light. With numbered positions there are \(2^4 = 16\) colourings. But a necklace can be turned, so colourings that are rotations of each other are one necklace. There are only 6.
For longer necklaces, do not list. For each rotation, count the colourings it fixes: those that look exactly the same afterwards.
Turn by 0 places: all 16. By 1 or 3 places: every bead must match its neighbour, so 2. By 2 places: opposite beads must match, so \(2^2 = 4\).
Number of necklaces = the average number of colourings fixed by a rotation. Here \(\dfrac{16 + 2 + 4 + 2}{4} = 6\).
Why? Count twice the pairs (rotation, colouring it fixes). By rotation: 24. By necklace: one with 4 versions has each fixed by 1 rotation; the striped one has 2 versions, each fixed by 2; a plain one has 1, fixed by all 4. Always 4 pairs. So \(24 = 4 \times\) (number of necklaces). This is Burnside's lemma.
Watch one: six beads, two colours
Turn by 2 places. Bead 1 moves to position 3, 3 to 5, and 5 to 1, so those three must share a colour. So must beads 2, 4, 6. Two groups, each free: \(2^2 = 4\) fixed colourings. A turn by \(r\) places makes \(\gcd(r, 6)\) groups.
| Turn by | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Groups | 6 | 1 | 2 | 3 | 2 | 1 |
| Fixed colourings | 64 | 2 | 4 | 8 | 4 | 2 |
The total is 84, and \(84 \div 6 = 14\) necklaces.
See all 14: mathdetours.com/demos/necklaces.html.
Your turn
- Three beads, three colours. Count the colourings fixed by each of the three rotations and find the number of necklaces.
- Five beads, two colours. Explain why a turn by 1, 2, 3 or 4 places fixes only 2 colourings. How many necklaces are there?
- Six beads, three colours. Redo the table from the example and find the number of necklaces.
- Now \(p\) beads, where \(p\) is prime, and \(c\) colours. Write a formula for the number of necklaces. The answer must be a whole number. What does that prove about \(c^p - c\)? Which theorem have you just proved?
Stretch: bracelets
A bracelet can also be flipped over, so there are 12 symmetries: the 6 rotations and 6 flips. Three flips have a mirror line through two opposite beads; three have it between beads. For six beads in two colours, count the colourings each flip fixes and average over all 12. Which two necklaces became one bracelet?
Answers
- Turn by 0: \(3^3 = 27\). By 1 or 2: all three beads must match, 3 each. \((27 + 3 + 3)/3 = 11\) necklaces.
- Because 5 is prime, repeating any of these turns carries bead 1 to every position, so all five beads must match: 2 colourings. \((32 + 2 + 2 + 2 + 2)/5 = 40/5 = 8\) necklaces.
- The groups are the same: 6, 1, 2, 3, 2, 1. Fixed colourings: \(3^6 = 729\), 3, 9, 27, 9, 3. Total 780, and \(780/6 = 130\) necklaces.
- Turn by 0 fixes \(c^p\). Each of the other \(p - 1\) turns fixes only the \(c\) one-colour necklaces, as in question 2. So there are \(\dfrac{c^p + (p-1)c}{p} = c + \dfrac{c^p - c}{p}\) necklaces. This is a whole number, so \(p\) divides \(c^p - c\). That is Fermat's little theorem.
Stretch. Mirror through two beads: those two are free and the other four form 2 mirror pairs, so \(2^4 = 16\). Mirror between beads: 3 mirror pairs, \(2^3 = 8\). Total \(84 + 3 \times 16 + 3 \times 8 = 156\), and \(156/12 = 13\) bracelets. Going round, dark-dark-light-dark-light-light and dark-dark-light-light-dark-light are different necklaces, but each is the other flipped over.