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):


*

*Black and white beads on a circle

*Beads on the circle

*Number of restricted ways to two-color a necklace
 A: It's based on Burnside's lemma.
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.$$
