8.

5 Inclusion–Exclusion 579

61. Let m be a positive integer. Let Xm be the random vari- b) Find the expected value and the variance of Xm using
able whose value is n if the mth success occurs on the Exercise 59 and the closed form for the probability
(n + m)th trial when independent Bernoulli trials are per- generating function in part (a).
formed, each with probability of success p. 62. Show that if X and Y are independent random variables
a) Using Exercise 32 in the Supplementary Exercises of on a sample space S such that X(s) and Y(s) are nonneg-
Chapter 7, show that the probability generating func- ative integers for all s ∈ S, then GX+Y (x) = GX (x)GY (x).
tion GXm is given by GXm (x) = pm ∕(1 − qx)m , where
q = 1 − p.

8.5 Inclusion–Exclusion
8.5.1 Introduction
A discrete mathematics class contains 30 women and 50 sophomores. How many students in
the class are either women or sophomores? This question cannot be answered unless more in-
formation is provided. Adding the number of women in the class and the number of sophomores
probably does not give the correct answer, because women sophomores are counted twice. This
observation shows that the number of students in the class that are either sophomores or women
is the sum of the number of women and the number of sophomores in the class minus the num-
ber of women sophomores. A technique for solving such counting problems was introduced
in 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.

8.5.2 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 math-
ematics) 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. ◂
580 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>
∩B B A A>
∩B B

∣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 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. ◂

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 sci-
ence 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 ei-
ther computer science or mathematics is

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

 8.5 Inclusion–Exclusion 581

1 1 1 1 1 1
2 1 1
A B A B A B

3 0 1
2 2 1 1 1 1

1 1 1

C C C

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

∣A∣ + ∣B∣ + ∣C∣ ∣A∣ + ∣B∣ + ∣C∣ – ∣A ∩ B∣ – ∣A∣ + ∣B∣ + ∣C∣ – ∣A ∩ B∣ –
∣A ∩ C∣ – ∣B ∩ C∣ ∣A ∩ C∣ – ∣B ∩ C∣ + ∣A ∩ B ∩ C∣

FIGURE 3 Finding a formula for the number of elements in the union of three sets.

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.
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
582 8 / Advanced Counting Techniques

∣S ∩ F ∩ R∣ = ? ∣S ∩ F∣ = 103

S S∩F F

S∩F∩R

S∩R F∩R

∣S∣ = 1232 ∣F∣ = 879

R
∣S ∩ R∣ = 23 ∣F ∩ R∣ = 14

∣R∣ = 114
∣S ∪ F ∪ R∣ = 2092

FIGURE 4 The set of students who have taken courses

in Spanish, French, and Russian.

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. ◂

We will now state and prove the inclusion–exclusion principle for n sets, where n is a
positive integer. This priniciple tells us that we can count the elements in a union of n sets by
adding the number of elements in the sets, then subtracting the sum of the number of elements
in all intersections of two of these sets, then adding the number of elements in all intersections
 8.5 Inclusion–Exclusion 583

of three of these sets, and so on, until we reach the number of elements in the intersection of
all the sets. It is added when there is an odd number of sets and added when there is an even
number of sets.

THEOREM 1 THE PRINCIPLE OF INCLUSION–EXCLUSION Let A1 , A2 , … , An be finite sets.

Then
∑ ∑
|A1 ∪ A2 ∪ ⋯ ∪ An | = |Ai | − |Ai ∩ Aj |
1≤i≤n 1≤i<j≤n
∑
+ |Ai ∩ Aj ∩ Ak | − ⋯ + (−1)n+1 |A1 ∩ A2 ∩ ⋯ ∩ An |.
1≤i<j<k≤n

Proof: We will prove the formula by showing that an element in the union is counted exactly
once by the right-hand side of the equation. Suppose that a is a member of exactly r of the sets
A1 , A2 , … , An where 1 ≤ r ≤ n. This element is counted C(r, 1) times by Σ|Ai |. It is counted
C(r, 2) times by Σ|Ai ∩ Aj |. In general, it is counted C(r, m) times by the summation involving
m of the sets Ai . Thus, this element is counted exactly

C(r, 1) − C(r, 2) + C(r, 3) − ⋯ + (−1)r+1 C(r, r)

times by the expression on the right-hand side of this equation. Our goal is to evaluate this
quantity. By Corollary 2 of Section 6.4, we have

C(r, 0) − C(r, 1) + C(r, 2) − ⋯ + (−1)r C(r, r) = 0.

Hence,

1 = C(r, 0) = C(r, 1) − C(r, 2) + ⋯ + (−1)r+1 C(r, r).

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
are 2n − 1 terms in this formula.

EXAMPLE 5 Give a formula for the number of elements in the union of four sets.
Extra
Examples Solution: The inclusion–exclusion principle shows that

|A1 ∪ A2 ∪ A3 ∪ A4 | = |A1 | + |A2 | + |A3 | + |A4 |

− |A1 ∩ A2 | − |A1 ∩ A3 | − |A1 ∩ A4 | − |A2 ∩ A3 | − |A2 ∩ A4 |
− |A3 ∩ A4 | + |A1 ∩ A2 ∩ A3 | + |A1 ∩ A2 ∩ A4 | + |A1 ∩ A3 ∩ A4 |
+ |A2 ∩ A3 ∩ A4 | − |A1 ∩ A2 ∩ A3 ∩ A4 |.

Note that this formula contains 15 different terms, one for each nonempty subset of
{A1 , A2 , A3 , A4 }. ◂