# Counting necklaces with a fixed number of each bead

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.

-

## 1 Answer

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).$$

-
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