Twelve Beads on a StringDate: 05/24/99 at 01:46:18 From: Grant McCasker Subject: Beads on a String I am having problems with a question: How many different arrangements are there when there are 12 beads of 4 different colours on a string? There are 6 red, 2 yellow, 2 black, and 2 green. Is this correct? (12 - 1)!/(2.2!.2!.2!.6!) = 3465 Date: 05/24/99 at 07:24:32 From: Doctor Anthony Subject: Re: Beads on a string If there were a single bead of one colour to act as a reference point your method would be okay, but without that we need to use Burnside's lemma and deal with group action and symmetries of the dihedral group D24. Burnside's lemma states in effect that the number of distinct configurations is equal to sum of all the group actions that keep the colours fixed, divided by the order of the group, in this case 24. There are 12 rotational symmetries, and for the reflection symmetries there are 6 diameters passing through the gap between two beads at each end, and 6 diameters that bisect a bead at either end. Rotational symmetries that keep the colours fixed for this particular colour scheme of 6, 2, 2, 2 are the identity and rotation through 180 degrees. We can make up a table of all the group actions that keep the colours fixed: Element Number of configurations --------- ------------------------- Identity 12!/(6!2!2!2!) r^6 6!/3!1!1!1! (this is 180 degree rotation) Reflection 6!/3!1!1!1! (through gaps between beads) Reflection(2 reds) 5!/2!1!1!1! (reds at end of diameter) Reflection(2 yellows) 5!/3!1!1! (yellows at end of diameter) Reflection(2 greens) 5!/3!1!1! (greens at end of diameter) Reflection(2 blues) 5!/3!1!1! (blues at end of diameter) There will be 6 axes for each of the reflections, so the total number of configurations fixed under group action is: 12!/6!2!2!2! + 6!/3! + 6[6!/3! + 5!/2! + 5!/3! + 5!/3! + 5!/3!] = 83160 + 120 + 6[120 + 60 + 20 + 20 + 20] = 83160 + 120 + 1440 = 84720 and applying Burnside, the number of nonequivalent configurations will be: 84720 ------- = 3530 24 So in all 3530 different necklaces could be made from the 12 beads coloured in the way described. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/