Group Actions, Colored Necklaces

Colored Necklaces

In the earlier necklace example, I chose a prime number for simplicity. When n has factors, some of the rotations split into smaller cycles.

Let a necklace have n beads, each assigned one of k colors. Let d divide n and rotate by n/d. We have now created n/d cycles of length d. The same thing might happen if we rotate by 7 times n/d, unless 7 divides d, and then something else happens. So we only use this cycle decomposition once for each integer < d and coprime to d. Do this for every divisor and you have the following cycle decomposition and color formula.

sum(d divides n) φ(d)*c_d^n/d

sum(d divides n) φ(d)k^n/d ÷ n

If we allow reflections, turning the necklace over, the additional permutations depend on the parity of n. A ring of length 2n contributes nc₂ⁿ + nc₁²c₂^n-1, while a ring of length 2n+1 contributes (2n+1)c₁c₂ⁿ. The latter formula was used when the necklace had 13 beads.

How many necklaces have 6 beads and 3 colors? Substitute 3 in the following to get 92.

(k⁶ + k³ + 2k² + 2k + 3k⁴ + 3k³) / 12