3
$\begingroup$

How many necklaces can be made with two red beads, two green beads, and two violet beads?

I'm trying to solve this with Burnside's Lemma however I'm stuck. Here's what I've got so far:

Let $S=\{$necklace of length 6 with 2 read, 2 green and 2 violet$\}$, $|S|=\frac{6!}{2!2!2!}=90$, let $G=\mathbb{D}_{6}$, $|G|=2*6=12$.

Now let $g\in G$, $g=e\Rightarrow |fix(g)|=|S|=90$ since $e$ sends any $s$ back to itself.

For when $g\neq e$, if $g$ is any one of the rotations by $\frac{\pi}{6}$ clockwise, what should I do from here? I intuitively know that not all rotations sends $s$ back to itself and that different configuration of the color beads also plays a role, yet I don't have a clear route to follow.

And what about flips?

Thanks for any help!

$\endgroup$
  • $\begingroup$ There are many things $g$ can be if it's not the identity map. There are five nontrivial rotations, and six reflections. $\endgroup$ – arctic tern Nov 16 '16 at 13:40
  • $\begingroup$ So for rotations, if $g=r,r^{2},r^{4},r^{5}$, $|fix(g)|=0|$; if $g=r^{3}$, there are $3!$ ways to arrange 1 red 1 green 1 violet beads in a three-bead-lineup, and $2*2*2$ ways to swap the two identical beads of same color, hence $|fix(g)|=48$? $\endgroup$ – Allen Ai Nov 16 '16 at 13:57
  • $\begingroup$ Swapping two beads of the same color does not change the necklace. (If you were computing the stabilizer of such a necklace within the full group of permutations $S_6$, then it would indeed be $\Bbb Z_2\times\Bbb Z_2\times\Bbb Z_3$, but that's not what we're doing here. We're just counting necklaces.) $\endgroup$ – arctic tern Nov 16 '16 at 14:17
  • $\begingroup$ True true. Then $|fix(r^{3})|$ should be $3!$ instead. How should I approach the flips? Since all three flips across two vertices are essentially the same and all three flips across the center of two edges are, frankly, the same? Should I just calculate $|fix(g)|$ for one of them and count them three times each? $\endgroup$ – Allen Ai Nov 16 '16 at 14:19
  • $\begingroup$ Yes, count Fix(g) for one of them and then count it thrice. $\endgroup$ – arctic tern Nov 16 '16 at 14:21
4
$\begingroup$

Here are the elements of the dihedral group of order twelve:

  • One identity map.
  • Two rotations by a 1/6th turn (clockwise and counterclockwise).
  • Two rotations by a 1/3rd turn (clockwise and counterclockwise).
  • One rotation by a 1/2 turn.
  • Three reflections across lines through two vertices.
  • Three reflections across lines through two edges.

For each type of element, look at its "cycle type" as a permutation of the vertices, or in other words the orbit (technically the orbit of the cyclic group it generates).

For instance, let's consider a 1/6th turn. Imagine we have a necklace which is a fixed point of this rotation. The rotation slides the first bead to the second bead position, so they must be the same color, but by the same token it slides the second bead to the third bead position and so on, which implies the beads must all be the same color. This is of course not possible, so $0$ fixed points.

$\endgroup$
6
$\begingroup$

I upvoted the first answer but I would like to show how to compute the cycle index $Z(D_6)$ of the dihedral group $D_6$ and apply the Burnside lemma and the Polya Enumeration Theorem to this problem. Observe that the OEIS uses the convention of refering to rotational symmetry as a necklace and as a bracelet when reflectional symmetry is included, so we are working with a bracelet here.

We need to enumerate and factor the twelve permutations that contribute to $Z(D_6).$

There is the identity, which contributes $$a_1^6.$$ The two rotations by a distance of one and five contribute $$2 a_6.$$ The two rotations by a distance of two or four contribute $$2 a_3^2.$$ Finally the rotation by a distance of three contributes $$a_2^3.$$

There are three reflections about an axis passing through opposite vertices, giving $$3 a_1^2 a_2^2$$

and three reflections about an axis passing through the midpoints of opposite edges, giving $$3 a_2^3.$$

This finally yields the cycle index $$Z(D_6) = \frac{1}{12} \left(a_1^6 + 2a_6 + 2a_3^2 + 3a_1^2 a_2^2 + 4a_2^3\right).$$

Do the Burnside calculation first. We have three colors and two instances of each. The colors must be constant on the cycles. We now proceed to count these. We get for $a_1^6$ the contribution ${6\choose 2,2,2}.$ There are no candidates for $a_6$ (we do not have six instances of a color). We do not have three instances either, so zero for $a_3^2.$ For $a_1^2 a_2^2$ we must choose a pair of colors for the two-cycles, giving $3\times 2\times {3\choose 2}.$ Finally for $a_2^3$ we get six permutations of the three colors. This yields

$$\frac{1}{12} \left({6\choose 2,2,2} + 3\times 2\times {3\choose 2} + 4\times 6\right) \\ = \frac{1}{12} (90 + 18 + 24) = 11.$$

On the other hand Polya says that we need the coefficient

$$[A^2 B^2 C^2] Z(D_6)(A+B+C)$$ which is

$$[A^2 B^2 C^2]\frac{1}{12} \left((A+B+C)^6 + 2(A^6+B^6+C^6) + 2(A^3 + B^3 + C^3)^2 \\+ 3(A+B+C)^2(A^2+B^2+C^2)^2 + 4(A^2+B^2+C^2)^3\right).$$

Now we may drop the terms that cannot possibly produce multiples of $A^2 B^2 C^2$ which leaves

$$[A^2 B^2 C^2]\frac{1}{12} \left((A+B+C)^6 \\ + 3(A+B+C)^2 (A^2+B^2+C^2)^2 + 4(A^2+B^2+C^2)^3\right).$$

Doing the coefficient extraction then yields

$$\frac{1}{12} \left({6\choose 2,2,2} + 3 \times 3 \times 2 + 4{3\choose 1,1,1}\right) = 11.$$

Here we have used the observation that we must choose a square from the first term of $(A+B+C)^2 (A^2+B^2+C^2)^2$ and then choose the two remaining squares from the second factor, which may be done in two ways.

$\endgroup$
  • $\begingroup$ I'm gonna mark this answer and come back when I've figured out what Polya Enumeration Theorem is! $\endgroup$ – Allen Ai Nov 17 '16 at 3:50
  • $\begingroup$ @MarkoRiedel: Nice and instructive presentation! (+1) $\endgroup$ – Markus Scheuer Nov 20 '16 at 22:48
  • $\begingroup$ Thank you. I frequently try to present PET as an extension of Burnside, showing that they are definitely the same and the proof of PET is instantaneous once Burnside is understood properly. Both may be applied when the cycle index has been computed. $\endgroup$ – Marko Riedel Nov 20 '16 at 22:52

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.