# Number of Necklaces of Beads in Two Colors

I was reading this paper, and came across an equation which gives an expression for the number of necklaces of beads in two colors, with length n.

$Z_n = \dfrac{1}{n} \displaystyle \sum \limits_{d \mid n} \phi \left( d \right) 2^{n/d}$

The author says that this equality is well known, and cites Golomb and Riordan as examples. However, I do not have access to these cited works.

I was curious, what is the proof of this equality? Is it generalizable to necklaces with an arbitrary number of colors?

Related Questions (that do not answer my question explicitly):

• It has something to do with sorting the necklaces by whether they're periodic at all, and if so by their least period. (Do you mean $\phi(d)$?) – Greg Martin Nov 11 '14 at 3:19
• @GregMartin Yes, I meant $\phi \left( d \right)$. The question has been edited to reflect this correction. – Ryan Nov 11 '14 at 4:01
• Your necklace already has an arbitrary number of beads. Did you mean to ask about generalizing to an arbitrary number of colors? – bof Nov 11 '14 at 5:29

The rotation group $G$ of the necklace is a cyclic group of order $n$. Let $\alpha$ be a generator of $G$, i.e. a rotation of order $n$, such as the rotation by one bead in the positive direction. Thus $G=\{\alpha^1,\alpha^2,\dots,\alpha^n\}$ where of course $\alpha^n$ is the identity permutation.
For $k\in\{1,2,\dots,n\}$, the rotation $\alpha^k$ is a permutation of order $\frac n{(k,\,n)}$ where $(k,\,n)$ is the greatest common divisor of $k$ and $n$; it partitions the set of $n$ beads into $(k,\,n)$ orbits, each of size $\frac n{(k,\,n)}$.
A coloring is invariant under $\alpha^k$ if and only if it's constant on each orbit; thus, with $2$ colors, the number of invariant colorings for $\alpha^k$ is $2^{(k,\,n)}$. According to Burnside's lemma, the number of indistinguishable colorings is obtained by averaging the number of invariant colorings over all elements of the group; thus $$Z_n=\frac1n\sum_{k=1}^n2^{(k,\,n)}.$$ All that remains is to verify that $$\sum_{k=1}^n2^{(k,\,n)}=\sum_{d|n}\phi(d)2^{n/d}.$$ This is true because $$\phi(d)=|\{k\in\{1,\dots,n\}:(k,\,n)=\frac nd\}|$$ or, equivalently, $$\phi(\frac nd)=|\{k\in\{1,\dots,n\}:(k,\,n)=d\}|.$$ For an arbitrary number $c$ of colors, just replace $2$ with $c$ in all the formulas; the number of indistinguishable colorings is $$\frac1n\sum_{d|n}\phi(d)c^{n/d}.$$ When $c=1$ this reduces to the familiar identity $$\sum_{d|n}\phi(d)=n.$$