3
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ Can you be more precise about the value of the limit? $\endgroup$
    – Qiaochu Yuan
    Commented Aug 1, 2012 at 18:56
  • $\begingroup$ @Qiaochu Yuan Thank you, I've added the approximation of the limit $\endgroup$
    – Mikhail Gaichenkov
    Commented 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$
    – Gjergji Zaimi
    Commented 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$
    – Mikhail Gaichenkov
    Commented 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$
    – Gjergji Zaimi
    Commented Aug 3, 2012 at 22:06

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .