3
$\begingroup$

Let $p \geq 3$ be a prime number.

We consider $2p$ black beads and $2p$ blue beads (both indistinguishable).

How many unique necklaces of size $4p$, created from these beads, are there? (Consider only rotations.)

I need help with the Burnside's lemma.

(I have not found a similar question with a satisfactory answer).

The first approach (by the formula):

We will use the well-known formula.

The color multi-set is $B = \{1^{2p}, 2^{2p}\}$.

The number of such necklaces is: $$ \begin{align} N(B) &= \frac{1}{|B|} \sum_{d\mid\gcd(n_1 \dots n_k)} \binom{|B|/d}{n_1/d \dots n_k/d} \phi(d) \\ &= \frac{1}{4p} \sum_{d\mid\gcd(2p, 2p)} \binom{4p/d}{2p/d \; 2p/d} \phi(d) \\ &= \frac{1}{4p} \biggl( \binom{2}{1 \; 1}\phi(2p) + \binom{2p}{p \; p}\phi(2) + \binom{4}{2 \; 2}\phi(p) \biggr) \\ &= \frac{1}{4p} \biggl( 2(p-1) + \frac{(2p)!}{(p!)^2} + 6(p-1) \biggr) \\ &= \frac{8(p-1)(p!)^2+(2p)!}{4p(p!)^2} \end{align} $$

The second approach (by the Burnside's lemma):

The group size is $4p$.

The Id fixes $\binom{4p}{2p}$ elements.

The first rotation fixes $0$ elements.

The second fixes $2$ elements.

What's the pattern for $p$? We have to know how many beads we can color in a given rotation, then we can check whether it is even possible.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Temporarily ignoring the requirement that there must be an equal number of black and blue beads...

When rotating once, or indeed when rotating any number of times $k$ where $\gcd(k,4p)=1$ you will have that every bead must be the same. That is, we have one degree of freedom.

When rotating twice, or indeed when rotating any number of times $k$ where $\gcd(k,4p)=2$ you will have that every other bead must be the same. That is, we have two degrees of freedom.

When rotating four times, or any number of times $k$ where $\gcd(k,4p)=4$ you will have every fourth bead must be the same. That is, four degrees of freedom.

When rotating $k$ times where $\gcd(k,4p)=p$ you will have every $p$'th bead must be the same. And finally, when rotating $2p$ times, every $2p$'th bead (i.e. the bead opposite) must be the same and we'll have $2p$ degrees of freedom.

Noting that each of these will partition the set of beads into $1,2,4,p$ or $2p$ equally sized sets, and recalling that there must be an equal number of blue and black beads, we find that gcds of $1$ and $p$ are impossible to satisfy this (recalling that $p$ is prime greater than 2 and thus odd).

In the case of $2$ degrees of freedom, picking which color occurs first forces what color follows, and so there are $2$ options here. In the case of $4$ degrees of freedom, you pick two of the spaces for blue and the remainder must be block for $\binom{4}{2}=6$ options here.

Among the numbers $1,2,3,\dots,4p-1$ there are $p-1$ of these which correspond to a gcd of $2$ and $p-1$ of these which correspond to a gcd of $4$ (recalling that $4p$ and $0$ correspond to the identity rotation and are left out of our count for now).

In the case of the identity rotation, we simply pick which $2p$ of the spaces are blue, the rest are black, for a total of $\binom{4p}{2p} = \dfrac{(4p)!}{(2p)!(2p)!}$, similarly in the case of the $180^\circ$ rotation, we pick which $p$ of the first half of the beads are blue vs black for $\binom{2p}{p}$ cases

By my count then, applying (not-)burnside's lemma, we arrive at

$$\dfrac{1}{4p}\left(\binom{4p}{2p} +\binom{2p}{p}+ (p-1)\times 2 + (p-1)\times 6\right)$$

This was very close to what you had written, but it seems you missed the case of the identity rotation in your earlier attempt.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .