Given 2 red beads, 2 blue beads, 1 yellow bead, and 1 green bead, how many different necklaces can be made?

Question

I need to write a Matlab code to determine the answer (which was given as 16) and I need to utilize loops to remove flips and circular shifts

Answer 1

We use the Polya Enumeration Theorem (PET). The cycle index $Z(D_6)$ of the dihedral group $D_6$ is given by

$$Z(D_6) = \frac{1}{12} \left(\sum_{d|6} \varphi(d) a_d^{6/d} + 3 a_2^3 + 3 a_1^2 a_2^2\right).$$

This is

$$\frac{1}{12} \left(a_1^6 + a_2^3 + 2 a_3^2 + 2 a_6 + 3 a_2^3 + 3 a_1^2 a_2^2\right) \\ = \frac{1}{12} \left(a_1^6 + 2 a_3^2 + 2 a_6 + 4 a_2^3 + 3 a_1^2 a_2^2\right).$$

We seek

$$[R^2 B^2 Y G] Z(D_6; R+B+Y+G).$$

The only contribution comes from

$$\frac{1}{12} \left(a_1^6 + 3 a_1^2 a_2^2\right).$$

This is because with the Polya substitution the terms $2 a_3^2 + 2 a_6 + 4 a_2^3$ produce powers of three, six, and two, exclusively.

Continuing, we get

$$\frac{1}{12} [R^2 B^2 Y G] (R+B+Y+G)^6 \\ + \frac{1}{4} [R^2 B^2 Y G] (R+B+Y+G)^2 (R^2+B^2+Y^2+G^2)^2.$$

This is

$$\frac{1}{12} {6\choose 2,2,1,1} + \frac{1}{4} \times 2 \times 2 = 16.$$

BTW the convention at the OEIS is to use the term necklace for cyclic symmetries and bracelet for dihedral ones.

Answer 2

By convention, necklaces are invariant with respect to rotation, while bracelets are invariant with respect to both rotation and reflection because a bracelet can be turned over, while a necklace cannot.

Thus, we wish to count bracelets with two blue beads, two green beads, one red bead, and one yellow bead.

If we use the red bead as our reference point, we have five positions to fill. We can fill two of them with blue beads in $\binom{5}{2}$ ways and two of the remaining three positions with green beads in $\binom{3}{2}$ ways. The yellow bead must fill the remaining beads. Therefore, if we were only concerned with rotational invariance, we would have $$\binom{5}{2}\binom{3}{2} = 30$$ necklaces.

However, we wish to count bracelets. If a bracelet is its own reflection, we have counted it once. However, if it is not its own reflection, we have counted it twice, once when we place the beads in a particular order as we traverse the circle in a clockwise direction relative to the red bead and once when we place the same beads in a counterclockwise (anti-clockwise) direction as we traverse the circle relative to the red bead.

There are two bracelets that are there own reflections. To make it easy to visualize, I have spaced the beads around the circle so that the red and yellow beads are opposite each other.

The remaining $30 - 2 = 28$ bracelets have been counted twice, once when we count a bracelet and once when we count its reflection in the diameter that passes through the red bead. For instance, we have counted the following bracelet twice since each bracelet is a reflection of the other in the indicated axis.

Hence, the number of distinguishable bracelets is $$2 + \frac{1}{2} \cdot 28 = 2 + 14 = 16$$