1.6 Permutations 171.5.6We have 20 kinds of presents; this time, we have a large supply of each
kind. We want to give presents to 12 children. Again, it is not required that every
child gets something; but no child can get two copies of the same present. In how
many ways can we give presents?
1.6 Permutations
During Alice’s birthday party, we encountered the problem of how many
ways can we seatnpeople onnchairs (well, we have encountered it for
n= 6 andn= 7, but the question is natural enough for anyn). If we
imagine that the seats are numbered, then finding a seating for these people
is the same as assigning them to the numbers 1, 2 ,...,n(or 0, 1 ,...,n−1if
we want to please the logicians). Yet another way of saying this is to order
the people in a single line, or write down an (ordered) list of their names.
If we have a list ofnobjects (an ordered set, where it is specified which
element is the first, second, etc.), and we rearrange them so that they are
in another order, this is calledpermutingthem; the new order is called a
permutationof the objects. We also call the rearrangement that does not
change anything a permutation (somewhat in the spirit of calling the empty
set a set).
For example, the set{a, b, c}has the following 6 permutations:
abc, acb, bac, bca, cab, cba.So the question is to determine the number of waysnobjects can be
ordered, i.e., the number of permutations ofnobjects. The solution found
by the people at the party works in general: We can put any of thenpeople
in the first place; no matter whom we choose, we haven−1 choices for the
second. So the number of ways to fill the first two positions isn(n−1). No
matter how we have filled the first and second positions, there aren− 2
choices for the third position, so the number of ways to fill the first three
positions isn(n−1)(n−2).
It is clear that this argument goes on like this until all positions are
filled. The second to last position can be filled in two ways; the person
put in the last position is determined, once the other positions are filled.
Thus the number of ways to fill all positions isn·(n−1)·(n−2)··· 2 ·1.
This product is so important that we have a notation for it:n! (readn
factorial). In other words,n! is the number of ways to ordernobjects.
With this notation, we can state our second theorem.
Theorem 1.6.1The number of permutations ofnobjects isn!.
Again, we can illustrate the argument above graphically (Figure 1.3). We
start with the node on the top, which poses our first decision: Whom do
we seat in the first chair? The 3 arrows going out correspond to the three