Section 4.3 Principle of Inclusion and Exclusion; Pigeonhole Principle
265
PraCtiCe 27 How does Equation (2) relate to Example 31 of Section 4.2?
■
example 40
A pollster queries 35 voters, all of whom support referendum 1, referendum 2, or
both, and finds that 14 voters support referendum 1 and 26 support referendum 2.
How many voters support both?
If we let A be the set of voters supporting referendum 1 and B be the set of
voters supporting referendum 2, then we know that
0 A c B 0 = 35
0 A 0 = 14
0 B 0 = 26
From Equation (2),
0 A c B 0 = 0 A 0 + 0 B 0 − 0 A d B 0
35 = 14 + 26 − 0 A d B 0
0 A d B 0 = 14 + 26 − 35 = 5
so 5 voters support both.
Equation (2) can easily be extended to three sets, as follows:
0 A c B c C 0 = 0 A c (B c C ) 0
= 0 A 0 + 0 B c C 0 − 0 A d (B c C ) 0
= 0 A 0 + 0 B 0 + 0 C 0 − 0 B d C 0 − 0 (A d B) c (A d C ) 0
= 0 A 0 + 0 B 0 + 0 C 0 − 0 B d C 0 − ( 0 A d B 0 + 0 A d C 0 − 0 A d B d C 0 )
= 0 A 0 + 0 B 0 + 0 C 0 − 0 A d B 0 − 0 A d C 0 − 0 B d C 0 + 0 A d B d C 0
Therefore the three-set version of the principle of inclusion and exclusion is
0 A c B c C 0 = 0 A 0 + 0 B 0 + 0 C 0 − 0 A d B 0 − 0 A d C 0 − 0 B d C 0 + 0 A d B d C 0
(3)
PraCtiCe 28 Justify each of the equalities used in deriving Equation (3).
■
In addition to the formal derivation of Equation (3) that we just did, a sort of
geometric argument for 0 A c B c C 0 is suggested by Figure 4.7 on the next page.
When we add 0 A 0 + 0 B 0 + 0 C 0 , we are counting each of 0 A d B 0 , 0 A d C 0 , and 0 B
d C 0 twice, so we must throw each of them away once. When we add 0 A 0 + 0 B 0
+ 0 C 0 , we are counting 0 A d B d C 0 three times, but in subtracting 0 A d B 0 ,
0 A d C 0 , 0 B d C 0 we have thrown it away three times, so we must add it back once.
265
PraCtiCe 27 How does Equation (2) relate to Example 31 of Section 4.2?
■
example 40
A pollster queries 35 voters, all of whom support referendum 1, referendum 2, or
both, and finds that 14 voters support referendum 1 and 26 support referendum 2.
How many voters support both?
If we let A be the set of voters supporting referendum 1 and B be the set of
voters supporting referendum 2, then we know that
0 A c B 0 = 35
0 A 0 = 14
0 B 0 = 26
From Equation (2),
0 A c B 0 = 0 A 0 + 0 B 0 − 0 A d B 0
35 = 14 + 26 − 0 A d B 0
0 A d B 0 = 14 + 26 − 35 = 5
so 5 voters support both.
Equation (2) can easily be extended to three sets, as follows:
0 A c B c C 0 = 0 A c (B c C ) 0
= 0 A 0 + 0 B c C 0 − 0 A d (B c C ) 0
= 0 A 0 + 0 B 0 + 0 C 0 − 0 B d C 0 − 0 (A d B) c (A d C ) 0
= 0 A 0 + 0 B 0 + 0 C 0 − 0 B d C 0 − ( 0 A d B 0 + 0 A d C 0 − 0 A d B d C 0 )
= 0 A 0 + 0 B 0 + 0 C 0 − 0 A d B 0 − 0 A d C 0 − 0 B d C 0 + 0 A d B d C 0
Therefore the three-set version of the principle of inclusion and exclusion is
0 A c B c C 0 = 0 A 0 + 0 B 0 + 0 C 0 − 0 A d B 0 − 0 A d C 0 − 0 B d C 0 + 0 A d B d C 0
(3)
PraCtiCe 28 Justify each of the equalities used in deriving Equation (3).
■
In addition to the formal derivation of Equation (3) that we just did, a sort of
geometric argument for 0 A c B c C 0 is suggested by Figure 4.7 on the next page.
When we add 0 A 0 + 0 B 0 + 0 C 0 , we are counting each of 0 A d B 0 , 0 A d C 0 , and 0 B
d C 0 twice, so we must throw each of them away once. When we add 0 A 0 + 0 B 0
+ 0 C 0 , we are counting 0 A d B d C 0 three times, but in subtracting 0 A d B 0 ,
0 A d C 0 , 0 B d C 0 we have thrown it away three times, so we must add it back once.