Section 4.4 Permutations and Combinations
275
(b)
(a)
C [n, r]
P[n, r]
n
r]
n
r]
figure 4.9
example 52
The special cases for C(n, r) are C(n, 0), C(n, 1), and C(n, n). The formula for C(n, 0),
C(n, 0) =
n!
0!(n − 0)!
= 1
reflects the fact that there is only one way to choose zero objects from n objects:
Choose the empty set.
C(n, 1) =
n!
1!(n − 1)!
= n
Here the formula indicates that there are n ways to select 1 object from n objects.
C(n, n) =
n!
n!(n − n)!
= 1
Here we see that there is only one way to select n objects from n objects, and that
is to choose all of the objects.
In the formula for C(n, r), suppose n is held fixed and r is increased. Then r!
increases, which tends to make C(n, r) smaller, but (n − r)! decreases, which tends
to make C(n, r) larger. For small values of r, the increase in r! is not as great as
the decrease in (n − r)!, and so C(n, r) increases from 1 to n to larger values. At
some point, however, the increase in r! overcomes the decrease in (n − r)!, and
the values of C(n, r) decrease back down to 1 by the time r = n, as we calculated
in Example 52. Figure 4.9a illustrates the rise and fall of the values of C(n, r) for a
fixed n. For P(n, r), as n is held fixed and r is increased, n − r and therefore (n − r)!
decreases, so P(n, r) increases. Values of P(n, r) for 0 ≤ r ≤ n thus increase from
1 to n to n!, as we calculated in Example 46. See Figure 4.9b; note the difference
in the vertical scale of Figures 4.9a and 4.9b.
example 53
How many 5-card poker hands are possible with a 52-card deck? Here order does
not matter because we simply want to know which cards end up in the hand. We
want the number of ways to choose 5 objects from a pool of 52, which is a combinations problem. The answer is C(52, 5) = 52!/(5!47!) = 2,598,960.
275
(b)
(a)
C [n, r]
P[n, r]
n
r]
n
r]
figure 4.9
example 52
The special cases for C(n, r) are C(n, 0), C(n, 1), and C(n, n). The formula for C(n, 0),
C(n, 0) =
n!
0!(n − 0)!
= 1
reflects the fact that there is only one way to choose zero objects from n objects:
Choose the empty set.
C(n, 1) =
n!
1!(n − 1)!
= n
Here the formula indicates that there are n ways to select 1 object from n objects.
C(n, n) =
n!
n!(n − n)!
= 1
Here we see that there is only one way to select n objects from n objects, and that
is to choose all of the objects.
In the formula for C(n, r), suppose n is held fixed and r is increased. Then r!
increases, which tends to make C(n, r) smaller, but (n − r)! decreases, which tends
to make C(n, r) larger. For small values of r, the increase in r! is not as great as
the decrease in (n − r)!, and so C(n, r) increases from 1 to n to larger values. At
some point, however, the increase in r! overcomes the decrease in (n − r)!, and
the values of C(n, r) decrease back down to 1 by the time r = n, as we calculated
in Example 52. Figure 4.9a illustrates the rise and fall of the values of C(n, r) for a
fixed n. For P(n, r), as n is held fixed and r is increased, n − r and therefore (n − r)!
decreases, so P(n, r) increases. Values of P(n, r) for 0 ≤ r ≤ n thus increase from
1 to n to n!, as we calculated in Example 46. See Figure 4.9b; note the difference
in the vertical scale of Figures 4.9a and 4.9b.
example 53
How many 5-card poker hands are possible with a 52-card deck? Here order does
not matter because we simply want to know which cards end up in the hand. We
want the number of ways to choose 5 objects from a pool of 52, which is a combinations problem. The answer is C(52, 5) = 52!/(5!47!) = 2,598,960.