2
$\begingroup$

The question asks: if there are 16 beads on a string and on the string, there are 3 white beads and 13 black beads. How many different necklaces can you make?

To determine the number of different types of necklaces, the number of orbits needs to be determined. To do this, we need to determine the symmetries of the circle.

So I know there are 32 elements in the group G, which is the identity, 15 rotations of 360/15 x n, where n=1,2...16, then 8 reflections over the corners and 8 reflections over the sides.

Clearly, the identity yields a total of 16 choose 3 which is 560 and the 15 rotations is 0 as every time you rotate, the adjacent colour would need to be the same and the whole necklace will be a single colour. However, I don't know how to determine the number of reflections? I.e. the Xg number we need to determine the sum of all Xg's.

Please can someone explain how to work with the reflections

$\endgroup$
0
$\begingroup$

Let's have another look at the problem. What you are trying to achieve is essentially dividing the $13$ back beads in $3$ parts. There's a catch though, we have to take care of the cyclic symmetries. Let's see what we can do. If we neglect the symmetries, we can do it in ${{n+r-1} \choose r}={15 \choose 13}=105$ ways. Now, we see which symmetrical conditions occur. $13$ cannot be divided into $3$ equal parts, so we need not worry about that. It can be divided into parts two of which would be equal. This can be done in $7$ different ways i.e. $\{(0,0,13),(1,1,11),...,(6,6,1)\}$. All of the cases can occur in $3$ ways. So, the number of the rest of the cases, in which all of the partitions would be different, would be $105-(7 \times 3)=84$. Now, such cases can be represented in $3!=6$ ways. So, the number of independent cases would be $\frac{84}{6}=14$. So, the number of possible necklaces would be $21+14=35$.

$\endgroup$
0
$\begingroup$

Observe that rotational symmetry is usually refered to as being a necklace and dihedral symmetry as a bracelet. There is additional material at this link at MSE Meta.

In the present case we require the cycle index of the dihedral group $D_{16}.$ We start with the rotations. Label the slots clockwise from $0$ to $15$. There is the identity, for a contribution of $$a_1^{16}.$$

There is a rotation that maps $0$ to $8$ for a contribution of $$a_2^8.$$

The rotations that map $0$ to $4,12$ which do not map $0$ to $8$ contribute $$2 a_4^4.$$

The rotations that map $0$ to $2,6,10,14$ contribute $$4 a_8^2.$$

Finally the rotations that map $0$ to $1,3,5,7,9,11,13,15$ contribute $$8 a_{16}.$$

This gives for the cycle index $Z(C_{16})$ of the cyclic group $$Z(C_{16}) = \frac{1}{16} a_1^{16} + \frac{1}{16} a_2^8 + \frac{1}{8} a_4^4 + \frac{1}{4} a_8^2 + \frac{1}{2} a_{16}.$$

We reqire dihedral symmetry however. There are eight reflections about an axis passing through the midpoints of opposite bridges between adjacent slots, which create two-cycles for a contribution of $$8 a_2^{8}.$$

Reflections about an axis passing through opposite slots fix those and partition the rest into two-cycles for a contribution of $$8 a_1^2 a_2^{7}.$$

This gives for the cycle index $Z(D_{16})$ of the dihedral group $$Z(D_{16}) = \frac{1}{32} a_1^{16} + \frac{1}{32} a_2^8 + \frac{1}{16} a_4^4 + \frac{1}{8} a_8^2 + \frac{1}{4} a_{16} + \frac{1}{4} a_2^8 + \frac{1}{4} a_1^2 a_2^7 \\ = \frac{1}{32} a_1^{16} + \frac{9}{32} a_2^8 + \frac{1}{16} a_4^4 + \frac{1}{8} a_8^2 + \frac{1}{4} a_{16} + \frac{1}{4} a_1^2 a_2^7.$$

Now the answer we are looking for is given by $$[B^3 W^{13}] Z(D_{16})(B+W).$$

Recall that the PET substitution is $$a_d = B^d + W^d.$$

Note that $(3,13)=1$ and so terms like e.g. $a_4^4$ or $a_8^2$ cannot possibly contribute since they produce powers that are multiples of $4$ and $8$ respectively. Therefore the only terms that contribute are

$$\frac{1}{32} a_1^{16} + \frac{1}{4} a_1^2 a_2^7.$$

We obtain $$\frac{1}{32} [B^3 W^{13}] (B + W)^{16} + \frac{1}{4} [B^3 W^{13}] (B + W)^2 (B^2 + W^2)^7 \\ = \frac{1}{32} {16\choose 3} + \frac{1}{4} [B^3 W^{13}] 2BW (B^2 + W^2)^7 \\ = \frac{1}{32} {16\choose 3} + \frac{1}{2} [B^2 W^{12}] (B^2 + W^2)^7 \\ = \frac{1}{32} {16\choose 3} + \frac{1}{2} {7\choose 1} = 21.$$

In going from the first to the second line in this last computation we have used the fact that the powers of $B$ and $W$ in $(B^2+W^2)(B^2+W^2)^7$ are even while $3$ and $13$ are odd.

Remark. The above can also be computed using Burnside rather than Polya but we still require the cycle index so I thought we may as well go with PET. When using Burnside we need to ask (among several possibilities) how many assignments are fixed by a permutation of cycle structure $a_1^2 a_2^7.$ Since we have an odd number of $B$s and $W$s and $a_2^7$ consists of (even) two-cycles we must place a $B$ and a $W$ in the two slots that are fixed points to get even counts for $B$ and $W$. There are two possibilities for this. This leaves $B^2$ and $W^{12}$ which means we need to choose one of the seven two-cycles for the color black, which gives seven possibilities, and color the rest white. This is of course the same as what Polya would produce.

$\endgroup$

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.