How many necklaces are there with a known number of beads of each color? [duplicate]

I suspect that the answer to my question might be trivially found in the Wikipedia page for the combinatorial concept of a necklace, but I'm finding that page very hard to understand.

Suppose I have $N$ beads in $k$ available colors, where I've fixed the number of beads of each color. That is, I specify a particular $k$-tuple of nonnegative integers $(n_1, n_2, \dots, n_k)$ such that $\sum \limits_{i=1}^k n_i = N$, where $n_i$ ($i = 1, \dots, k$) is the number of beads of the $i$th color. Then how many (fixed) necklaces can be made from these beads? I.e. how many length-$n$ strings are there over an alphabet of size $k$ if we fix the total number of appearances of each character in the alphabet and we identify strings that are related by circular shifts?

If I understand the Wikipedia article correctly, the first equation gives the total number of necklaces if we only fix the number $k$ of available colors, but sum over all possible specific $k$-tuples that represent a particular partition of the beads into the different colors. But what if we know the exact partition? I don't understand the second equation on the Wikipedia page, because I don't understand what they mean by a "necklace of length $n$ with exactly $k$ different colored beads", or how this is different from the situation that the previous equation considers.

(If it makes things easier, you can feel free to assume that the $n_i$ are all positive rather than nonnegative, so that $k$ represents the number of colors that actually appear rather than the number of colors that are available. This changes the number of valid $k$-tuples, but I don't think it really matters much if we're specifying a particular $k$-tuple.)

Solution 1:

The number of linear arrangements of beads in $k$ colors distributed like $(n_1,\dots,n_k)$ is simply the multinomial coefficient $$\binom{n}{n_1,\dots,n_k},$$ where $n=n_1+\dots+n_k$. For circular arrangements, the answer is instead $$ \boxed{\frac1{n}\sum_{d|\gcd(n_1,\dots,n_k)}\varphi(d)\binom{n/d}{n_1/d,\dots,n_k/d},} $$ where $\varphi$ is the totient function.

This can be proven using Burnside's lemma. Namely, when enumerating necklaces that have rotational symmetry by $(360/d)^\circ$ degrees, we see they must consist of $d$ identical linear sections of beads of length $n/d$, which can be chosen in $\binom{n/d}{n_1/d,\dots,n_k/d}$ ways. For this to be possible, all of the bead counts must be divisible by $d$, hence the $d\mid \gcd(n_1,\dots,n_k)$ condition. Finally, for each divisor $d$ of $\gcd(n_1,\dots,n_k)$, there are $\varphi(d)$ rotations with the same number of symmetries as rotation $(360/d)^\circ$. For example, when $d=12$, the equivalent symmetries are $30^\circ,150^\circ,210^\circ,$ and $330^\circ$.