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 

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 

    -------  =  3530

So in all 3530 different necklaces could be made from the 12 beads 
coloured in the way described.

- Doctor Anthony, The Math Forum   
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- The Math Forum at NCTM. All rights reserved.