Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Can you be more precise about the value of the limit? –  Qiaochu Yuan Aug 1 '12 at 18:56
    
@Qiaochu Yuan Thank you, I've added the approximation of the limit –  Mikhail Gaichenkov Aug 1 '12 at 19:06
    
I don't understand how this limit is equal to the claimed generating function. Can you elaborate? –  Gjergji Zaimi Aug 3 '12 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/inversions.pdf –  Mikhail Gaichenkov Aug 3 '12 at 17:17
2  
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 '12 at 22:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.