2
$\begingroup$

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 Answers 1

3

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

  • 0
    Okay. Then I don't think you can do substantially better than the multinomial coefficients. (This is not so bad a formula if the number of divisors of $n$ is small, but in general...)2012-08-24