Page 575 - Discrete Mathematics and Its Applications

554 8 / Advanced Counting Techniques

A B = A + B – A B = 25 + 13 – 8 = 30 A B = A + B – A B = 142 + 90 – 12 = 220

A A BB
A B
A A A B BB A A A B BB

A = 25 A B = 8 B = 13 A = 142 A B = 12 B = 90

FIGURE 1 The Set of Students in a FIGURE 2 The Set of Positive Integers Not
Discrete Mathematics Class. Exceeding 1000 Divisible by Either 7 or 11.

Example 3 shows how to find the number of elements in a finite universal set that are outside
the union of two sets.

EXAMPLE 3 Suppose that there are 1807 freshmen at your school. Of these, 453 are taking a course in
computer science, 567 are taking a course in mathematics, and 299 are taking courses in both
computer science and mathematics. How many are not taking a course either in computer science
or in mathematics?

Solution: To find the number of freshmen who are not taking a course in either mathematics
or computer science, subtract the number that are taking a course in either of these subjects
from the total number of freshmen. Let A be the set of all freshmen taking a course in com-
puter science, and let B be the set of all freshmen taking a course in mathematics. It follows
that |A|= 453, |B|= 567, and |A ∩ B|= 299. The number of freshmen taking a course in
either computer science or mathematics is

|A ∪ B|=|A|+|B|−|A ∩ B|= 453 + 567 − 299 = 721.

Consequently, there are 1807 − 721 = 1086 freshmen who are not taking a course in computer
science or mathematics. ▲

We will now begin our development of a formula for the number of elements in the union
of a finite number of sets. The formula we will develop is called the principle of inclusion–
exclusion. For concreteness, before we consider unions of n sets, where n is any positive integer,
we will derive a formula for the number of elements in the union of three sets A, B, and C.To
construct this formula, we note that |A|+|B|+|C| counts each element that is in exactly one
of the three sets once, elements that are in exactly two of the sets twice, and elements in all three
sets three times. This is illustrated in the first panel in Figure 3.
To remove the overcount of elements in more than one of the sets, we subtract the number
of elements in the intersections of all pairs of the three sets. We obtain

|A|+|B|+|C|−|A ∩ B|−|A ∩ C|−|B ∩ C|.

This expression still counts elements that occur in exactly one of the sets once. An element that
occurs in exactly two of the sets is also counted exactly once, because this element will occur
in one of the three intersections of sets taken two at a time. However, those elements that occur
in all three sets will be counted zero times by this expression, because they occur in all three
intersections of sets taken two at a time. This is illustrated in the second panel in Figure 3.