3
$\begingroup$

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.

2 Answers 2

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

  • 0
    @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.2012-05-04
0

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$

  • 0
    I think this is the first time I saw the timestamp "just now" on two answers simultaneously :-)2012-05-03