15.12. The Pigeonhole Principle 479
Teaching Assistants. Here is another colorful example of a combinatorial argu-
ment.
Theorem 15.11.2. n
X
rD 0
n
r
!
2n
n r
!
D
3n
n
!
Proof. We give a combinatorial proof. LetSbe alln-card hands that can be dealt
from a deck containingndifferent red cards and2ndifferent black cards. First,
note that every3n-element set has
jSjD
3n
n
!
n-element subsets.
From another perspective, the number of hands with exactlyrred cards is
n
r
!
2n
n r
!
since there are
n
r
ways to choose therred cards and
2n
n r
ways to choose the
n rblack cards. Since the number of red cards can be anywhere from 0 ton, the
total number ofn-card hands is:
jSjD
Xn
rD 0
n
r
!
2n
n r
!
:
Equating these two expressions forjSjproves the theorem.
Finding a Combinatorial Proof
Combinatorial proofs are almost magical. Theorem 15.11.2 looks pretty scary, but
we proved it without any algebraic manipulations at all. The key to constructing a
combinatorial proof is choosing the setSproperly, which can be tricky. Generally,
the simpler side of the equation should provide some guidance. For example, the
right side of Theorem 15.11.2 is
3n
n
, which suggests that it will be helpful to
chooseSto be alln-element subsets of some3n-element set.
15.12 The Pigeonhole Principle
Here is an old puzzle:
