Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Twelve Beads on a String


Date: 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/   
    
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/