The question asks to show that there are just five different necklaces which can be constructed from five white beads and three black beads.

There is a systematic example of how to solve this in the book:

  • Create an 8-gon for the 8 beads. This represents the necklaces of 8 beads.
  • The number of configurations of necklaces is $8 \choose 3$ including symmetries of necklaces.
  • Let $G$ be the group of symmetries for each necklace.
  • $|G| = 1 + 7 + 8 =$ (identity) + (7 rotations) + (4 side reflections) + (4 vertex reflections)
  • Count $|G_x|$, so the $g \in G$ that fix each $x \in X$, so $|G_x| =56+(4\times6)=80$.
  • Use $|Gx|=\frac{1}{|G|} \times |G_x|$
  • $|Gx| = 5$, the number of orbits, is the number of necklaces.

So basically I can solve the problem, but I have no intuition behind what is going on here. My question is why is the number of orbits equal the number of necklaces? What does the set $X$ represent? Is it the set of beads? Why is the number of orbits of $G$ on $X$ the number of necklaces?

  • 1
    $\begingroup$ How were orbits defined for you? Orbits can be thought of as equivalence classes under the group action of $G$ (the action of $G$ on the necklace can be thought of as permuting the necklace beads via the symmetries of the 8-gon). Orbits here correspond to classes of necklaces up to similarity via a group symmetry. In other words, it's a way of computing the number of distinct necklaces by filtering out necklaces that are actually the same under symmetry of the group. $\endgroup$ – Alex Wertheim Feb 10 '14 at 6:53
  • 1
    $\begingroup$ I think $X$ is the set of possible arrangements of the beads. So for example, if $B_{1}, \ldots, B_{8}$ were labeled beads, then if we represented our necklace as a string, a possible necklace in $X$ would be $(B_{2}, B_{1}, B_{7}, B_{5}, B_{8}, B_{4}, B_{6}, B_{3})$. Call this necklace $x$, for example. Then $Gx$ is indeed another necklace. Elements of $G$ are permutations corresponding to symmetries of the $8$-gon, so applying $G$ to $x$ permutes the beads, giving another necklace. $\endgroup$ – Alex Wertheim Feb 10 '14 at 7:10

The set $X$ represents all of the possible ways you could have naively strung the necklace. You can put the white beads on in ${8\choose 3}$ possible positions. But this overcounts the number of necklaces. For instance if I thread 5 black, then 3 white beads, this is equivalent to the necklace created by threading 3 white beads and then 5 black beads. They are the "same" necklace because I can rotate one into the other. Because I can rotate one into the other, these necklaces are in the same orbit. Consider the necklace in which I thread $2$ white beads, then $1$ black, then $1$ white, then $4$ black beads. No matter how I rotate or flip this new necklace, I cannot map it to the necklace with three consecutive white beads. So, it is in a distinct orbit. So, in this way each orbit represents necklaces that are equivalent under the action of $D_8$.

Your book has you work out the orbits using the Burnside's lemma, which may make it slightly more difficult to discern what is happening. To verify the book's result, write out explicitly all of the ways to thread the necklace placing one bead on at a time, then find explicitly which elements of $D_8$ take one necklace to another. Take note of the orbits: all of the necklaces in a given orbit will be the same.

  • $\begingroup$ Thanks, I understand! So basically the intuition necessary for the problem is to recognize that the number of orbits is the number of necklaces? Then to apply the orbit-stabilizer theorem? $\endgroup$ – Bobby Lee Feb 10 '14 at 7:20
  • $\begingroup$ I should have said Burnside's lemma, not the orbit-stabilizer theorem, but yes. $\endgroup$ – Bulberage Feb 10 '14 at 15:21

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.