Burnside's Formula to determine rotationally indistinguishable necklaces

Given M beads on a string and N colours, determine using Burnside's formula, the number of rotationally indistinguishable necklaces, where the group acting is a cyclic group. Any tips/ hints would be appreciated, thanks.

-
I'd start by looking at Burnsides's formula. –  Graphth Oct 24 '11 at 16:19

If we ignore rotations, there are $N^M$ different necklaces, but we have an action of the cyclic group $C_M$ on our necklaces, and two necklaces are indistinguishable if and only if they lie in the same orbit under this action. Therefore, we are trying to count the number of orbits.

Burnside's formula says that the number of orbits is equal to the average size of the number of elements fixed by each group element. In symbols,

$$\displaystyle\left|X/G\right|=\frac{1}{\left|G\right|}\sum_{g\in G} \left|X^g\right|$$

where $X^g=\{x\in X \mid gx=x \}$.

To apply the formula, we need to be able to figure out the number of necklaces fixed by any particular element of the cyclic group. I will work out an example, which should be enough to see how things go in the general case.

Suppose that we have six beads, so that we have an action of $C_6$, which we can represent by $\{0,1,2,3,4,5\}$ under addition mod 6. If we take $g=4$, a necklace will be fixed by the action of $g$ if and only if shifting it over by $4$ does not change the layout of the necklace. This is the same as saying that the necklace has a pattern with periodicity 4. However, if we have six beads, then the periodicity of any pattern must divide 6 (as well as dividing 4), and therefore the periodicity must divide $\operatorname{gcd}(6,4)=2$. How many necklaces have periodicity 2? We can select any combination for the first two beads, and this determines the rest of the necklace. Therefore, there are $N^2$ patterns with periodicity 2. Doing this for all the other elements in the group (but noting that for the identity element, when we say periodicity 0 we mean that we are putting no restrictions), we see there are

$$\frac{N^6+N+N^2+N^3+N^2+N}{6}$$ necklaces up to rotation.

It may be a fun exercise to verify directly that this is indeed an integer for every $N$.

-
Thank you so much! –  user17595 Oct 24 '11 at 21:42
$$\frac{1}{M}\sum\limits_{i=1}^m N^{\gcd(m,i)}$$ where $i\in\{1,2,\ldots,m\}$.