Comparison of two very large necklaces

Question

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.

Answer 1

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

Answer 2

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