Page 578 - Discrete Mathematics and Its Applications

8.5 Inclusion–Exclusion 557

Therefore, each element in the union is counted exactly once by the expression on the right-hand
side of the equation. This proves the principle of inclusion–exclusion.

The inclusion–exclusion principle gives a formula for the number of elements in the union
of n sets for every positive integer n. There are terms in this formula for the number of ele-
ments in the intersection of every nonempty subset of the collection of the n sets. Hence, there
n
are 2 − 1 terms in this formula.

EXAMPLE 5 Give a formula for the number of elements in the union of four sets.

Solution: The inclusion–exclusion principle shows that

|A 1 ∪ A 2 ∪ A 3 ∪ A 4 |=|A 1 |+|A 2 |+|A 3 |+|A 4 |

−|A 1 ∩ A 2 |−|A 1 ∩ A 3 |−|A 1 ∩ A 4 |−|A 2 ∩ A 3 |−|A 2 ∩ A 4 |
−|A 3 ∩ A 4 |+|A 1 ∩ A 2 ∩ A 3 |+|A 1 ∩ A 2 ∩ A 4 |+|A 1 ∩ A 3 ∩ A 4 |
+|A 2 ∩ A 3 ∩ A 4 |−|A 1 ∩ A 2 ∩ A 3 ∩ A 4 |.

Note that this formula contains 15 different terms, one for each nonempty subset of
{A 1 ,A 2 ,A 3 ,A 4 }. ▲

Exercises

1. How many elements are in A 1 ∪ A 2 if there are 12 ele- c) there are 50 common elements in each pair of sets and
ments in A 1 , 18 elements in A 2 , and 25 elements in all three sets.
a) A 1 ∩ A 2 =∅? b) |A 1 ∩ A 2 |= 1? d) the sets are equal.
6. Find the number of elements in A 1 ∪ A 2 ∪ A 3 if there are
c) |A 1 ∩ A 2 |= 6? d) A 1 ⊆ A 2 ?
100 elements in A 1 , 1000 in A 2 , and 10,000 in A 3 if
2. There are 345 students at a college who have taken a
course in calculus, 212 who have taken a course in dis- a) A 1 ⊆ A 2 and A 2 ⊆ A 3 .
b) the sets are pairwise disjoint.
crete mathematics, and 188 who have taken courses in c) there are two elements common to each pair of sets
both calculus and discrete mathematics. How many stu- and one element in all three sets.
dents have taken a course in either calculus or discrete 7. There are 2504 computer science students at a school. Of
mathematics?
these, 1876 have taken a course in Java, 999 have taken a
3. A survey of households in the United States reveals that course in Linux, and 345 have taken a course in C. Fur-
96% have at least one television set, 98% have telephone ther, 876 have taken courses in both Java and Linux, 231
service, and 95% have telephone service and at least have taken courses in both Linux and C, and 290 have
one television set. What percentage of households in the taken courses in both Java and C. If 189 of these students
United States have neither telephone service nor a televi- have taken courses in Linux, Java, and C, how many of
sion set? these 2504 students have not taken a course in any of
4. A marketing report concerning personal computers states these three programming languages?
that 650,000 owners will buy a printer for their machines 8. In a survey of 270 college students, it is found that 64 like
next year and 1,250,000 will buy at least one software brussels sprouts, 94 like broccoli, 58 like cauliflower, 26
package. If the report states that 1,450,000 owners will like both brussels sprouts and broccoli, 28 like both brus-
buy either a printer or at least one software package, how sels sprouts and cauliflower, 22 like both broccoli and
many will buy both a printer and at least one software cauliflower, and 14 like all three vegetables. How many
package? of the 270 students do not like any of these vegetables?
9. How many students are enrolled in a course either in cal-
5. Find the number of elements in A 1 ∪ A 2 ∪ A 3 if there culus, discrete mathematics, data structures, or program-
are 100 elements in each set and if
ming languages at a school if there are 507, 292, 312,
a) the sets are pairwise disjoint. and 344 students in these courses, respectively; 14 in both
b) there are 50 common elements in each pair of sets and calculus and data structures; 213 in both calculus and pro-
no elements in all three sets. gramming languages; 211 in both discrete mathematics