You're Reading a Free Preview
You're Reading a Free Preview
You're Reading a Free Preview
You're Reading a Free Preview
You're Reading a Free Preview There are 6 beads in that necklace and each one is a different color. Identify the colors by the codes 1, 2, 3, 4, 5, and 6. Lay the necklace on the table and look for the bead of color 6. What are the other colors read clockwise from that bead? Is it 12345? 15324? Some other sequence There are such sequences.However, and represent the same necklace flipped over. By laying the necklace on the table we made it easier to count the possibilities, but we counted each one twice.There are possible necklaces. NOTE: Your teacher wants you to mention "permutations".It is just one of many names/words (hopefully not too many) that they will make you learn. Words and symbols help us communicate more efficiently, as long as we use them just as necessary.
Paul Raff gave a formula for both bracelets and necklaces so in my answer, I will provide a general method that you can use for this kind of problem. It works also if you want to colour a cube for example. As Paul Raff pointed out, you did get mix up between bracelet and necklace so in my answer I will include the answer for both of them. Where did you get it wrong?It seems to me that you are counting number of ways to colour a bracelet rather than a necklace so I checked your calculation with respect to colouring a bracelet. I would say that the main problem in your counting is that even for each case of the base, you cannot always guarantee to get the final result for that case by multiplying as you did. For example, in the case of $A^2B^2C^2$, we consider two following iterations: The one on the left gives $\frac{6\cdot5\cdot 4}{3!}=\frac{120}{6}$ ways to choose three colours $A,B,C$, which is what you gave in your table. However, the one on the right gives $\frac{6 \cdot 5 \cdot 4}{2}=\frac{120}{2}$ ways to choose three colours $A,B,C$. Necklace colouringYou can use Burnside lemma where you can count the number of ways to colour the object by looking at its group of symmetry $G$. For the necklace, the group $G$ can be:
Let $X$ be the set of all possible colouring for the necklace at a fixed orientation. This follows $|X|=6^6$ as there are $6$ possible colours for each bead. Now, in Burnside lemma, we essentially want to count number of colourings from $X$ that remains unchanged under actions from $G$. In particular:
The Burnside lemma says that you can add all these numbers up and divide by number of elements of $G$ (which is $6$) to obtain all possible colourings. Hence, the answer for colouring a necklace is $$\frac{6^6 \cdot 1 +6 \cdot 2+ 6^2 \cdot 2+6^3 \cdot 1}{6}=7826.$$ Bracelet colouringThe difference between bracelets and necklaces is in the group of symmetry $G$. In particular, for bracelets, $G$ has some extra elements: Two colourings of the bracelet are considered same if from one colouring, we can reflect the bracelet through a line to obtain the other colouring. There are two types of lines:
This time $G$ has $12$ elements. Next, we do the same thing with necklace, i.e. we count number of colourings that remains fixed under these reflections:
Now, applying Burnside's lemma, we sum up all these numbers counted for each element in $G$ then we divide by number of elements in $G$ (which is $12$). The final answer is $$\frac{1}{12}\left( 6^6 \cdot 1+6 \cdot 2+ 6^2 \cdot 2+6^3 \cdot 1+6^3 \cdot 3+ 6^4 \cdot 3 \right)=4291.$$ |