14.10. Combinatorial Proofs 587
for any nonempty setIŒ1::mç. This lets us calculate:
jSjD
ˇˇ
ˇ
ˇˇ
[m
iD 1
Cpi
ˇˇ
ˇ
ˇˇ (by (14.8))
D
X
;¤IŒ1::mç
. 1/jIjC^1
ˇˇ
ˇˇ
ˇ
\
i 2 I
Cpi
ˇˇ
ˇˇ
ˇ
(by Inclusion-Exclusion (14.6))
D
X
;¤IŒ1::mç
. 1/jIjC^1
n
Q
j 2 Ipj
(by (14.9))
D n
X
;¤IŒ1::mç
1
Q
j 2 I. pj/
D n
(^) m
Y
iD 1
1
1
pi
!
Cn;
so
.n/Dn jSjDn
Ym
iD 1
1
1
pi
;
which proves (14.7).
Yikes! That was pretty hairy. Are you getting tired of all that nasty algebra? If
so, then good news is on the way. In the next section, we will show you how to
prove some heavy-duty formulas without using any algebra at all. Just a few words
and you are done. No kidding.
14.10 Combinatorial Proofs
Suppose you havendifferent T-shirts, but only want to keepk. You could equally
well select thekshirts you want to keep or select the complementary set ofn k
shirts you want to throw out. Thus, the number of ways to selectkshirts from
amongnmust be equal to the number of ways to selectn kshirts from amongn.
Therefore:
n
k
!
D
n
n k
!
:
This is easy to prove algebraically, since both sides are equal to:
nŠ
kŠ .n k/Š