The Art and Craft of Problem Solving

6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION 213

Let us apply these simple concepts to get a new proof of the complement form of
PIE (6.3.6). Let the universal set U contain N elements, and without loss of generality,
suppose that we have just four sets AI, A 2 , A3, A4. Define No to be the number of
elements in U that have none of these properties. In other words, No is counting the
number of elements of U that are not in any of AI, A 2 , A 3 , A4. Define the function g(x)
by

g(x):= (l-lAI (x))(I-lA2(X))(I-lA 3 (X))(I-lA 4 (X)).

Then, by applying equations (6) and (7) we see (verify!) that g(x) = INo (x) and thus
(8) implies that (verify!)

In other words,

No = " g(x).

xti;

No = "(I-lAI (x))(I-lA 2 (X))(I-lA

xti;^3 (X))(I-lA^4 (X)).

When we multiply out the four factors in the right-hand side, we get

No = + " I

xti;

• " (lAI (x) + lA 2 (X) + lA 3 (X) + lA 4 (X))
  xti;

• " (lAI (X)lA 2 (x) + lAI (X)lA 3 (x) + lAI (X)lA 4 (x)
  xti;

+ lA 2 (X)lA 3 (x) + lA 2 (X)lA 4 (x) + lA 3 (X)lA 4 (x))

- " (lAI (X)lA2 (X)lA 3 (x) + lAI (X)lA 2 (X)lA 4 (x)

xti;

+ lAI (X)lA 3 (X)lA 4 (x) + lA

2 (X)lA^3 (X)lA 4 (x))

+ " (lAI (X)lA 2 (x)lA 3 (x)lA 4 (X)).

xti;

If we apply equations (6), (7) and (8), we see that this ugly sum is exactly the same as

No = N

Sl

• S (^2) ,
  S 3


• S 4
  using the notation of (6.3.6). In other words, we just demonstrated the truth of PIE for
  four sets. The argument certainly generalizes, for it uses only the algebraic fact that
  the expansion of
  (l-a)(l-b)(l-c)···