Page 432 - Discrete Mathematics and Its Applications

6.3 Permutations and Combinations 411

Consequently, to compute C(n, r) you can cancel out all the terms in the larger factorial in the
denominator from the numerator and denominator, then multiply all the terms that do not cancel
in the numerator and finally divide by the smaller factorial in the denominator. [When doing
this calculation by hand, instead of by machine, it is also worthwhile to factor out common
factors in the numerator n(n − 1) ··· (n − r + 1) and in the denominator r!.] Note that many
calculators have a built-in function for C(n, r) that can be used for relatively small values of n
and r and many computational programs can be used to find C(n, r). [Such functions may be
called choose(n, k)or binom(n, k)].
Example 11 illustrates how C(n, k) is computed when k is relatively small compared to n
and when k is close to n. It also illustrates a key identity enjoyed by the numbers C(n, k).
EXAMPLE 11 How many poker hands of five cards can be dealt from a standard deck of 52 cards? Also, how
many ways are there to select 47 cards from a standard deck of 52 cards?

Solution: Because the order in which the five cards are dealt from a deck of 52 cards does not
matter, there are

52!
C(52, 5) =
5!47!
different hands of five cards that can be dealt. To compute the value of C(52, 5), first divide the
numerator and denominator by 47! to obtain

52 · 51 · 50 · 49 · 48
C(52, 5) = .
5 · 4 · 3 · 2 · 1
This expression can be simplified by first dividing the factor 5 in the denominator into the
factor 50 in the numerator to obtain a factor 10 in the numerator, then dividing the factor 4 in the
denominator into the factor 48 in the numerator to obtain a factor of 12 in the numerator, then
dividing the factor 3 in the denominator into the factor 51 in the numerator to obtain a factor
of 17 in the numerator, and finally, dividing the factor 2 in the denominator into the factor 52 in
the numerator to obtain a factor of 26 in the numerator. We find that
C(52, 5) = 26 · 17 · 10 · 49 · 12 = 2,598,960.

Consequently, there are 2,598,960 different poker hands of five cards that can be dealt from a
standard deck of 52 cards.
Note that there are

52!
C(52, 47) =
47!5!
different ways to select 47 cards from a standard deck of 52 cards. We do not need to compute
this value because C(52, 47) = C(52, 5). (Only the order of the factors 5! and 47! is different
in the denominators in the formulae for these quantities.) It follows that there are also 2,598,960
different ways to select 47 cards from a standard deck of 52 cards. ▲

In Example 11 we observed that C(52, 5) = C(52, 47). This is a special case of the useful
identity for the number of r-combinations of a set given in Corollary 2.

COROLLARY 2 Let n and r be nonnegative integers with r ≤ n. Then C(n, r) = C(n, n − r).

Proof: From Theorem 2 it follows that

n!
C(n, r) =
r! (n − r)!