Discrete Mathematics for Computer Science

The Principle of Inclusion-Exclusion 37

The number of elements in the union of two finite sets is the sum of the number of elements

in each of the sets minus the number of elements in their intersection. A Venn diagram for

these sets is shown in Figure 1.13.

U

A B

ArnB

Figurel.13 IAuBI.

(What the proof entails.) What procedure could be used to count the elements in A U B?

First, count all the elements of A. Then, count all the elements of B. In the process,

all the elements of A n B have been counted twice, so subtract I A n B I to compen-

sate.

Proof The set AUB=(A-B) U(AAB)U(B-A), and any pair of (A-B),

(A n B), and (B - A) are disjoint (Theorem 6 in Section 1.3.2). It follows immediately

that (A - B) and (A n B) U (B - A) are also disjoint. Hence, by using Theorem l(b) of

this section, we get

IA U B I =IA - B I + I (AN B) U (B - A)I

=I[A--BI+IANBF+IB--AI

By Theorem 6(b)

IAI=IA-BI+IANBI

IBI = IAnBI-+-IB- AI

Putting the last two equations together gives

I A I+ IB I=A - BI+2. 1AAnB I+ IB -A I

IAI+IBI-IAnBI = IA-BI+IAABI+IB-AI

Now, substituting this into the equation for I A U B I, we get the required result:

IAUBI=IAI+IBI-IAnBI I

1.5.3 Principle of Inclusion-Exclusion for Three Sets

U
Figurel.14 IAuBUCI. A B

C