Inclusion and Exclusion principle, Venn diagram, examples with solutions, set theory , Mathematics
In this article, you will learn all about the Principle of inclusion and exclusion. the principle of inclusion and exclusion explains how to find the total number of elements that belong to the particular set.
principle:
for two arbitrary set A and B the principle states as :
|AᴜB| = |A| + |B| – |A∩B|
|A∪B∪C| = |A| + |B| + |C| – | A∩B| – |A∩C| – |B∩C| + |A∩B∩C|
Examples:
example 1:
Suppose a survey of 100 people asks if they have a cat or dog as a pet. The results are as follows: 55 answered yes for the cat, 58 answered yes for dog and 20 people checked yes for both cat and dog. How many people have a cat or a dog?
solution:
the people who have a cat is denoted by set C
the people who have a dog is denoted by set D
|C| = 55
|D|= 58
|C∩D|= 20
by using the inclusion and exclusion principle:
|CᴜD| = |C| + |D| – |C∩D|
|CᴜD| = 55-58-20
|CᴜD| = 93
therefore, the total number of people who have either a cat or a dog is 93
Example 2:
Among 50 patients admitted to a hospital, 25 are diagnosed with pneumonia, 30 with
bronchitis, and 10 with both pneumonia and bronchitis. Determine:
(a) The number of patients diagnosed with pneumonia or bronchitis (or both).
(b) The number of patients not diagnosed with pneumonia or bronchitis.
Solution:
Let U denote the entire set of patients. Let P and B denote the set of patients diagnosed with
pneumonia and bronchitis respectively. Thus:
|U| = 50 # set of patients
|P| = 25 # set of patient who have pneumonia
|B| = 30 # set of patients who have bronchitis
|P ∩ B| = 10 # set of patients who have both
(a) Determine the number of patients diagnosed with pneumonia or bronchitis (or both).
|P ∪ B| = |P| + |B| – |P ∪ B|
|P ∪ B| = (25 + 30) – (10)
|P ∪ B| = 45
Thus 45 patients are diagnosed with pneumonia or bronchitis.
Example 3:
A survey in 1986 asked households whether they had a VCR, a CD player or cableTV. 40 had a VCR. 60 had a CD player; and 50 had cable TV. 25 owned VCR and CD player. 30 owned a CD player and had cable TV. 35 owned a VCR and had cable TV.10 households had all three. How many households had at least one of the three?
Solution:
let 𝑉 be the set of households with a VCR.
Let 𝐶 be the set of households with a CD player.
Let 𝑇 be the set of households with cable TV.
We have to find | V∪C∪T |
By inclusion-exclusion,
| V∪C∪T | = |V| + |C| + |T| − | V∩C | − | V∩T | − | C∩T | + | V∩C∩T |
Therefore, | V∪C∪T | = 40 + 60 + 50 − 25 − 30 − 35 + 10
| V∪C∪T |= 70
Example 4:
A large software development company employs 100 computer programmers. Of them, 45 are proficient in Java, 30 in C#, 20 in Python, six in C# and Java, one in Java and Python, five in C# and Python, and just one programmer is proficient in all three languages above. Determine the number of computer programmers that are not proficient in any of these three languages.
Solution:
Let U denote the set of all employed computer programmers and let J, C and P denote the set of programmers proficient in Java, C# and Python, respectively.
Thus:
|U| = 100
|J| = 45
|C| = 30
|P| = 20
|J ∩ C| = 6
|J ∩ P| = 1
|C ∩ P| = 5
|J ∩ C ∩ P| = 1
We need to determine the cardinality of the complement of the set J ∪ C ∪ P. (This is
denoted as |(J ∪ C ∪ P)’|).
Calculate |J ∪ C ∪ P| first before determining the complement value:
|J ∪ C ∪ P| = | J | + | C | + | P | - |J ∩ C| - |J ∩ P| - |C ∩ P| + |J ∩ C ∩ P|
|J ∪ C ∪ P| = 45 + 30 + 20 - 6 - 5 - 1 + 1
|J ∪ C ∪ P| = 84
Now calculate the complement:
|(J ∪ C ∪ P)’ | = |U| – |J ∪ C ∪ P|
|(J ∪ C ∪ P)’ |= 100 – 84
|(J ∪ C ∪ P)’ |= 16
16 programmers are not proficient in any of the three languages.
Example 5:
There are 350 farmers in a large region. 260 farm beetroot, 100 farm yams, 70 farm radish, 40 farm beetroot and radish, 40 farm yams and radish, and 30 farm beetroot and yams. Let B, Y, and R denote the set of farms that farm beetroot, yams, and radish respectively. Determine the number of farmers that farm beetroot, yams, and radish.
Solution:
given data:
|U| = 350
|B| = 260
|Y| = 100
|R| = 70
|B ∩ R| = 40
|Y ∩ R| = 40
|B ∩ Y| = 30
We need to determine the cardinality of the intersection of all three sets, which is |B ∩ Y ∩ R|.
Let x farmers farm beetroot, yams, and radish. That is, let |B ∩ Y ∩ R| = x
now solve for x algebraically:
|U|= 350 = 190 + x + (30 – x) + x + (40 – x) + (40 – x) + 30 + x + x – 10
350 = 320 + x
x = 30
Therefore, 30 farmers farm beetroot, yams, and radish.
Example 6:
How many integers are there between 1 and 1,000 which are not divisible by 2, 3, 5 or 7?
solution:
The total number of integers between 1 to 1000 is 1000.
A denotes the set of numbers which are divisible by 2
B denotes the set of numbers which are divisible by 3
C denotes the set of numbers which are divisible by 5
D denotes the set of numbers which are divisible by 7
| A | = 1000/2=500
| B | = 1000/3=300
| C | = 1000/5=200
| D | = 1000/7=142
|A ∩ B| = 1000/2*3=166
|A ∩ C| = 1000/2*5=100
|A ∩ D| = 1000/2*7= 71
|B ∩ C|= 1000/3*5=66
|B ∩ D| = 1000/3*7=47
|C ∩ D| = 1000/ 5*7 = 28
|A ∩ B ∩ C| = 1000/2*3*5=33
|A ∩ B ∩ D| = 1000/2*3*7 = 23
|A ∩ C ∩ D| = 1000/2*5*7=14
|B ∩ C ∩ D| = 1000/3*5*7 = 9
|A ∩ B ∩ C ∩ D| = 1000/2*3*5*7 = 4
By using the inclusion-exclusion principle:
|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D| − |A ∩ B| − |A ∩ C| − |A ∩ D| − |B ∩ C| − |B ∩ D| − |C ∩ D| + |A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D| − |A ∩ B ∩ C ∩ D|
by putting values
|A ∪ B ∪ C ∪ D| =500+300+200+142–166–100–71–47–28+33+23+14+9–4
|A ∪ B ∪ C ∪ D| = 772
the number of integers from 1 to 1000 which are divisible by 2,3,5 and 7 are 772
Comments
Post a Comment