Page 577 - Discrete Mathematics and Its Applications

556 8 / Advanced Counting Techniques

S F
S F
S F
S S F F
S F R
S F R
S F
S R
S R
F R
F
S R F R
R R

FIGURE 4 The Set of Students Who Have Taken Courses
in Spanish, French, and Russian.

We will now state and prove the inclusion–exclusion principle, which tells us how many
elements are in the union of a finite number of finite sets.

THEOREM 1 THE PRINCIPLE OF INCLUSION–EXCLUSION Let A 1 ,A 2 ,...,A n be finite sets.
Then

|A 1 ∪ A 2 ∪ ··· ∪ A n |= |A i |− |A i ∩ A j |
1≤i≤n 1≤i<j≤n
n+1
+ |A i ∩ A j ∩ A k | − ··· + (−1) |A 1 ∩ A 2 ∩ ··· ∩ A n |.
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 A 1 ,A 2 ,...,A n where 1 ≤ r ≤ n. This element is counted C(r, 1) times by |A i |.Itis
counted C(r, 2) times by |A i ∩ A j |. In general, it is counted C(r, m) times by the summation
involving m of the sets A i . 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

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

Hence,

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