3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$?) $\endgroup$ – Greg Martin Nov 11 '14 at 3:19
  • $\begingroup$ @GregMartin Yes, I meant $\phi \left( d \right)$. The question has been edited to reflect this correction. $\endgroup$ – Ryan Nov 11 '14 at 4:01
  • $\begingroup$ Your necklace already has an arbitrary number of beads. Did you mean to ask about generalizing to an arbitrary number of colors? $\endgroup$ – bof Nov 11 '14 at 5:29
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.