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

combinatoricscomputer scienceMATLABpermutationspolya-counting-theory

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

enter image description here

Best Answer

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.