Discrete Mathematics for Computer Science

The Principle of Inclusion-Exclusion 35

Theorem 1. (Basic Counting Theorem) Let A and B be subsets of a finite universal

set U.

(a) Let B C A. Then:

i. IBI<IAI.

ii. IA-BI=IAI-IBI.

iii. IBI = IAlifandonlyifB =A.

(b) Let A and B be disjoint finite sets. Then, I A n B I = 0, and I A U B I = IA + I B

(c) IAI=IUI-IAI.

Proof. The proof is left to the reader. M

Example 2. The population of Atlanteas is 830, of which 250 are adult females and 380

are children.

(a) How many adults live in Atlanteas?

(b) How many adult males live in Atlanteas?

(c) How many "females and children" live in Atlanteas?

Solution. The universal set is U = {residents of Atlanteas}. The subsets of interest are

A = {adults}, F = {adult females), M = {adult males), and C = {children}

(a) AI =IUI - ICI =830 - 380 =450 (part (c))

(b) IMI = AI - IFI = 450 - 250 = 200 (since M C A use part (a))

(c) IFUCI = IFI + ICI -IFnCI =250+380-0=630 (since FnC = 0, usepart

(b))^0

The results in parts (a) and (b) of Theorem 1 are very special, because they make

strong assumptions about A and B. If these assumptions fail, the conclusions are generally

incorrect.

Example3. LetU={0,1,2),A={0,1},andB={1,2).

(a) Since A is not a subset of B, the hypothesis of part (a) does not hold. Neither does the

conclusion. JAI = I B I, but A # B, and IA - B I = 1 #0 = IA I - IBI.

(b) The sets A and B are not disjoint sets, so the hypothesis of part (b) does not hold. We
have IANBj= fl} = 1 #0 and IAUBI = 10,1,211 =3A4= iAI+IBI,
so neither conclusion holds.
A more interesting question is the cardinalities of I A n B I and I A U B I when neither
A nor B is a subset of the other and the sets are not disjoint. There are, of course, some
trivial truths, such as 0 < I A n B I and I A n B I < I A 1. What is interesting, however, is
the relationship between I A n B I and I A U B I. The reader should study the two examples
below and then, before reading any further, try to identify a pattern.

Example 4. Let A = {0, 1, 2, 3, 4, 5, 6, 7} and B = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13}. So,

I A I = 8, 1 B I = 10, I A n B I = 4, and I A U B I = 14.

Example 5. The population of Atlantis is 834, of which 500 are females. There are 175
people who are at least two meters tall, and only 10 of the females are at least two meters
tall. How many males are less than two meters tall?