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
    What about a closed form solution, is that out of reach, or would posing certain constraints on the numbers change anything?2012-08-24
  • 0
    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?2012-08-24
  • 0
    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.2012-08-24
  • 0
    Approximate in what regime?2012-08-24
  • 0
    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.2012-08-24
  • 0
    I mean how large is $n$ relative to $k$ and the $n_i$?2012-08-24
  • 0
    There is no (non-trivial) bound on how large $k$ and $n_i$ can be, as far as I can see right now.2012-08-24
  • 0
    That's not what I mean. I mean is $n$ some very large number and $k$ very small compared to it? Or is $k$ approximately as large as $n$ and the $n_i$ are very small? Or something else?2012-08-24
  • 0
    I am sorry I was not clear enough. There is no relative bounds like that either.2012-08-24
  • 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