Mathematics for Computer Science

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))

Dn

X

;¤IŒ1::mç

1

Q

j 2 I.pj/

Dn

(^) m
Y
iD 1



1

1

pi

!

Cn;

so

.n/DnjSjDn

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 ofnk

shirts you want to throw out. Thus, the number of ways to selectkshirts from

amongnmust be equal to the number of ways to selectnkshirts from amongn.

Therefore:

n

k

!

D

n

nk

!

:

This is easy to prove algebraically, since both sides are equal to:

nŠ

kŠ .nk/Š

: