Discrete Mathematics for Computer Science

The Principle of Inclusion-Exclusion 41

left to be given to G 3 .There is one way to return this hat to G 3 .Therefore, IH, n/H21 = 1.

By symmetry, IHt n /21 = IHt n/ H 31 = IH 2 n H 31 = 1. Finally, IH, n H 2 n H 31 = 1.

By the Principle of Inclusion-Exclusion, we compute I H 1 U H 2 U H31 as

I H, U H2 U H3 I = I H 1 I + I H2 I + I H 3 I- HI n1H21 - I H, nn 31

-I 12 n H 3 I + I H, nn 2 n H31

=2+2+2-1-1-1+1=4

That is, of the six possible ways to hand back the hats, in four of them at least one gentle-

man gets his own hat back. 0

1.5.4 Principle of Inclusion-Exclusion for Finitely Many Sets

Notice the alternating plus and minus signs in the Principle of Inclusion-Exclusion. For the

union of three sets, add the sizes of all the individual sets (intersections of one set), subtract

the sizes of the intersections of two sets, and add the size of the intersection of all three

sets. This alternation continues for computing the size of the union of more than three sets.

To state the next theorem neatly, we define two terms. Neither term is commonly used,

but each is quite understandable in the context of the Principle of Inclusion-Exclusion.

Definition 2. Let A 1 , A 2 ,..., A, be sets. An odd intersection from

A 1, A2,..... A.

is an intersection of an odd number of the Ai 's. An even intersection is an intersection of

an even, positive number of Ai 's.

Example 10. Let A 1 , A 2 , A 3 , A 4 , and A 5 be sets. Odd intersections are:

n = 1 : A 1 , A 2 , A 3 , A 4 , A 5

n = 3: A 1 n A 2 n A 3 , A 1 n A 2 n A 4 , A, A A 2 n A 5 , A 1 n A 3 n A 4 ,

A 1 A A 3 A A 5 , A 1 n A 4 n A 5 , A 2 n A 3 A A 4 , A 2 n A 3 n A 5 ,

A 2 n A 4 n A5, A 3 A A 4 n A 5

n = 5: A, A A 2 A A 3 A A 4 n A 5

Even intersections are:

n=0:0

n =2 : A 1 A A 2 , A 2 A A 3 , A 3 A A 4 , A 4 A A 5 ,

A, n A 3 , A 2 A A 4 , A 3 A A 5 ,

A 1 n A 4 , A 2 n A 5 ,

A 1 A A5

n = 4: A 1 n A 2 n A 3 A A 4 , A 1 A A 2 A A 3 A A 5 ,

A 1 n A 3 n A 4 n A 5 , A 2 A A 3 n A 4 n A5 U

Theorem 4. (Principle of Inclusion-Exclusion For Finitely Many Sets) Let A 1 , A 2 ,
A.... A, be finite sets (n > 1). Then, I A, U A 2 U ... U An I equals the sum of the
cardinalities of all odd intersections from A 1 , A 2 ... , An (including single sets) minus
the sum of the cardinalities of all even intersections from A 1 , A2 ..... An.