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?

  • $\begingroup$ Do you know Burnside's lemma? $\endgroup$ – cansomeonehelpmeout Oct 25 '18 at 19:34
  • $\begingroup$ Yes, I hear about it, thank you, but how to apply it? It results in the number of fixed necklaces. $\endgroup$ – Mikhail Gaichenkov Oct 25 '18 at 19:48
  • $\begingroup$ What exactly are you trying to prove? $\frac{\phi(1)a^n}{n N(n,a)} \to 1$? $\endgroup$ – Peter Taylor Oct 26 '18 at 10:19
  • $\begingroup$ 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/… $\endgroup$ – 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$.


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.