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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.