4

The problem of Necklaces is well-known, i.e "The number of fixed necklaces of length $n$ composed of $a$ types of beads $N(n,a)$" can be calculated: http://mathworld.wolfram.com/Necklace.html

Let us consider the limit $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$.
It is possible to show that the limit presents the result which looks like the generating function for inversion ( we may exclude one unimportant factor): $\frac {a^n} {n!}$ $\prod_{p=1}^n \frac {1-a^p} {1-a}$

For $n \to \infty$ we have $\prod_{p=1}^n N(p,a) \approx \frac {a^n} {n!}$ $\prod_{p=1}^n \frac {1-a^p} {1-a}$. Then, for eg please see theorem #1 http://www.cs.uwaterloo.ca/journals/JIS/VOL4/MARGOLIUS/inversions.pdf The generating function under theorem 1 looks like $\prod_{p=1}^n \frac {1-a^p} {1-a}$

So, a question appears, how to explain the influence of the symmetric group's properties for the particular case? In other words why and how the connection appears?

flag
Can you be more precise about the value of the limit? – Qiaochu Yuan Aug 1 at 18:56
@Qiaochu Yuan Thank you, I've added the approximation of the limit – Mikhail Gaichenkov Aug 1 at 19:06
I don't understand how this limit is equal to the claimed generating function. Can you elaborate? – Gjergji Zaimi Aug 3 at 3:26
@ Gjergji Zaimi For $n \to \infty$ we have $\prod_{p=1}^n N(p,a) \approx \frac {a^n} {n!}$ $\prod_{p=1}^n \frac {1-a^p} {1-a}$. Then, for eg please see theorem #1:cs.uwaterloo.ca/journals/JIS/VOL4/MARGOLIUS/… – Mikhail Gaichenkov Aug 3 at 17:17
The coefficient of $a^n/n!$ in $\prod N(p,a)$ is $\prod \varphi(p)$, but in the other side it is 1... – Gjergji Zaimi Aug 3 at 22:06
show 2 more comments

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.