The Art and Craft of Problem Solving

210 CHAPTER 6 COMBINATORICS

will be G) intersections of pairs of these sets, and for each of them, we will count x

once. Hence S 2 counts x exactly G) times. In general, Sk counts the element x exactly

(D times. If k > r, then Sk is a sum of cardinalities of intersections of k > r sets, and

none of these sets can contain x, which only lies in r sets! And of course, Sr counts x

exactly once (i.e., (�) times), since there is only one intersection of r sets that actually

contains x.

We have reduced PIE, then, to proving the identity

Recall that r = m and I = (�), so the above equality has the equivalent formulation

(�)

G)

+

(;)

+".+(-ly

G)

=^0 , (5)

which was part of problem 6.1. 22. One can prove equation (5) easily in at least three

different ways. Try them all!

• Induction plus the summation identity (6. 1.14 ) of Pascal's Triangle;


• A direct examination of the elements in Pascal's Triangle, using the symmetry
  identity (6.1.1 3 ) and the summation identity;


• The slickest way, perhaps: Just expand 0 = ( 1 - 1 Y with the binomial theorem
  and you immediately get (5)!

In any event, now that we know that (5) is true, we have proven PIE. •

A few examples will convince you of the power in PIE. The key to approaching

these problems is a flexible attitude about whether to count something or its comple­

ment.

Example 6.3.5 How many five-card hands from a standard deck of cards contain at

least one card in each suit?

Solution: First note that there are e 52 ) possible hands, since the order of the cards

in a hand is immaterial. Whenever you the words "at least," you should be alerted to

the possibility of counting complements. Which is easier to compute: the number of

suits containing no diamonds, or the number of suits containing at least one diamond?

Certainly the former is easier to calculate; if there are no diamonds, then there are only

52 - 13 = 39 cards to choose from, so the number of hands with no diamonds is ei).

This suggests that we define as our "foundation" sets C, D, H, S to be the sets of hands

containing no clubs, diamonds, hearts, spades, respectively. Not only do we have

Ie! = IDI = IHI = lSI = c: ),

but the intersections are easy to compute as well. For example, D n H is the set of

hands that contain neither diamonds nor hearts. There are 52 - 2. 1 3 = 26 cards to