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.

Solution 1:

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$.

Solution 2:

The formula involving the GCD may also be proved by the Polya Enumeration Theorem (PET). We'll use $N$ for the number of beads and $M$ for the colors. Essentially we have the cyclic group $C_N$ acting on $N$ slots and there are $M$ different colors. This means that the desired value can be obtained through the cycle index of said group, giving $$Z(C_N)(Q_1+Q_2+\cdots +Q_M)_{Q_1=1, Q_2=1, \ldots Q_M=1}.$$ Now the cycle index of the cyclic group is given by $$Z(C_N) = \frac{1}{N} \sum_{d|N} \varphi(d) a_d^{N/d}.$$ Therefore the substituted index is $$\frac{1}{N} \left.\sum_{d|N} \varphi(d) (Q_1^d+Q_2^d+\cdots+Q_M^d)^{N/d}\right|_{Q_1=1, Q_2=1, \ldots Q_M=1} = \frac{1}{N} \sum_{d|N} \varphi(d) M^{N/d}.$$ Now the Euler totient applied to the divisors of $N$ is a classification of the integers $n$ where $1\le n\le N$ according to their greatest common divisor $d$ with $N$, and if that divisor is $d$ then there are $\varphi(N/d)$ values with that divisor, so this is $$\frac{1}{N} \sum_{d|N} \varphi(N/d) M^d = \frac{1}{N} \sum_{n=1}^N M^{\gcd(N,n)}.$$ Here is a MSE link to a chain of PET computations.

Addendum, Nov 2019. With this computation we actually don't need PET and the Burnside lemma with the cycle index substitution $a_d = M$ instantly yields

$$\frac{1}{N} \sum_{d|N} \varphi(d) M^{N/d}.$$

This is because for colors to be constant on a cycle (they must be if they are fixed by the corresponding permutation) we have exactly $M$ choices and hence $a_d^{n/d}$ which has $n/d$ cycles of length $d$ contributes $M^{n/d}.$ For the alternate form we may write

$$\frac{1}{N} \sum_{n=1}^N M^{\gcd(N,n)} = \frac{1}{N} \sum_{d|N} \sum_{n=1 \atop \gcd(N,n)=d}^N M^{\gcd(N,n)} \\ = \frac{1}{N} \sum_{d|N} \sum_{n=1 \atop \gcd(N,n)=d}^N M^d = \frac{1}{N} \sum_{d|N} M^d \sum_{n=1 \atop \gcd(N,n)=d}^N 1 \\ = \frac{1}{N} \sum_{d|N} M^d \sum_{m=1 \atop \gcd(N,md)=d}^{N/d} 1 = \frac{1}{N} \sum_{d|N} M^d \sum_{m=1 \atop \gcd(N/d,m)=1}^{N/d} 1 = \frac{1}{N} \sum_{d|N} M^d \varphi(N/d).$$