Page 574 - Discrete Mathematics and Its Applications

8.5 Inclusion–Exclusion 553

Section 6.1. In this section we will generalize the ideas introduced in that section to solve
problems that require us to count the number of elements in the union of more than two sets.

The Principle of Inclusion–Exclusion

How many elements are in the union of two finite sets? In Section 2.2 we showed that the number
of elements in the union of the two sets A and B is the sum of the numbers of elements in the
sets minus the number of elements in their intersection. That is,

|A ∪ B|=|A|+|B|−|A ∩ B|.

As we showed in Section 6.1, the formula for the number of elements in the union of two sets
is useful in counting problems. Examples 1–3 provide additional illustrations of the usefulness
of this formula.
EXAMPLE 1 In a discrete mathematics class every student is a major in computer science or mathematics,
or both. The number of students having computer science as a major (possibly along with
mathematics) is 25; the number of students having mathematics as a major (possibly along with
computer science) is 13; and the number of students majoring in both computer science and
mathematics is 8. How many students are in this class?

Solution: Let A be the set of students in the class majoring in computer science and B be the set
of students in the class majoring in mathematics. Then A ∩ B is the set of students in the class
who are joint mathematics and computer science majors. Because every student in the class
is majoring in either computer science or mathematics (or both), it follows that the number of
students in the class is |A ∪ B|. Therefore,

|A ∪ B|=|A|+|B|−|A ∩ B|
= 25 + 13 − 8 = 30.

Therefore, there are 30 students in the class. This computation is illustrated in Figure 1. ▲

EXAMPLE 2 How many positive integers not exceeding 1000 are divisible by 7 or 11?

Solution: Let A be the set of positive integers not exceeding 1000 that are divisible by 7, and
let B be the set of positive integers not exceeding 1000 that are divisible by 11. Then A ∪ B
is the set of integers not exceeding 1000 that are divisible by either 7 or 11, and A ∩ B is the
set of integers not exceeding 1000 that are divisible by both 7 and 11. From Example 2 of
Section 4.1, we know that among the positive integers not exceeding 1000 there are 1000/7
integers divisible by 7 and 1000/11
divisible by 11. Because 7 and 11 are relatively prime,
the integers divisible by both 7 and 11 are those divisible by 7 · 11. Consequently, there are
1000/(11 · 7)
positive integers not exceeding 1000 that are divisible by both 7 and 11. It
follows that there are

|A ∪ B|=|A|+|B|−|A ∩ B|

1000 1000 1000
= + −
7 11 7 · 11
= 142 + 90 − 12 = 220

positive integers not exceeding 1000 that are divisible by either 7 or 11. This computation is
illustrated in Figure 2. ▲