# Rotation of necklaces

The number of fixed necklaces of length $$n$$ with $$a$$ types of beads is $$N(n,a)=\frac1n\sum_{d|n}\phi(d)a^{n/d}\;.$$ It is clear intuitively that the number of rotational coincidences gets proportionally negligible for the large number of beads. How to prove it? Any estimation to calculate?

• Do you know Burnside's lemma? – cansomeonehelpmeout Oct 25 '18 at 19:34
• Yes, I hear about it, thank you, but how to apply it? It results in the number of fixed necklaces. – Mikhail Gaichenkov Oct 25 '18 at 19:48
• What exactly are you trying to prove? $\frac{\phi(1)a^n}{n N(n,a)} \to 1$? – Peter Taylor Oct 26 '18 at 10:19
• Thank you. The question come from comparison of 2 necklaces. Could you have a look at the comments by leonbloy please? math.stackexchange.com/questions/140504/… – Mikhail Gaichenkov Oct 26 '18 at 17:38

A necklace that has no rotational symmetry is called a primitive or aperiodic necklace, or a Lyndon word (if written as a word by taking the lex-smallest rotation.) The number of primitive necklaces is given by almost the same formula as the one you give for the number of necklaces, but with Euler's $$\phi$$ replaced by the Mobius function $$\mu$$ (see Wikipedia): $$\frac{1}{n} \sum_{d |n } \mu(d) a^{n/d}.$$
Intuitively, we would expect that for large $$n$$ a random necklace would be almost surely be primitive, since there would have to be a large number of coincidences to find a rotational symmetry. To prove this, just take the ratio
$$\frac{\frac{1}{n} \sum_{d |n } \mu(d) a^{n/d}}{ \frac{1}{n} \sum_{d |n } \phi(d) a^{n/d}} = \frac{a^n + O(a^{n-1}) }{ a^n + O(a^{n-1}) }$$
since the highest order terms in both polynomials corresponds to $$d=1$$, and $$\mu(d) = \phi(d) = 1$$. Then the limit as $$n \rightarrow \infty$$ is $$1$$.