3
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ There are other questions on this site where Burnside lemma has been explained in detail. Can you take one of them and apply to your problem? See math.stackexchange.com/questions/3810598/… as an example. $\endgroup$ – Math Lover Sep 15 '20 at 14:43
  • $\begingroup$ I can apply the lemma with two colors of beads, but when it comes to three colors, I cannot trust my equations because every time I do, the answer keeps changing. $\endgroup$ – wormname Sep 15 '20 at 14:46
  • 3
    $\begingroup$ Can you show one of your attempts? $\endgroup$ – Math Lover Sep 15 '20 at 14:49
  • $\begingroup$ simply writing out all possibilities is a lot of work, but maybe you should start doing it anyway because often only in the process of doing something the stupid way you figure out a way to do it smarter. Don't let the fact that someone solved it more elegantly 100 years ago intimidate you - this is the type of problem you can solve yourself without any prior knowledge, which is much more satisfying and also more likely to help you with similar problems in the long run. $\endgroup$ – Vincent Sep 15 '20 at 15:18
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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