Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to count the number of necklaces, with $n$ beads in total, where the alphabet of beads is $\{1,\ldots,k\}$, and where the number of beads with color $i$ is $n_i$. For example, if $n=4$, and $n_1 = n_2 = 2$, the following necklaces are the only possible $$1122$$ $$1212$$

I have been able to find formulas for different variations of the problem, but not this one. If there is no nice formula, a generating function is always a nice compromise.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

There is a reasonably nice generating function coming from the Pólya enumeration theorem. It is given explicitly in, for example, this blog post: the number you want is the coefficient of $\prod r_i^{n_i}$ in

$$\frac{1}{n} \sum_{d | n} (r_1^{n/d} + ... + r_k^{n/d})^d \varphi \left( \frac{n}{d} \right).$$

share|improve this answer
    
What about a closed form solution, is that out of reach, or would posing certain constraints on the numbers change anything? –  utdiscant Aug 24 '12 at 4:27
    
What do you mean by closed-form solution? Expanding the above out using the multinomial theorem gives you a pretty terrible formula in terms of multinomial coefficients. Is that a closed-form solution? –  Qiaochu Yuan Aug 24 '12 at 4:28
    
The counting problem stated above will be part of a larger counting problem, which I will in the end want to approximate, for example using Stirlings formula. So "a pretty terrible formula in terms of multinomial coefficients" sounds like the right direction. –  utdiscant Aug 24 '12 at 4:31
    
Approximate in what regime? –  Qiaochu Yuan Aug 24 '12 at 4:32
    
What do you mean by "Approximate in what regime"? I am counting some combinations of cycles and spanning trees in cubic graphs, using the small-subgraph conditioning method. –  utdiscant Aug 24 '12 at 4:44

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.