# How many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads?

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.

• Are we using all the beads? Dec 1, 2014 at 8:26
• Yes, all of the beads must be used. Dec 1, 2014 at 8:37
• Dec 1, 2014 at 8:47
• 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
– user354674
Aug 7, 2016 at 9:00

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

• nice understanding of the problem ! I spent a week to solve it in the n-cocktail party when n is not a prime ...
– user354674
Aug 7, 2016 at 9:01

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!

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

• This is not correct, because you have not accounted for the fact that the arrangement is in a circle, so many permutations are equivalent. Mar 22, 2017 at 0:32