Problem
Consider necklaces consisting of (n=6) beads arranged in a circle. Each bead is colored from (q=6) available colors. Two necklaces are considered the same if one can be obtained from the other by a rotation (but not by reflection). No two adjacent beads may have the same color.
Question: How many distinct such necklaces are there?
The number of proper colorings of a cycle graph \(C_m\) with \(q\) colors is given by the chromatic polynomial
\[
P(C_m,q) = (q-1)^m + (-1)^m (q-1).
\]
Let \(G=C_6\) be the rotation group of order 6. A rotation by \(k\) beads decomposes the necklace into \(\gcd(k,6)=s\) repeating blocks. Colorings fixed by that rotation correspond to proper colorings of the cycle \(C_s\) with \(q=6\) colors.
Compute \(P(C_s,6)\) for all possible \(s\):
| 0 |
6 |
\((6-1)^6 + (6-1) = 5^6 + 5 = 15630\) |
| 1 |
1 |
\((6-1)^1 - (6-1) = 0\) |
| 2 |
2 |
\((6-1)^2 + (6-1) = 25 + 5 = 30\) |
| 3 |
3 |
\((6-1)^3 - (6-1) = 125 - 5 = 120\) |
| 4 |
2 |
\(30\) |
| 5 |
1 |
\(0\) |
By Burnside’s lemma, the number of distinct necklaces is
\[
\begin{aligned}
\frac{1}{|G|}\sum_{g\in G} |\text{Fix}(g)|
&= \frac{15630+0+30+120+30+0}{6} \\
&= \frac{15810}{6} \\
&= \boxed{2635}.
\end{aligned}
\]
