Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
Elementary Puzzles
High School Permutations and Combinations
High School Puzzles
Middle School Puzzles

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search