Page 431 - Discrete Mathematics and Its Applications

410 6 / Counting

Example 8 illustrates that many counting problems can be solved by finding the number of
subsets of a particular size of a set with n elements, where n is a positive integer.
An r-combination of elements of a set is an unordered selection of r elements from the set.
Thus, an r-combination is simply a subset of the set with r elements.
EXAMPLE 9 Let S be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-combination from S. (Note that {4, 1, 3} is the
same 3-combination as {1, 3, 4}, because the order in which the elements of a set are listed does
not matter.) ▲

The number of r-combinations of a set with n distinct elements is denoted by C(n, r). Note
n

that C(n, r) is also denoted by and is called a binomial coefficient. We will learn where
r
this terminology comes from in Section 6.4.
EXAMPLE 10 We see that C(4, 2) = 6, because the 2-combinations of {a, b, c, d} are the six subsets {a, b},
{a, c}, {a, d}, {b, c}, {b, d}, and {c, d}. ▲

We can determine the number of r-combinations of a set with n elements using the formula
for the number of r-permutations of a set. To do this, note that the r-permutations of a set can be
obtained by first forming r-combinations and then ordering the elements in these combinations.
The proof of Theorem 2, which gives the value of C(n, r), is based on this observation.

THEOREM 2 The number of r-combinations of a set with n elements, where n is a nonnegative integer and
r is an integer with 0 ≤ r ≤ n, equals

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

Proof: The P (n, r) r-permutations of the set can be obtained by forming the C(n, r)
r-combinations of the set, and then ordering the elements in each r-combination, which can be
done in P(r, r) ways. Consequently, by the product rule,

P (n, r) = C(n, r) · P(r, r).

This implies that
P (n, r) n!/(n − r)! n!
C(n, r) = = = .
P(r, r) r!/(r − r)! r! (n − r)!

We can also use the division rule for counting to construct a proof of this theorem. Because the
order of elements in a combination does not matter and there are P(r, r) ways to order r elements
in an r-combination of n elements, each of the C(n, r) r-combinations of a set with n elements
P(n,r)
corresponds to exactly P(r, r) r-permutations. Hence, by the division rule, C(n, r) = ,
P(r,r)
n!
which implies as before that C(n, r) = .
r! (n−r)!
The formula in Theorem 2, although explicit, is not helpful when C(n, r) is computed for
large values of n and r. The reasons are that it is practical to compute exact values of factorials
exactly only for small integer values, and when floating point arithmetic is used, the formula in
Theorem 2 may produce a value that is not an integer. When computing C(n, r), first note that
when we cancel out (n − r)! from the numerator and denominator of the expression for C(n, r)
in Theorem 2, we obtain
n! n(n − 1) ··· (n − r + 1)
C(n, r) = = .
r! (n − r)! r!