Ways To List 1, 2, ... 10 Out of Order

Date: 02/25/97 at 09:43:43
From: Jule Brennan
Subject: Ways To List 1, 2, ... 10 Out of Order

Dear Dr. Math,

How many ways are there to list the numbers one through ten so that 
no number appears in its own position (i.e. 1 is not first in the 
list, 2 is not second, three is not third, etc.)?      

Sincerely,
   Mrs. Brennan's Fifth Grade Math Class

Date: 03/14/97 at 11:13:01
From: Doctor Barney
Subject: Re: Ways To List 1, 2, ... 10 Out of Order

Well,  this is a very complicated question.  I would like to start 
with a slightly easier question, so that you can get used to the type 
of reasoning I will be using to explain how I solved this problem.  

To start with, consider this warm-up problem:  How many ways are there 
to arrange the numbers 1 through 10 without any restrictions?

We can answer this question by taking the numbers one at a time.  For 
example, there are 10 places we could put the -1- in the sequence: it 
could go in any of the 10 places. 

Now for EACH of those 10 places, how many places are there where you 
could put the -2-?  It could go anywhere except in the place that is 
already taken by the -1-, so there are 9 places the -2- could go for 
each of the 10 places that the -1- can go.  That means that there are 
10x9 = 90 different ways to put the -1- and the -2- in the ten places 
in the sequence.  

Next, for EACH of these 90 places, how many places could you put the 
-3-?  I think you can see there will be 8 places the -3- can go 
(anywhere except wherever the -1- is and wherever the -2- is) so now 
we have 10x9x8 = 720 different ways to put the -1- and the -2- and the 
-3- in the ten places in the sequence.

By similar logic, for EACH of the 720 ways to arrange the first 3 
digits, there will be 7 places to put the -4-, and 10x9x8x7 = 5,040 
ways to arrange the first 4 digits.

If you continue this process for all 10 numbers, you will see that the 
answer to this warm-up problem is 10x9x8x7x6x5x4x3x2x1=3,628,800.  
(This expression is called ten factorial, and is often notated as 10!)  
You may notice a pattern developing before you actualy complete all 
of the steps, which often helps find a sort of short-cut to the 
answer.

Now let us tackle the real problem you asked:
  
How many places are there where you could put the -1- ?    I suppose 
there are 9 places you could put it, since it can go anywhere except 
the first place.

Okay. Now, for EACH of those 9 places, how many ways are there to 
arrange the other numbers?  Lets start with the -2- .  If the -1- were 
in the -2-s place, then the -2- could go anywhere else, so there would 
be 9 places.  But, if the -1- were anywhere else the -2- could not go 
in its own place or in the place where the -1- was, so then there are 
only 8 places for the -2- to go.  So how many ways are there to put 
both the -1- and the -2- into the 10 places (in position), without 
regard to the other numbers?   9 ways with the -1- in the -2-s place 
plus 8 ways for EACH of the other 8 places that the -1- can go.  
9+8x8 = 73.  

Now let's find out how many ways there are to put the -3- into the 
picture for EACH of the 73 ways we have found so far.  Well, if the 
-1- or the -2- were in the -3-s place, then there would be 8 places 
that the -3- could go, right?  But if neither the -1- nor the -2- were 
in the -3-s place, then the -3- would only have 7 places it could go.
So, how many of the 73 ways to put the -1- and the -2- in position 
would have either the   -1- or the -2- in the -3-s place?  There are 
only 8 ways to put these two numbers in position which have the -1- in 
the -3-s place, and there are also 8 ways to put these two numbers in 
place which have the -2- in the -3-s place, so there are only 16 ways 
with one of these numbers in the -3-s place.

The other 57 ways to put the -1- and the -2- in position all have the 
-3-s place left open.  (73-16=57) So (16 possible arrangements of -1- 
and -2- with the -3-s place occupied) x (8 places for the -3- to go if 
the -3-s place is occupied) + (57 possible arrangements of -1- and -2- 
with the -3-s place vacant) x (7 places for the -3- to go if the -3-s 
place is vacant) = 16x8+57x7 = 527 ways to put the first 3 numbers in 
position.

We are trying to look for a pattern so that we do not have to do all 
10 numbers this way.

Lets do -4-.  For each of the 527 possible ways to put the first 3 
numbers in position, how many places are there that the 4 could go?  
By using similar logic to the steps above, in 171 of those 527 cases 
the -4-s place will be occupied, and in the other 356 cases it will 
not be, so there are 171x7+356x6= 3,333 ways to put the first 4 
numbers in position.

Now I have begun to notice a pattern emerging.  Each time we add a new 
digit to the problem, the first question we ask is:  How many of the 
possible arrangements from the previous step will leave the new digits 
own place open?   But that is really a similar problem to the original 
question, except with less possible places to put the numbers instead 
of 10.  So I noticed that the answer to this question is related to 
the answer from the previous step.  I know that this is very confusing 
at this point, and I don't expect your class to be able to follow all 
of it, but I wanted to show you what I did, rather than just tell you 
the answer.   Let me show you what I mean:

number of          equation       number of ways to
digits                            arrange these digits

  1                0 x 10 + 1 x 9      =      9

  2                 1 x 9 + 8 x 8      =     73

  3               16 x 8 + 57 x 7      =    527
                (2x8)    (73-16)

  4             171 x 7 + 356 x 6      =   3,333
                (3x57)   (527-171)

  5         1,424 x 6 + 1,909 x 5      =  18,089
             (4x356)  (3,333-1,424)

  6         9,545 x 5 + 8,544 x 4      =  81,901  
           (5x1,909)  (18,089-9,545)

  7       51,264 x 4 + 30,637 x 3      = 269,967

Do you see the pattern?  I used a spreadsheet to continue this 
iterative process, and for all 10 digits the answer is: 1,334,961  

These possible arrangements are called permutations, which is an 
important concept in the field of probability.  There is probably a 
formula we could have looked up to tell us the answer, but sometimes 
its more fun (and more educational) to figure it out for yourself.  

-Doctor Barney,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/