The Art and Craft of Problem Solving

208 CHAPTER 6 COMBINATORICS

systematic way to handle these situations.

In simplest fonn, PIE states that the number of elements in the union of two sets is

equal to the sum of the number of elements in the sets minus the number of elements

in their intersection. Symbolically, we can write this as

IA UBI = IAI + IBI-IA nBI·

It is easy to see why this is true: Adding IAI and IBI overcounts the value of IA UBI.

This overcounting is not unifonn; we did not count everything twice, just the elements

of A nB. Consequently, we can correct for overcounting by subtracting IA nBI.

A bit of experimenting quickly leads to a conjecture for the general case of PIE

with n sets.

6.3.3 Ve rify that for three sets, PIE is

IAUBuCI = IAI + IBI + ICI-(IAnBI + IAncl + IBnCI)+ IAnBncl·

6.3.4 Ve rify that for four sets, PIE is

IAUBUCUDI =

+ (IAI + IBI + ICI + IDI)

• (IAnBI + IAncl + IAnDI + IBncl+ IBnDI + ICnDI)

• (IA nB nCi + IA nC nDI + IA nB nDI + IB nC nDI)
  -IAnBncnDI·

In general, we conjecture

The cardinality of the union of n sets =

+ (sum of the cardinalities of the sets)

• (sum of the cardinalities of all possible intersections of two sets)

• (sum of the cardinalities of all possible intersections of three sets)

± (the cardinality of the intersection of all n sets),

where the last tenn is negative if n is even, and positive is n is odd.

It is pretty easy to explain this infonnally. For example, consider the following

diagram, which illustrates the three-set situation.