# Comparison of two very large necklaces

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

$$N(n,a)=\frac1n\sum_{d|n}\phi(d)a^{n/d}\;.$$

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

-
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. –  Mikhail G May 4 '12 at 4:24
@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. –  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$$

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