Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.