1
$\begingroup$

I am trying to figure out how many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads. I understand how to do the problem with two colors, but I am struggling to utilize Burnside's Theorem when adding another color. My understanding of the two colored case is primary visual, which is less than satisfactory for the three color case.

I suppose $D_{14}$ must act on the vertices of a 14-gon, say $X =$ {$1, 2, 3,..., 14$}, but from here I do not see where to go.

$\endgroup$
4
  • $\begingroup$ Are we using all the beads? $\endgroup$ – Hernandez Dec 1 '14 at 8:26
  • $\begingroup$ Yes, all of the beads must be used. $\endgroup$ – Lucky For Me Dec 1 '14 at 8:37
  • $\begingroup$ More info math.stackexchange.com/questions/600/… $\endgroup$ – turkeyhundt Dec 1 '14 at 8:47
  • $\begingroup$ with the same number of heads for each, it is the circular n-cocktail party. You must be aware of 2 and 7 circular symmetries if any $\endgroup$ – user354674 Aug 7 '16 at 9:00
4
$\begingroup$

$S$ = {necklaces of length 14 with 8 blue, 3 green and 3 brown beads}. Clearly,$|S| = \frac {14!} {8!3!3!} $.
The group of symmetries, $G = D_{14}$. Clearly, $|G| = 28$. And as you have identified G is acting on S.

And by Burnside lemma, required answer is, $$ \#orbits = \frac 1 {|G|}*\sum_{\sigma \in G}fix(\sigma)$$

1) $\sigma = identity $

Then it fixes any element in $S$. Thus, $fix(\sigma) = |S| = \frac {14!} {8!3!3!}$

2) Rotations, $\sigma$ = rotation by $\frac {360} {14} degree$ clockwise = $p^1$

Carefully consider the cyclic structure of the permutation $\sigma$, $$\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13&14\\ 2&3&4&5&6&7&8&9&10&11&12&13&14&1 \end{pmatrix}$$ $$\equiv (1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ 14) \ \ \text{[in cycle notation]}$$ If $\sigma$ fixes $x \in S$, then all vertex of the 14-gon must have the same color which is not the case, hence $fix(\sigma)=0$.

Clearly, $fix(\sigma=p^{13})=0$.

3)$\sigma=p^2$ i.e $$\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13&14\\ 3&4&5&6&7&8&9&10&11&12&13&14&1&2 \end{pmatrix}$$ $$\equiv (1\ 3\ 5\ 7\ 9\ 11\ 13)(2\ 4\ 6\ 8\ 10\ 12\ 14) \ \ \text{[in cycle notation]}$$.

So, $\sigma$ has two cycles of length 7 and if you think carefully, for x to be in $fix(\sigma)$ all vertices in a single cycle will have same bead color. Which is not possible with 8 red, 3 blue and 3 brown beads. So, $fix(\sigma)=0$.

Clearly, $fix(\sigma=p^{12})=0$.

In the same fashion compute the $fix(\sigma)$ for the remaining by looking into the cycle structure and then use the burnside to get the required answer.

$\endgroup$
1
  • $\begingroup$ nice understanding of the problem ! I spent a week to solve it in the n-cocktail party when n is not a prime ... $\endgroup$ – user354674 Aug 7 '16 at 9:01
1
$\begingroup$

I noticed the (correct) answer did not actually produce any number in the end. To do so is straightforward using the Cycle index.

First, we compute the cycle index $Z(D_{14})$ of $D_{14}$. This is given by $$ Z(D_{14}) = \frac{1}{2}Z(C_{14}) + \frac{1}{4}(a_2^{7} + a_1^2 a_2^6) = \frac{1}{28}(a_1^{14}+a_2^7+6a^2_7 + 6a_{14}) + \frac{1}{4}(a_2^{7} + a_1^2a_2^6).$$

Let $b, g, n$ denote the number of blue, green, and brown beads respectively. Then, by the magic of the Cycle Index Theorem, we simply substitute $b^j + g^j + n^j$ for $a_j$ in the above formula. This leaves us with a very long multinomial, but one can quickly check (using a computer!) what the coefficient of $b^8 g^3 n^3$ is in there -- this corresponds to the number of colourings using $8$ blue, $3$ green, and $3$ brown beads. This coefficient is $2160$, and hence there are that many coloured necklaces using those beads, up to $D_{14}$-symmetry.

Note that often one will consider $C_{14}$-symmetry rather than dihedral for necklaces. In this case, one does the exact same procedure as above, but one uses $Z(C_{14})$ instead. This gives a total number of $4290$ necklaces using the specified colours (and, as a reality check, it is good that $4290 > 2160$, as imposing more structure should give us fewer necklaces!). That $4290/2$ is very close to $2160$ is not a coincidence -- this corresponds to that allowing flipping along a line of symmetry should roughly half the number of necklaces we have!

$\endgroup$
0
$\begingroup$

You may use the basic permutation rule which gives us $\dfrac{(8+3+3)!}{(8!\times3!\times3!)}$

$\endgroup$
1
  • 3
    $\begingroup$ This is not correct, because you have not accounted for the fact that the arrangement is in a circle, so many permutations are equivalent. $\endgroup$ – The Count Mar 22 '17 at 0:32

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.