Necklace problem with Burnside Lemma

Question

How many necklaces can be made with two red beads, two green beads, and four violet beads?(8 total)

Using Burnside lemma is complicated for me due to my lack of understanding of the lemma. I want to know the method step-by-step.

Answer 1

To start with:

We have $\frac{8!}{2!2!4!} = 420$ permutations of the eight beads. We will be arranging them around an 8-bead item, which means we need to use the dihedral group $D_{16}$ and its various actions.

There are seven conjugacy classes among the elements of this group, we'll consider them in turn.

• the identity action does nothing; all 420 possibilities remain unchanged under this action
• the single $1/2$ rotation steps everything around four beads. This keeps things of the form $abcdabcd$ unchanged, so neclackes like $VVRGVVRG$ or $GVRVGVRV$ count for this. There are 12 such necklaces.
• the two $1/4$ rotations steps everything around two beads; this action doesn't leave any entries unchanged, since they would have to be of the form $abababab$ and we only have two red beads.
• the two $1/8$ rotations steps everything around one bead; this action also does not leave any entries unchanged, since we have more than one color of bead.
• the two $3/8$ rotations steps everything around three beads; this action also also doesn't leave any entries unchanged, since we have more than one color of bead.
• the four reflections across a line through beads flips things back and forth so that two beads stay put. Necklaces of the form $abcdedcb$ remain unchanged through this; since we only have even counts of beads, $a = e$ must be true. We're left with 12 entries such as $VRGVVVGR$.
• the four reflections across a line between beads flips things back and forth so no beads stay put. These look like $abcddcba$, and there's 12 such entries, such as $VRGVVGRV$

Now, applying Burnside's Lemma, there are

$$\frac{1\cdot420 + 1\cdot12 + 2\cdot0 + 2\cdot0 + 2\cdot0 + 4\cdot12 + 4\cdot12}{1+1+2+2+2+4+4} = \frac{528}{16} = 33$$

distinct necklaces.

Presented below is the full list:

These 20 are completely asymmetrical:

GGRRVVVV GGRVRVVV GGRVVRVV
GGRVVVRV GGVRRVVV GGVRVRVV
GRGRVVVV GRGVRVVV GRRVGVVV
GRRVVGVV GRRVVVGV GRVGRVVV
GRVGVRVV GRVGVVRV GRVGVVVR
GRVRVGVV GRVRVVGV GRVVGVRV
GRVVRVGV GVGVRRVV

these six are fixed under a reflection that passes between beads:

GRVVVVRG GVRVVRVG GVVRRVVG
RGVVVVGR VRGVVGRV RVGVVGVR

these five are fixed under a reflection that passes through two beads:

RGVVRVVG VRGVVVGR GRVVGVVR
VVRGVGRV VGVRVRVG

Finally there is one that is fixed under rotation GRVVGRVV and one that is fixed under both rotation and through-reflection GVRVGVRV

Answer 2

We may as well deploy PET here since we need the cycle index $Z(D_8)$ of the dihedral group $D_8$ of order $16$ to apply Burnside. We compute and average the number of assignments of colors to the eight slots fixed by permutations from each conjugacy class in $D_8$, taking into account the order of the class. This means the assignment is constant on the cycles, so we can place exactly one color in the slots on a given cycle, substituing $a_d$ from the index with $R^d + G^d + V^d,$ which is PET.

Consulting the following fact sheet on necklaces and bracelets we get for the cycle index of the dihedral group $D_8$

$$Z(D_8) = \frac{1}{16} a_1^8 + \frac{1}{4} a_1^2 a_2^3 + \frac{5}{16} a_2^4 + \frac{1}{8} a_4^2 + \frac{1}{4} a_8.$$

We seek $$[R^2 G^2 V^4] Z(D_8; R+G+V).$$

Here we assume that the OP asks for the full symmetry i.e. dihedral, which means that the label to use is bracelet. Working through the five terns in the cycle index we obtain

• $\frac{1}{16} a_1^8$ $$[R^2 G^2 V^4] \frac{1}{16} (R+G+V)^8 = \frac{1}{16} {8\choose 2,2,4}$$
• $\frac{1}{4} a_1^2 a_2^3$ $$[R^2 G^2 V^4] \frac{1}{4} (R+G+V)^2 (R^2 + G^2 + V^2)^3 \\ = [R^2 G^2 V^4] \frac{1}{4} (R^2 + G^2 + V^2) (R^2 + G^2 + V^2)^3 \\ = [R^2 G^2 V^4] \frac{1}{4} (R^2 + G^2 + V^2)^4 \\ = [R G V^2] \frac{1}{4} (R + G + V)^4 = \frac{1}{4} {4\choose 2,1,1}.$$
• $\frac{5}{16} a_2^4$ $$[R^2 G^2 V^4] \frac{5}{16} (R^2 + G^2 + V^2)^4 = \frac{5}{16} {4\choose 2,1,1}.$$
• $\frac{1}{8} a_4^2$ $$[R^2 G^2 V^4] \frac{1}{8} (R^4 + G^4 + V^4)^2 = 0.$$
• $\frac{1}{4} a_8$ $$[R^2 G^2 V^4] \frac{1}{4} (R^8 + G^8 + V^8) = 0.$$

We thus get for our answer

$$\frac{1}{16} {8\choose 2,2,4} + \frac{9}{16} {4\choose 2,1,1} = \bbox[5px,border:2px solid #00A000]{33.}$$