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?

  • $\begingroup$ Can you be more precise about the value of the limit? $\endgroup$ Aug 1, 2012 at 18:56
  • $\begingroup$ @Qiaochu Yuan Thank you, I've added the approximation of the limit $\endgroup$ Aug 1, 2012 at 19:06
  • $\begingroup$ I don't understand how this limit is equal to the claimed generating function. Can you elaborate? $\endgroup$ Aug 3, 2012 at 3:26
  • $\begingroup$ @ 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/inversions.pdf $\endgroup$ Aug 3, 2012 at 17:17
  • 2
    $\begingroup$ The coefficient of $a^n/n!$ in $\prod N(p,a)$ is $\prod \varphi(p)$, but in the other side it is 1... $\endgroup$ Aug 3, 2012 at 22:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.