2B Permutations
|
Suppose you wish to take a picture of your three friends, Alice, Betty, and Cindy, lined up in a row. As photographer you can arrange the women from left to right in the order you prefer. In how many different ways can you line up the women? As there are only three women, it is not difficult to ponder a moment and write down all the possibilities; referring to the ladies by the letters A, B, C, we discover the six arrangements
ABC |
ACB |
BAC |
BCA |
CAB |
CBA |
Each one of the arrangements of the women is called a permutation; altogether there are six possible permutations.
But what if there were ten ladies? Now the problem becomes more serious, as it would take forever to write down all the possibilities, and even if you tried you would never know whether you left any out. Thus it appears that we must devise a method of counting the permutations without actually writing them all down. The way to do this is to divide the procedure of lining up the women into steps, and then use the multiplication principle.
Going back to the case of three ladies, we imagine that there are three slots where the ladies may stand:
In arranging the ladies there are three corresponding steps; we must fill the first slot, then the second slot, and then the third. We have three ways to place a lady in the first slot. After this first step is complete, there are then two ways of filling the second slot, as there are only two ladies left. Finally, after filling the first two slots, there is only one lady left, so there is just one way to fill the last slot. By the multiplication principle, the number of ways of completing the entire procedure by doing all three steps is
3 · 2 · 1 = 6 .
Of course the same technique works with ten ladies, except that we need ten slots and ten steps instead of three. The number of permutations of ten women is
10! = 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 3,628,800 .
We use the shorthand notation 10! to refer to this long product. More generally, for any positive integer N the notation N! designates the product
N! = N · (N−1) · (N−2) · … · 3 · 2 · 1 .
We read "N!" as "N factorial". Some other factorials are
1! = 1 |
2! = 2 · 1 = 2 |
3! = 3 · 2 · 1 = 6 |
||
4! = 4 · 3 · 2 · 1 = 24 |
5! = 5 · 4 · 3 · 2 · 1 = 120 |
6! = 6 · 5 · 4 · 3 · 2 ·1 = 720 . |
A permutation of a group of objects is a way of placing the objects in an order. Since obviously our method of ordering ladies should work just as well with general objects, we have the following rule:
| First Permutation Rule |
The number of possible permutations of N objects is N! |
There are many other ways of ordering objects besides lining them up for a picture, as the ensuing examples will demonstrate.
example 1
 |
Six horses are entered in a race. In how many different orders can the horses complete the race?
There are six steps in ordering the horses. First we choose a first place winner, then a second place finisher, then third, fourth, fifth, and sixth. There are 6 choices for first, then 5 choices for second, 4 for third, etc.; therefore, the number of possible permutations is
6! = 6 · 5 · 4 · 3 · 2 ·1 = 720 .
example 2
 |
A dance class has 5 men students and 5 women students. How many ways can the teacher form 5 couples to dance the waltz?
We divide the procedure of forming couples into 5 steps. First we number the women 1 through 5. There are 5 ways of choosing a male partner for woman # 1. Then for woman # 2 there are only 4 choices remaining, for woman # 3 only 3 choices, for woman # 4 there are 2 choices, and finally for woman # 5 there is but 1 choice. The number of ways the teacher can form 5 couples is
5! = 5 · 4 · 3 · 2 ·1 = 120.
example 3
 |
A baseball team has 9 starting players. How many ways can the coach make out the batting order?
The coach may select the leadoff batter in 9 ways, then the second batter in 8 ways, the third batter in 7 ways, etc., until the last batter can be chosen in only one way. The end result is
9! = 9 · 8 · 7 · 6 · 5 ·4 · 3 · 2 · 1 = 362,880 .
example 4
 |
Lori's dog gave birth to 4 puppies. As she has no space for more than one dog, she will give one puppy to each of her four cousins. In how many ways can she distribute the four puppies among her cousins?
The four steps are to give Fido to a cousin, in one of 4 ways, then Lassie to another cousin in one of 3 ways, then Rover to a cousin in one of 2 ways, and finally Spot to the last cousin. The number of possible permutations is
4! = 4 · 3 · 2 · 1 = 24 .
example 5
 |
