MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

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 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|cite|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 – Mikhail Gaichenkov Aug 3 '12 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 '12 at 22:06

Your Answer


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

Browse other questions tagged or ask your own question.