2
$\begingroup$

Good day!

Disclaimer: Not a homework question

How many necklaces can be made with 6 beads of 3 different colors?

I know i'm supposed to use the formula: $\frac{1}{ \left |G \right |} \sum_{g \in G} \left | Fix(g) \right |$

My books gives the example of 9 beads of 3 different colors, and gives $$ \frac{1}{ \left |G \right |} \sum_{g \in G} \left | Fix(g) \right |= \frac {1}{18}(3^9+2 \times 3^3+ 6 \times 3 +9 \times 3^5)= 1219 $$

Can anyone explain this? Where do the terms in the parenthesis come from? And the $ \frac {1}{18}$ ? Thanks!

$\endgroup$
3
  • 1
    $\begingroup$ Look around for "Polya counting theory" and/or "Burnside lemma" $\endgroup$
    – thedude
    Dec 11 '15 at 22:57
  • 1
    $\begingroup$ Basically you take the group that acts on the object. For a 9 bead necklace it is the dihedral group $D_9$. It has 9 rotations and 9 rotations followed by reflection, so 18 elements. This is the denominator. Then you must consider, for each element of the group, how many necklaces are invariant under the action of that element. For example, the identity fixes any necklace, so there are $3^9$ invariant necklaces under the identity. This is the first summand. Etc. $\endgroup$
    – thedude
    Dec 11 '15 at 23:05
  • 1
    $\begingroup$ This link at MSE Meta has a section on necklaces and bracelets with contributions from a number of different users. $\endgroup$ Dec 11 '15 at 23:48
2
+50
$\begingroup$

Basically you have to find out which necklaces are identical. Necklaces are identical if they are identical under symmetric operations just as rotate them ($r$) or turning them around ($s$).

First of all I explain why you get the powers of 3.

Look at the case that you do not turn the necklace (you apply the identity $\{e\}$). Because all of 9 beads can have different colors, you can have $3^9$ different necklaces.

Now look at what happen if you consider the rotation $r$, that means you rotate the necklace $2 \pi / 9$ around. If you do so until you reach the point where you began you will see that the necklace stays only identical for all $r, r^2, r^3,..., r^8$ if all the breads have an identical colour, so there are 3 options to create such a necklace.

Now turn the necklace upside down. There is 1 bead that is fixed and all the other 8 beads are at a new position. For the necklace to be identical under this symmetric operation (call it $s$) the 8 beads that change their position have to have the same colour as the bread that was at this position at the beginning. Because of this you have 5 breads where you can choose the colour and then the remaining four must have fixed colours. This corresponds to $3^5$.

Now look at the case if you rotate the necklace around $2 \pi / 3$ corresponding to $r^3$. Then you can choose the colour of three breads and through rotation the other 6 breads must have colours depending on the colours of the first 3. Hence you have $3^3$ choices for the colours.

Take a look at the conjugacy classes of the symmetric operations.

The case $3^9$ corresponds to the identity {e} from which there is one. The rotation $r$ could aswell be $\{r, r^2, r^4, r^5, r^7, r^8\}$ because all the elements are of order 9, which means that they bring the necklace back in the starting position after 9 times applied. Notice that this are 6 elements, so its 6 times 3.

$\{r^3, r^6\}$ form another conjugacy class, so you have $2 \cdot 3^3$.

The last conjugacy class is $\{s, rs, r^2s, r^3s, r^4s, ..., r^8s\}$ containing 9 elements, thus $9 \cdot 3^5$.

At last, notice that $|G| = 18$ because we have 18 possible symmetric operations here: $\{e, r, r^2, ..., r^8, s, rs, r^2s, ... r^8s\}$.

Maybe you can try the case of 6 breads of 3 different colours yourself now and ask if you get stuck anywhere.

$\endgroup$
3
  • $\begingroup$ ahh! very good. Thank you! This is exactly what I wanted! $\endgroup$ Dec 16 '15 at 21:47
  • $\begingroup$ Glad I could help. Don't forget to award the bounty if you want to ;) $\endgroup$ Dec 19 '15 at 15:32
  • $\begingroup$ Ahh just did. Ive never done a bounty, I though it was automatic when I accepted your answer. $\endgroup$ Dec 20 '15 at 17:03

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.