Four acrobats will line up for a picture. Each acrobat has the option of standing on his/her feet or standing on his/her head. How many possible pictures are there?
This problem combines our permutation formula with the multiplication principle. We can divide the procedure of lining up and positioning the acrobats into five steps:
Step 1 - line up the 4 acrobats : 4! = 24 ways
Step 2 - position the first acrobat : 2 ways
Step 3 - position the second acrobat : 2 ways
Step 4 - position the third acrobat : 2 ways
Step 5 - position the fourth acrobat : 2 ways
Thus the number of possible pictures is the product
24 · 2 · 2 · 2 · 2 = 384 .
If we wanted to go into more detail, we could divide step 1 into 4 smaller steps - by lining up the acrobats one at a time. However, as we already have a formula for the lining-up procedure, we may as well use it.
Returning to the acrobats, let us now suppose that an acrobat troupe consists of 10 members, and that their publicist will choose 4 members of the troupe and line them up for a publicity picture (standing normally - to keep it simple). How many possible pictures are there under these conditions? This problem is slightly different from the preceding permutation problems, because now we do not order all the objects in the group but just a certain number of them. Nevertheless, the method of solving the problem is the same - we divide the procedure into steps and use the multiplication principle. We imagine four slots where the acrobats are to stand, and fill the slots one a time. The first slot can be filled in 10 ways, the second in 9 ways, and so on. The number of ways of lining up 4 of the 10 available acrobats is
10 |
· | 9 |
· | 8 |
· | 7 |
= 5040 . |
The shorthand way of writing the product on the left is P(10,4); that is,
P(10,4) = 10 · 9 · 8 · 7 = 5040 .
We say that the number of permutations of 10 objects taken 4 at a time is P(10,4).
More generally, if N and M are positive integers and N ≥ M, then P(N,M) represents the number of ways of choosing M objects from N objects and placing them in an order; the way to calculate this number is to multiply
P(N,M) = N · (N−1) · (N−2) · … (continue for M factors).
Here are examples:
P(7,3) = 7 · 6 · 5 = 210 |
P(12,4) = 12 · 11 · 10 · 9 = 11,880 |
|
P(4,1) = 4 |
P(9,5) = 9 · 8 · 7 · 6 · 5 = 15,120 |
|
P(100,2) = 100 · 99 = 9,900 |
P(6,6) = 6 · 5 · 4 · 3 · 2 · 1 = 720 |
The last example, P(6,6), illustrates what we already know - that the number of ways of choosing N objects from N objects and placing them in an order is
P(N,N) = N!
The example P(4,1) = 4 illustrates the general formula for choosing one object from N objects,
P(N,1) = N .
In summary, our second rule for permutations is
| Second Permutation Rule |
The number of possible permutations of M objects chosen from N objects is P(N,M). |
example 6
 |
A football team has 5 players trying out for the quarterback position. How many ways can the coach select a starting quarterback and a backup quarterback?
Here we are choosing 2 objects from 5 objects, and then ordering the two objects - one as a starter and the second as a backup. There are 5 ways of choosing the starter and then 4 ways of choosing the backup; thus the number of permutations is
P(5,2) = 5 · 4 = 20.
 |
example 7
In a race of 7 women, in how many ways can first, second, and third place ribbons be awarded?
From the 7 women there are 7 possible winners, and then 6 possible runner-ups, and finally 5 possible third place finishers. We are choosing 3 from 7 and placing them in an order; the number of ways is
P(7,3) = 7 · 6 · 5 = 210 .
example 8
 |
Janet has 6 business suits, and will travel to LA for a business convention the first 3 days of next week. How many ways can she choose suits for Monday, Tuesday, and Wednesday,
(a) if she wears a different suit each day?
(b) if she is willing to wear the same suit repeatedly?
The first question is a permutation question, while the second is not. If she wears a different suit each day, then we must choose one suit for Monday, a different one for Tuesday, and still another for Wednesday. We have 6 choices for Monday, 5 for Tuesday, and 4 for Wednesday, so the number of permutations is
P(6,3) = 6 · 5 · 4 = 120 .
In the second question we may make the same choice each day, so for each day there are 6 choices. By the multiplication principle, the number of ways of making the three choices is
6 · 6 · 6 = 216 .
example 9
 |
A dance class has 7 men and 5 women. How many ways can the instructor form 5 couples to rehearse the tango?
This problem is a little tricky. The way to handle it is to choose a man for each woman. In step 1 we choose a man for Alice, in step 2 we choose a man for Betty, etc., until all 5 women have a partner. For Alice there are 7 choices, then for Betty 6 choices, and so on, so that after 5 steps the number of permutations is
P(7,5) = 7 · 6 · 5 · 4 · 3 = 2,520 .
If we try it the other way around - that is, choose a woman for each man - then the method fails because not every man can be given a woman. Moreover, we cannot just give a woman to 5 of the men, because then we are restricting the number of men to 5 and thereby changing the problem; we will miss some possibilities for couples if we arbitrarily discard 2 men.
example 10
 |
Suppose 4 cars at once enter a parking lot with 6 empty parking places. In how many ways can the drivers choose parking spaces?
This problem is like the previous tango problem. We have to match cars with parking places. Since there are more parking places than cars, not every parking place will get a car; but every car will have a parking place so we will assign the parking places to the cars. For the Chevy there are 6 choices, then for the Ford 5 choices, next for the Honda 4 choices, and finally for the Mazda 3 choices. The number of permutations is
P(6,4) = 6 · 5 · 4 · 3 = 360 .
EXERCISES 2B
 |
 |
|
 |
 |
|
 |