I came across one problem and I would like to find an answer. It is well-known how to calculate the number of fixed necklaces of length $n$ composed of $a$ types of beads $N(n,a)$. http://mathworld.wolfram.com/Necklace.html

So, let us consider very large necklaces with length $n$ and $n+1$. I wonder about the limit of $N(n+1,a)/N(n,a)$ for $n \to \infty$.

Actually I started from the finding the limit for the number of fixed necklaces for infinity. It seems to me that it should looks like a generating function for the total number of inversion in combinatorial theory and some factor which includes a power and factorial of $n$.

If you can make a computer experiment to see the numbers for very large $n$, it'll be a great opportunity to think about the numbers as well. Thank you for any help.


As given in the MathWorld article you linked to, the number of fixed necklaces of length $n$ with $a$ types of beads is


Using $\phi(d)\le d\le a$ and separating out the term for $d=1$, with $\phi(1)=1$, we have

$$ \begin{align} a^n\le nN(n,a)&\le a^n+\sum_{1\ne d|n}a^{n/d+1} \\ &\le a^n + \sum_{d=2}^na^{n/d+1} \\ &\le a^n + na^{n/2+1}\;, \end{align} $$

and thus

$$ \frac n{n+1}\frac{a^{n+1}}{a^n+na^{n/2+1}}\le\frac{N(n+1,a)}{N(n,a)}\le\frac n{n+1}\frac{a^{n+1}+(n+1)a^{(n+1)/2+1}}{a^n}\;. $$

The limit for $n\to\infty$ of both bounds is $a$, so it follows that the ratio tends to $a$ for $n\to\infty$.

  • $\begingroup$ Thank you, could you tell me why you separated out the term for d=1? Actually there are other divisors $d_i$ acording to the link at mathworld. In other words I am not sure why totient function dissapeared. Please correct me if I am wrong. $\endgroup$ – Mikhail G May 4 '12 at 4:24
  • $\begingroup$ @Mikhail: I separated out the term for $d=1$ because it's the dominating one, because its power of $a$ is at least twice that of the next-largest term. I announced what I used to make the totient function disappear: for the $d=1$ term, $\phi(1)=1$, and for the remaining terms, $\phi(d)\le a$ (which yields the $+1$ in the exponent of $a$). Of course there are other divisors, but I believe they've all been properly dealt with. $\endgroup$ – joriki May 4 '12 at 5:18

More a conjecture than an answer:

When the number of beads is large, one can intuition/conjecture (hopefully prove!) that the number of rotational coincidences gets proportionally negligible. If this is true (and numerical values seem to support this intuition, eg http://oeis.org/A000031 and http://oeis.org/A001869 ) the number of necklaces should tend to

$$N(n,a) \to \frac{a^n}{n}$$

(total number of linear arrangements divided by number of rotations) and hence:

$$\frac{N(n+1,a)}{N(n,a)} \to a\frac{n}{n+1} \approx a$$

  • $\begingroup$ I think this is the first time I saw the timestamp "just now" on two answers simultaneously :-) $\endgroup$ – joriki May 3 '12 at 19:14

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.