Discrete Mathematics for Computer Science

36 CHAPTER 1 Sets, Proof Templates, and Induction

Solution. Of the 834 people, 500 are females, so 334 are males. Of the 175 people at

least two meters tall, 10 are females. This says that there are at 175 - 10 = 165 males who

are at least two meters tall.

Since there are 334 males in total and 165 of them are at least two meters tall, there

are 169 = 334 - 165 males who are less than two meters tall. The situation is shown in

Figure 1.12.

Males Females

165 10 At least two

meters tall

169 490 Less than two

meters tall

Figure 1.12 Population characteristics.

In Example 5 we first counted how many males were at most two meters tall by di-

viding the set of all Atlanteans up into two sets, one consisting of all the females and the

other consisting of all the males. We did this correctly, because we knew the number of

Atlanteans and the number of females. We then made another such count to find the num-

ber of males who were at least two meters tall. We knew the total number of Atlanteans

who were at least two meters tall and the number of females who were at least two meters

tall. A simple subtraction gave the number of males at least two meters tall. We see that in

computing the size of both sets, we knew the size of two of the sets, and the two subsets

were disjoint. This result is an application of Theorem l(b) in Section 1.5.1. We next deal

with the case in which A and B are not disjoint.

1.5.2 Principle of Inclusion-Exclusion for Two Sets

Example 6. A deck of cards has four suits: Clubs, Diamonds, Hearts, and Spades. Dia-

monds and Hearts are called red suits; Clubs and Spades are called black suits. Each suit

contains 13 cards with values Ace(l), 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, and King. How

many cards are black or have the value of 3?

Solution. Let A be the set of black cards and B the set of 3's. The example asks for the

size of I A U B I. Clearly, I A I = 26, and I B I = 4. The problem is that two of the 3's are

also black. In this case, I A n B I # 0. The count I A I + I B I overcounts by I A n B I. The

answer is

IAUB = IAI+IBI-IAnBI =26+4-2=28 U

The card problem in Example 6 is a special example of the Principle of Inclusion-

Exclusion that we prove in more generality next.

Theorem 2. (Principle of Inclusion-Exclusion for Two Sets) Let A and B be finite

sets. Then,

IAUBI = IAI+IBI - IAnBI