Page 576 - Discrete Mathematics and Its Applications

8.5 Inclusion–Exclusion 555

1 1 1 1 1 1
2 1 1
A B
A B A B
3 0 0 0 0 1
2 2 2 1 1 1 1 1 1 1

1 1 1 1 1 1
C C C C C C

(a) Count of elements by (b) Count of elements by (c) Count of elements by

FIGURE 3 Finding a Formula for the Number of Elements in the Union of Three Sets.

To remedy this undercount, we add the number of elements in the intersection of all three
sets. This final expression counts each element once, whether it is in one, two, or three of the
sets. Thus,

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

This formula is illustrated in the third panel of Figure 3.
Example 4 illustrates how this formula can be used.

EXAMPLE 4 A total of 1232 students have taken a course in Spanish, 879 have taken a course in French,
and 114 have taken a course in Russian. Further, 103 have taken courses in both Spanish and
French, 23 have taken courses in both Spanish and Russian, and 14 have taken courses in both
French and Russian. If 2092 students have taken at least one of Spanish, French, and Russian,
how many students have taken a course in all three languages?

Solution: Let S be the set of students who have taken a course in Spanish, F the set of students
who have taken a course in French, and R the set of students who have taken a course in Russian.
Then

|S|= 1232, |F|= 879, |R|= 114,
|S ∩ F|= 103, |S ∩ R|= 23, |F ∩ R|= 14,

and

|S ∪ F ∪ R|= 2092.

When we insert these quantities into the equation

|S ∪ F ∪ R|=|S|+|F|+|R|−|S ∩ F|−|S ∩ R|−|F ∩ R|+|S ∩ F ∩ R|

we obtain

2092 = 1232 + 879 + 114 − 103 − 23 − 14 +|S ∩ F ∩ R|.

We now solve for |S ∩ F ∩ R|.We find that |S ∩ F ∩ R|= 7.Therefore, there are seven students
who have taken courses in Spanish, French, and Russian. This is illustrated in Figure 4. ▲