1
$\begingroup$

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?

  • 0
    Yes, you're right. But things get different when they are not coprime.2012-09-28

1 Answers 1

1

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