Page 433 - Discrete Mathematics and Its Applications

412 6 / Counting

and

n! n!
C(n, n − r) = = .
(n − r)![n − (n − r)]! (n − r)! r!
Hence, C(n, r) = C(n, n − r).

We can also prove Corollary 2 without relying on algebraic manipulation. Instead, we can
use a combinatorial proof. We describe this important type of proof in Definition 1.

DEFINITION 1 A combinatorial proof of an identity is a proof that uses counting arguments to prove that
both sides of the identity count the same objects but in different ways or a proof that is based
on showing that there is a bijection between the sets of objects counted by the two sides of
the identity. These two types of proofs are called double counting proofs and bijective proofs,
respectively.

Many identities involving binomial coefficients can be proved using combinatorial proofs. We
now show how to prove Corollary 2 using a combinatorial proof. We will provide both a double
counting proof and a bijective proof, both based on the same basic idea.
Combinatorial proofs
are almost always much
shorter and provide more
insights than proofs Proof: We will use a bijective proof to show that C(n, r) = C(n, n − r) for all integers n
based on algebraic and r with 0 ≤ r ≤ n. Suppose that S is a set with n elements. The function that maps a subset
manipulation.
A of S to A is a bijection between subsets of S with r elements and subsets with n − r elements
(as the reader should verify). The identity C(n, r) = C(n, n − r) follows because when there
is a bijection between two finite sets, the two sets must have the same number of elements.
Alternatively, we can reformulate this argument as a double counting proof. By definition,
the number of subsets of S with r elements equals C(n, r). But each subset A of S is also
determined by specifying which elements are not in A, and so are in A. Because the complement
of a subset of S with r elements has n − r elements, there are also C(n, n − r) subsets of S
with r elements. It follows that C(n, r) = C(n, n − r).

EXAMPLE 12 How many ways are there to select five players from a 10-member tennis team to make a trip to
a match at another school?

Solution: The answer is given by the number of 5-combinations of a set with 10 elements. By
Theorem 2, the number of such combinations is

10!
C(10, 5) = = 252. ▲
5! 5!

EXAMPLE 13 A group of 30 people have been trained as astronauts to go on the first mission to Mars. How
many ways are there to select a crew of six people to go on this mission (assuming that all crew
members have the same job)?
Solution: The number of ways to select a crew of six from the pool of 30 people is the number
of 6-combinations of a set with 30 elements, because the order in which these people are chosen
does not matter. By Theorem 2, the number of such combinations is

30! 30 · 29 · 28 · 27 · 26 · 25
C(30, 6) = = = 593,775.
6! 24! 6 · 5 · 4 · 3 · 2 · 1
▲