Counting Arrangements of Objects in a Set

Date: 01/17/2006 at 23:27:22
From: Mia
Subject: My question is about patterns, and different ways of arrangi

A set containing two elements can be arranged in two different ways 
(for elements a and b, it can be ab or ba).  I need to find out in how
many ways can sets containing three, four, five or six elements be
arranged.  

I figured out that the set 123 can be arranged in six ways: 123, 321,
231, 213, 312 and 132.  But it takes too long to do by switching
places of the elements.  Is there an easier way to do it?

Thanks, Mia.

Date: 01/18/2006 at 10:06:34
From: Doctor Greenie
Subject: Re: My question is about patterns, and different ways of arrangi

Hello, Mia --

Yes, there is an easy way to find these numbers of ways of arranging 
the elements for different sizes of sets.

One way to understand the formula for the number of ways to arrange 
the elements of a set is to consider "filling the blanks" one 
element at a time.  In your simple example with a set consisting of 
the two elements a and b, we want to find the number of ways of 
filling two blanks:
  __  __

We have two choices for the element to put in the first blank--a or b.  
Once we have chosen the element for the first blank, we have only one 
choice left for the second blank.  So for each of the two choices for 
filling the first blank we have one choice for filling the second.  
The "for each" indicates multiplication; so the number of ways of 
arranging the two elements of this set is

  2*1 = 2

Note that we tend to think of filling the blanks left to right, but 
that is not necessary.  We can choose to fill the second blank first 
if we want; we will still have two choices for the first blank we 
fill and one choice for the second, giving us a total of 2*1=2 ways 
to arrange the elements.

So what happens if, for example, we have a set consisting of 5 
elements?  We have 5 choices for the element to place in the first 
blank we fill.  For each of those 5 choices, we have 4 choices for the 
element to place in the second blank we fill, giving us 5*4=20 ways to 
fill the first two blanks.  Then for each of those 5*4=20 choices for 
the first two blanks, we have 3 choices for the element to place in 
the third blank we fill, giving us 5*4*3=60 ways to fill the first 
three blanks.  And so on, until all the blanks are filled.  The total 
number of ways of filling the 5 blanks is

  5*4*3*2*1 = 120

Similarly, the number of ways of arranging the elements of a set with 
10 elements would be

  10*9*8*7*6*5*4*3*2*1 = 3628800

The preceding is a common explanation for the formula for the number 
of ways to arrange the elements of a set.  Following is another 
approach to finding the formula.  This approach is more difficult to 
understand; however, it demonstrates a very powerful technique for 
finding patterns: we find the number of arrangements for a particular 
number of elements, and then we add one more element and see how that 
changes the number of arrangements.

So let's go back to our simple case where we have found that there are 
two ways to arrange the elements in a 2-element set:

  ab  ba

Now we add a third element to the set, c.  What arrangements can we 
make with the three elements?

The original two elements can still be in either of the two orders 
they were in when the set contained only two elements--either a is  
before b, or b is before a.

For each of those two orderings of a and b, what choices do we have 
for where to place element c?  We can place the new element before the 
two original elements, or we can place it between them, or we can 
place it after them.  So for the case where a is before b, we get the 
arrangements

  cab  acb  abc

And for the case where b is before a, we get the arrangements

  cba  bca  bac

So with a 2-element set we had a total of 2 possible arrangements of 
the elements; and when we added a third element, we got 3 different 
arrangements from each of the 2 different arrangements of the original 
two elements.

So adding the third element to the set multiplied the number of 
arrangements by 3.  So the number of arrangements for a 3-element set 
is 3*2 = 6.

Consider then adding a 4th element d to the set.  For each of the 6 
arrangements we have for 3 elements, there are 4 different places we 
can put the 4th element.  For example, from the arrangement "abc" of 
the first 3 elements, we can get the following 4 arrangements:

  dabc  adbc  abdc  abcd

So adding the 4th element to the set gives us a total of 4*6=24 
arrangements of the elements.

Then you can see the pattern: adding a 5th element would give us a 
total of 5*24 = 120 elements; adding a 6th would give us 120*6 = 720 
elements; and so on.

I hope all this helps.  Please write back if you have any further 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/