Section 4.3 Principle of Inclusion and Exclusion; Pigeonhole Principle
267
example 42
A produce stand sells only broccoli, carrots, and okra. One day the stand served
207 people. If 114 people purchased broccoli, 152 purchased carrots, 25 purchased
okra, 64 purchased broccoli and carrots, 12 purchased carrots and okra, and 9 purchased all three, how many people purchased broccoli and okra?
Let
A = {people who purchased broccoli}
B = {people who purchased carrots}
C = {people who purchased okra}
Then 0 A c B c C 0 = 207, 0 A 0 = 114, 0 B 0 = 152, 0 C 0 = 25, 0 A d B 0 = 64, 0 B d C 0 = 12,
and 0 A d B d C 0 = 9. From Equation (3),
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
207 = 114 + 152 + 25 − 64 − 0 A d C 0 − 12 + 9
0 A d C 0 = 114 + 152 + 25 − 64 − 12 + 9 − 207 = 17
In Equation (2), we add the number of elements in the single sets and subtract
the number of elements in the intersection of two sets. In Equation (3), we add the
number of elements in the single sets, subtract the number of elements in the intersection of two sets, and add the number of elements in the intersection of three
sets. This seems to suggest a pattern: If we have n sets, we should add the number
of elements in the single sets, subtract the number of elements in the intersection
of two sets, add the number of elements in the intersection of three sets, subtract
the number of elements in the intersection of four sets, and so on. This leads us to
the general form of the principle of inclusion and exclusion:
In Equation (4) the notation
∙
1≤i
for example, says to add together the number of elements in all the intersections of
the form A i d A j where i and j can take on any values between 1 and n as long as i < j.
pRinciple Of iNClUSiON aNd exClUSiON
Given the finite sets A 1 , c , A n, n ≥ 2, then
0 A 1 c c c A n 0 = ∙
1≤i≤n
0 A i 0 − ∙
1≤i
+
∙
1≤i
− c + (−1)
n+1
0 A 1 d c d A n 0
(4)
267
example 42
A produce stand sells only broccoli, carrots, and okra. One day the stand served
207 people. If 114 people purchased broccoli, 152 purchased carrots, 25 purchased
okra, 64 purchased broccoli and carrots, 12 purchased carrots and okra, and 9 purchased all three, how many people purchased broccoli and okra?
Let
A = {people who purchased broccoli}
B = {people who purchased carrots}
C = {people who purchased okra}
Then 0 A c B c C 0 = 207, 0 A 0 = 114, 0 B 0 = 152, 0 C 0 = 25, 0 A d B 0 = 64, 0 B d C 0 = 12,
and 0 A d B d C 0 = 9. From Equation (3),
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
207 = 114 + 152 + 25 − 64 − 0 A d C 0 − 12 + 9
0 A d C 0 = 114 + 152 + 25 − 64 − 12 + 9 − 207 = 17
In Equation (2), we add the number of elements in the single sets and subtract
the number of elements in the intersection of two sets. In Equation (3), we add the
number of elements in the single sets, subtract the number of elements in the intersection of two sets, and add the number of elements in the intersection of three
sets. This seems to suggest a pattern: If we have n sets, we should add the number
of elements in the single sets, subtract the number of elements in the intersection
of two sets, add the number of elements in the intersection of three sets, subtract
the number of elements in the intersection of four sets, and so on. This leads us to
the general form of the principle of inclusion and exclusion:
In Equation (4) the notation
∙
1≤i
for example, says to add together the number of elements in all the intersections of
the form A i d A j where i and j can take on any values between 1 and n as long as i < j.
pRinciple Of iNClUSiON aNd exClUSiON
Given the finite sets A 1 , c , A n, n ≥ 2, then
0 A 1 c c c A n 0 = ∙
1≤i≤n
0 A i 0 − ∙
1≤i
+
∙
1≤i
− c + (−1)
n+1
0 A 1 d c d A n 0
(4)