# Number of different necklaces using $m$ red and $n$ white pebbles

It's very well known that the number of different necklaces using two colors of pebbles (Two necklaces which can be obtained from one another by rotation are considered the same), is exactly $\frac{1}{n}(\sum_{d|n} \phi(\frac{n}{d})2^d)$. What about the answer to this question:

How many different (as defined above) necklaces are there using exactly $m$ red and $n$ white pebbles?

-
At least if $\gcd(n.m)=1$, the answer is simply $\frac1{m+n}{m+n\choose n}$. –  Hagen von Eitzen Sep 28 '12 at 18:36
Yes, you're right. But things get different when they are not coprime. –  Goodarz Mehr Sep 28 '12 at 19:28

The number of necklaces that are symmetric after rotation by $i$ is given by ${\frac{n+m}{\mathrm{ord}(i)} \choose \frac{m}{\mathrm{ord}(i)}}$ if $\mathrm{ord}(i)$ divides $m$ and $0$ otherwise (here $\mathrm{ord}(i)$ is the additive order of $i$ in $\mathbb{Z}_{m+n}$).

To see this, label the cells $0,1,\ldots,n+m-1$. We "populate" the first $\frac{n+m}{\mathrm{ord}(i)}$ cells $0,1,\ldots,\frac{n+m}{\mathrm{ord}(i)}-1$, which determines the rest of the necklace through its symmetry. I.e., if we place a bead in cell $x$, to satisfy the symmetry, we must also place it in the $\mathrm{ord}(i)$ cells $x,x+i,x+2i,\ldots$ (working modulo $n+m$), thereby introducing $\mathrm{ord}(i)$ copies of that symbol.

Hence Burnside's Lemma implies the total number of necklaces is:

$\frac{1}{m+n} \sum_{{i \in \mathbb{Z}_{m+n}} \atop {\mathrm{ord}(i) \text{ divides } m}} {\frac{n+m}{\mathrm{ord}(i)} \choose \frac{m}{\mathrm{ord}(i)}}.$

We can make the sum purely numerical by using the identity $\mathrm{ord}(i)=\frac{n+m}{\mathrm{gcd}(i,n+m)}$ when $i \neq 0$ (and $\mathrm{ord}(0)=1$).

-