264
Sets, Combinatorics, and Probability
Principle of inclusion and exclusion
To develop the principle of inclusion and exclusion, we first note that if A and B
are any subsets of a universal set S, then A − B, B − A, and A d B are mutually
disjoint sets (see Figure 4.6). For example, if x [ A − B, then x o B, therefore
x o B − A and x o A d B.
$
%
6
$G%
%±$
$±%
Also, something can be said about the union of these three sets.
figure 4.6
From Example 31 (extended to three disjoint finite sets),
0 (A − B) c (B − A) c (A d B) 0 = 0 A − B 0 + 0 B − A 0 + 0 A d B 0
(1)
From Example 32,
0 A − B 0 = 0 A 0 − 0 A d B 0
and
0 B − A 0 = 0 B 0 − 0 A d B 0
Using these expressions in Equation (1), along with the result of Practice 26, we get
0 A c B 0 = 0 A 0 − 0 A d B 0 + 0 B 0 − 0 A d B 0 + 0 A d B 0
or
0 A c B 0 = 0 A 0 + 0 B 0 − 0 A d B 0
(2)
Equation (2) is the two-set version of the principle of inclusion and exclusion.
The name derives from the fact that when counting the number of elements in
the union of A and B, we must “include” (count) the number of elements in A and
the number of elements in B, but we must “exclude” (subtract) those elements in
A d B to avoid counting them twice.
■
PraCtiCe 26 What is another name for the set (A − B) c (B − A) c (A d B)?