Number of distinct necklaces with $12$ beads, each bead red or blue (rotations don't count!)

Question

Suppose I want to form a 12-bead necklace such that each bead is either red or blue. Necklaces which differ by a rotation are considered the same and beads of the same color are indistinguishable. How may distinct necklaces can I make in this way?

---

My approach to this problem is as follows. We only have to consider the cases where the number of red beads is between $0$ and $6$, as the remaining cases are symmetric. If the number of red beads is $0,1,2$ the number of necklaces is easily found to be $1,1,6$, respectively. For $3$ to $6$ read beads the counting becomes more difficult. So lets suppose we have $k$ red beads (thus $12-k$ blue beads). Starting at some red bead and moving clockwise, let the number of blue beads between consecutive red beads be $x_1,x_2,...,x_k$ (these are non-negative integers). We need $x_1+...+x_k=12-k$ and thus the number of necklaces with $k$ read beads is the number of sets (recall the elements of a set are unordered) of $k$ nonegative integers with sum $12-k$, which we will call $f(k)$. So the answer to the problem is sum from $k=0$ to $5$ of $2f(k)$, plus $f(6)$. The problem is finding $f(k)$. Perhaps this is the wrong approach?

Answer 1

You should use Burnside's lemma.

There are $4$ rotations of order $12$. Each of these stabilizes $2$ colorings.

There are $2$ rotations of order $6$. Each of these stabilizes $4$ colorings.

There are $2$ rotations of order $4$. Each of these stabilizes $8$ colorings.

There are $2$ rotations of order $3$. Each of these stabilizes $16$ colorings.

There is $1$ rotation of order $2$. Each of these stabilizes $64$ colorings

There is $1$ rotation of order $1$. It stabilizes the $4096$ colorings.

We now apply Burnside and obtain:

$\frac{4\cdot2+2\cdot4+2\cdot8+2\cdot16+1\cdot64+1\cdot 4096}{12}=352$ necklaces.

Answer 2

Polya's theorem is more powerful than Burnside's theorem, because you then don't have to consider how the symmetry group acts on colorings, instead you only have to consider how it acts on the structure that is colored, which is much easier.

This works as follows. For each element of the rotation group, you calculate how repeatedly applying that element to the neclace will divide the beads into groups that are mapped to each other. E.g. if we rotate by $2 \pi/6$ then this maps each bead to its second neighbor, therefore if we repeatedly apply this mapping we split the neclace into two sets of 6 beads. We then say that under the action of that element of the rotation group we have two orbits of length 6. What you then do is write down the term:

$$T_{1}^{n_1}T_{2}^{n_2}T_{3}^{n_3}\ldots$$

when there are $n_k$ orbits of length $k$. So, for the case of the rotation by $2\pi/6$, you have the term $T_6^2$. Adding up all the terms for all the elements of the group and dividing by the number of elements in the group yields the cycle index polynomial of the group. Then we can do a weighted counting of colorings such that the weight is the product of some arbitrary function $w$ of each color of each bead. Polya's theorem says that you have to take the cycle index polynomial and replace $T_i$ by the sum of the ith powers of the weights associated with each color.

The cycle index polynomial for this problem is given by:

$$\frac{1}{12}\left[T_{1}^{12} + T_{2}^6 + 2 T_{3}^4 + 2 T_{4}^3 + 2 T_{6}^2 + 4 T_{12}\right]$$

If we give each color a weight of 1, then we can replace the $T_n$ by the total number of colors, so you can put $T_i = 2$. But you can also give a red bead a weight of x, then you get a polynomial (which is called a generating function). The coefficient of $x^r$ is then the total number of colorings with r red beads. To do this, you need to put:

$$T_{k} = 1 + x^k$$

The generating function is thus given by:

$$S(x) = \frac{1}{12}\left[\left(1+x\right)^{12} +\left(1+x^2\right)^6 + 2 \left(1+x^3\right)^4 + 2 \left(1+x^4\right)^3 + 2 \left(1+x^6\right)^2 + 4 \left(1+x^{12}\right)\right]$$

E.g., the coefficient of $x^6$ is 80, so there are 80 necklaces with exactly 6 red and 6 blue beads.