The Art and Craft of Problem Solving

choose from, so

6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION 211

IDnHI = C5^6 ).

By similar reasoning, ID n H n SI = ei). Notice that enD n H n S = 0, since it is
impossible to omit all four suits!
These sets are not just easy to compute with, they are useful as well, because
e u D u H uS consists of all hands for which at least one suit is absent. That is exactly
the complement of what we want!
Thus we will use PIE to compute Ie u D u H U S I, and subtract this result from
es

2

). We have

where

S) = ICI + IDI + IHI + lSI,

S 2 = lenDI + lenHI + lensl + IDnHI + IDnsl + IH nSI,

S 3 = lenDnHI+lenDnsl+lenHnsl+IDnHnsl,

S 4 = lenDnHnsl·

In other words,

The combination of PIE with counting the complement is so common that it is

worth noting (and verifying) the following alternative formulation of PIE.

6.3.6 Complement PIE. Given N items, and k sets A) , A 2 , ... ,Ab the number of these
items that lie in none of the A j is equal to

N -S) +S 2 - S 3 + ... ±Sb

where Si is the sum of the cardinalities of the intersections of the A j 's taken i at at time,
and the final sign is plus or minus, depending on whether k is even or odd.

The next example combines "Complement PIE" with other ideas, including the
useful encoding tool invent a fo nt, whereby we temporarily "freeze" several symbols
together to define a single new symbol.

Example 6.3.7 Four young couples are sitting in a row. In how many ways can we

seat them so that no person sits next to his or her "significant other?"

Solution: Clearly, there are 8! different possible seatings. Without loss of gener­

ality, let the people be boys and girls denoted by b) ,b 2 , b 3 ,b 4 ,g) ,g 2 ,g 3 ,g 4 , where we

assume that the couples are bi and gi, for i = 1 ,2,3,4. Define Ai to be the set of all

seatings for which hi and gi sit together. To compute lAd, we have two cases: either