10.6. Counting Principles: Permuations and Combinations
In the previous section we introduced binomial coefficients, i.e. the numbers nCk, and showed how to compute them recursively by constructing Pascal's Triangle. In this section, we will interpret these numbers as well as another set of coefficients nPk, known as permuation coefficients. We will also derive formulas for these coefficients. The counting principles we introduce in this section will be the starting point of our discussion of probability in the following section.
We begin with permutations. Consider a set of n objects such as tickets, each labeled with numbers 1 to n. We would like to know how many possible outcomes there are if we select k of the n tickets. This number is denoted by the symbol nPk. Each of these possible ways of selecting tickets is called a permutation. Thus, nPk is the number of permutations of n distinct objects taken k at a time.
So how to we determine the value of nPk? The number of ways of selecting the k tickets is equal to the number of ways of selecting the first ticket times the number of ways of selecting the second ticket and so on, all the way down to the kth ticket. Clearly there are n ways to select the first ticket, since there are n tickets. Then there are n-1 ways to select the second ticket, since there are n-1 remaining tickets. Then there are n-2 ways to select the third ticket and so on, down to the kth ticket, of which there are n-k+1 ways of selecting, since this is the number of remaining tickets before it is chosen. Thus, the total number of permutations nPk is equal to the product n(n-1)(n-2)...(n-k+1).
Example 1: How many possible ways are there to knock the first three of 15 pool balls into the holes of a pool table, i.e. 3 first, followed by 12 and 7?
Solution: The ordering of the first three balls is a permuation of 15 distinct objects taken three at a time, so the number of them is given by 15P3, which is equal to (15)(14)(13) = 2730.
There is a nice compact way of expressing products of consecutive numbers, using an operation known as the factorial. For a positive integer n, the factorial of n, written as n! and read as "n factorial", is defined to be the product of all positive integers up to n. Specifically we have
- (10.6.1) n! = (1)(2)(3)...(n).
The factorial has a peculiar feature, namely the value of 0! = 1. It might seem like 0! should be equal to zero, since the product ends with zero. But we cannot apply formula (10.6.1) to the case n=0 because there are no terms in the product. Instead, we note that for every integer n greater than 1, we have n! = n(n-1)!. Since this works for all integers greater than 1, why not define 0! in such a way that it works for n=1 as well? In other words, we want it to be true that 1! = 1 * 0!. But since 1! = 1, this can only be true if 0! = 1.
So how can we express nPk = n(n-1)(n-2)...(n-k+1) in terms of the factorial? The trick is to recognize that this product is equal to the product of all positive integers from 1 to n divided by the product of all integers from 1 to n-k. In other words, we have
- (10.6.2) nPk = n! / (n-k)!
So what if we want to know the total number of possible orderings of n distinct objects? This number is given by nPn, which by (10.6.2) is equal to n! / (n-n)! = n! / 0! = n! / 1 = n!.
Example 2: How many possible ways are there to arrange 10 distinct books on a shelf?
Solution: This number is equal to 10P10 = 10! = 1*2*3*4*5*6*7*8*9*10 = 3,628,800. Note how quickly factorials grow!
Thus far, we have discussed permutations. There is another important counting principle, known as combinations. Suppose now we have n objects and we want to know how many possible ways there are to choose k of them, where we no longer care about the order in which we choose them. Such a choice is known as a combination of k objects taken from a set of n objects. The symbol we use to represent this number is nCk. We have already seen this number; it is a binomial coefficient! Later we will show that these numbers are in fact the same, but for now, we merely want to derive a formula for nCk, like we did for nPk. Note that the only difference between permutations and combinations is that with the latter, we no longer care about the order of the k objects we choose. Thus, we see that nPk should be equal to nCk times the number of possible ways of ordering the k objects we have chosen. But as we have seen, this number is equal to k!, so we have nPk = k! nCk. Thus we have
- (10.6.3) nCk = nPk / k! = n! / [k! (n-k)!].
This is a nice formula! Since the numbers nCk are binomial coefficients, we see that now we have a formula for computing them without having to construct Pascal's Triangle. This is very convenient, especially if n is large.
Example 3: Use Equation (10.6.3) to compute the following binomial coefficients.
- (a) 2C1
- (b) 5C3
- (c) 10C7
(Note that these are the same binomial coefficients we computed in Example 1 in the previous section.)
- (a) We have 2C1 = 2! / (1!)2 = 2 / 1 = 2.
- (b) We have 5C3= 5! / (3! 2!) = (5*4*3*2*1) / (2*1*3*2*1) = 5*4 / 2*1 = 20 / 2 = 10.
- (c) We have 10C7 = 10! / (7! 3!) = (10*9*8*7*6*5*4*3*2*1) / (7*6*5*4*3*2*1*3*2*1) = (10*9*8) / (3*2*1) = 720/6 = 120.
Note that these are all the same values we computed in the previous section. This should give us great confidence that the numbers nCk are indeed binomial coefficients, but we still need to prove this. So how do we do so? Let us look at the binomial theorem again. We want to find the coefficient multiplying xn-kyk in the expansion of (x + y)n. Suppose we wanted to determine this coefficient by counting. We have (x + y)n = (x + y)(x + y)...(x + y), the product having n terms. To evaluate this product the hard way, we would have to compute the sum of all 2n products of cross terms (2n since we have two choices for each cross term, namely x or y.) For instance, if n=3, we have (x + y)3 = (x + y)(x + y)(x + y) = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy. Obviously, we can simplify this expression since multiplication is commutative. Thus, we first collect all terms with three x's; these are the x3 terms, of which there is just one, namely xxx. Next, we collect all terms with two x's and one y; these are the x2y terms, of which there are three, namely xxy, xyx, and yxx. Then we collect all terms with one x and two y's; these are the xy2 terms, of which there are again three, namely xyy, yxy, and yyx. Finally, we collect all terms with three y's; these are the y3 terms, of which there is just one, namely yyy. Thus we see that (x + y)3 = x3 + 3x2y + 3xy2 + y3.
Now we generalize this procedure to (x + y)n. For a fixed integer k from 0 to n, to compute the binomial coefficient nCk multiplying xn-kyk, we need to count the number of possible ways there are to choose n-k x's and k y's. But this is just the number of possible ways of choosing k objects (namely the k y's) from a set of n objects, which is what we have discussed in this section. Thus, we see that the binomial coefficients we defined in the previous section are the same as those we defined in this section.
Equation (10.6.3) allows us to compute much larger binomial coefficients than would be practical by construction of Pascal's Triangle, as the following example shows.
Example 4: Compute the number of possible poker hands.
Solution: A poker hand is nothing but a combination of five cards from a deck of 52. Thus, the number of possible poker hands is equal to 52C5 = 52! / (5! 47!) = (52*51*50*49*48) / (5*4*3*2*1) = 311,857,200 / 120 = 2,598,960. That's a lot of possible hands!