Inclusion - Exclusion Principle

The Principle of Inclusion and Exclusion (PIE) is a counting technique that

computes the number of elements that satisfy at least one of several properties
while guaranteeing that elements satisfying more than one property are not
counted twice.

An underlying idea behind PIE is that summing the number of elements that
satisfy at least one of two categories and subtracting the overlap
prevents double counting.

For instance, the number of people that have at least one cat or at least one dog
can be found by taking the number of people who own a cat, adding the number
of people that have a dog, then subtracting the number of people who have
both.

PIE is particularly useful in Combinatorics and Probability problem solving when

it is necessary to devise a counting method that ensures an object is not counted
twice.

The Inclusion – Exclusion Principle computes the cardinal number of the Union
of multiple non-disjoint sets.
For any 2 Finite Sets A and B, the principle states that:
|A U B| = |A| + |B| - |A  B|

For any 3 Finite Sets A, B, and C the principle states that:

|A U B U C| = |A| + |B| + |C| - |A  B| - |A  C| - |B  C| + |A  B  C|

Inclusion-Exclusion Principle says that for any number of finite sets A 1, A2, A3...
A i,
Union of the Sets is given by = Sum of sizes of all single sets – Sum of all 2-set
intersections + Sum of all the 3-set intersections – Sum of all 4-set intersections
.. + (-1)^{i+1} Sum of all the i-set intersections.
In General, it can be said that:

Properties:
1. Computes the total number of elements that satisfy at least one of
several properties.

2. It prevents the problem of Double Counting.

The formulation using the Venn Diagram of 3 Finite Sets A, B and C as:

Practice Questions based on 2 Finite Sets

Question 1:
Let A and B be two finite sets such that n(A) = 20, n(B) = 28 and n(A U B) = 36.
Find n(A  B).
Question 2:
If n(A – B) = 18, n(A U B) = 70 and n(A  B) = 25, then find n(B).

Question 3:
In a group of 60 people, 27 likes cold drinks and 42 likes hot drinks and each
person likes at least one of the two drinks. How many likes both the drinks ?

Question 4:
In a group of 100 persons, 72 people can speak English and 43 can speak French.
(i) How many can speak English only ?
(ii) How many can speak French only ?
(iii) How many can speak both English and French ?

Solutions:
Solution 1:
By applying the formula:
n(A U B) = n(A) + n(B) - n(A  B)
On putting the given values to the above formula, we have
n(A U B) = 20 + 28 – 36
= 48 – 36
= 12

Solution 2:
By applying the formula:
n(A U B) = n(A - B) + n(A  B) + n(B - A)
On putting the given values to the above formula, we have
70 = 18 + 25 + n(B - A)
70 = 43 + n(B - A)
n(B - A) = 70 – 43
n(B - A) = 27
Now, n(B) = n (A  B) + n(B - A)
= 25 + 27
= 52

Solution 3:
Let A = Set of people who like Cold drinks
B = Set of people who like Hot drinks
Given,
n(A U B) = 60, n(A) = 27, n(B) = 42
By applying the formula:
n(A U B) = n(A) + n(B) - n(A  B)
On putting the given values to the above formula, we have:
60 = 27 + 42 - n(A  B)
n(A  B) = 27 + 42 – 60
= 69 – 60
=9
Therefore, 9 people like both the drinks.

Solution 4:
Let A be the set of people who speak English, n(A) = 72
Let B be the set of people who speak French, n(B) = 43
(A – B) be the set of people who speak English but not French.
(B – A) be the set of people who speak French but not English.
(A  B) be the set of people who speak both English and French.
Here, n(A U B) = 100 ………… (Given)

Now, by applying the formula:

n(A U B) = n(A) + n(B) - n(A  B)
100 = 72 + 43 - n(A  B)
n(A  B) = 72 + 43 – 100
= 115 – 100
= 15
Therefore, number of persons who speak both English and French.

By applying the formula:

n(A) = n(A – B) + n(A  B)
72 = n(A – B) + 15
n(A – B) = 72 – 15 = 57

By applying the formula:

n(B) = n(B – A) + n(A  B)
43 = n(B – A) + 15
n(B – A) = 43 – 15 = 28

Therefore, the number of people speaking English only = n(A – B) = 57

The number of people speaking French only = n(B – A) = 28
Practice Questions based on 3 Finite Sets

Question 1:
In a competition, a school awarded medals in different categories. 36 medals in
Dance, 12 medals in Dramatics and 18 medals in Music. If these medals went to
a total of 45 persons and only 4 persons got medals in all the three categories.
How many received medals in exactly two of these categories ?

Question 2:
Each student in a class of 40 plays at least one indoor game chess, carrom, and
scrabble. 18 play chess, 20 play scrabble and 27 play carrom. 7 play chess and
scrabble, 12 play scrabble and carrom, and 4 play chess, carrom and scrabble.
Find the number of students who play (i) chess and carrom, (ii) chess, carrom
but not scrabble.

Question 3:

In a survey among 140 students, 60 likes to play videogames, 70 likes to play

indoor games, 75 likes to play outdoor games, 30 play indoor and outdoor
games, 18 like to play video games and outdoor games, 42 play video games and
indoor games and 8 likes to play all types of games. Use the Venn diagram to
find:

(i) Students who play only outdoor games.

(ii) Students who play video games and indoor games, but not outdoor games.

Question 4:

In a survey, it is found that 21 people read English newspaper, 26 people read

Hindi newspaper, and 29 people read regional language newspaper. If 14 people
read both English and Hindi newspapers; 15 people read both Hindi and regional
language newspapers; 12 people read both English and regional language
newspaper and 8 read all types of newspapers, find:
(i) How many people were surveyed?

(ii) How many people read only regional language newspapers?

Solutions:
Solution 1:
Let A = Set of persons who got medals in Dance
B = Set of persons who got medals in Dramatics
C = Set of persons who got medals in Music
Given,
n(A) = 36, n(B) = 12, n(C) = 18
n(A U B U C) = 45, n(A  B  C) = 4

We know that the number of elements belonging to exactly two of the three sets
A, B, C = n(A  B) + n(B  C) + n(C  A) – 3n(A  B  C)
= n(A  B) + n(B  C) + n(C  A) – 3 * 4 ------------------(i)
n(A U B U C) = n(A) + n(B) + n(C) – n(A  B) - n(B  C) - n(C  A) + n(A  B  C)
Therefore,
n(A  B) + n(B  C) + n(C  A) = n(A) + n(B) + n(C) + n(A  B  C) - n(A U B U C)
Now, putting the values in eq. (i), we get:
= n(A) + n(B) + n(C) + n(A  B  C) - n(A U B U C) – 12
= 36 + 12 + 18 + 4 – 45 – 12
= 70 – 67
=3
Solution 2:
Let A be the set of students who play chess
B be the set of students who play scrabble
C be the set of students who play carrom
n(A) = 18, n(B) = 20, n(C) = 27
n(A  B) = 7, n(C  B) = 12, n(A  B  C) = 4, n(A U B U C) = 40
By applying the formula, we have
n(A U B U C) = n(A) + n(B) + n(C) – n(A  B) - n(B  C) - n(C  A) + n(A  B  C)
40 = 18 + 20 + 27 – 7 – 12 - n(C  A) + 4
n(C  A) = 18 + 20 + 27 – 7 – 12 + 4 – 40
= 69 – 59
= 10
Therefore, the number of students who play chess and carrom are 10.
Also, the number of students who play chess, carrom and not scrabble
= n(C  A) - n(A  B  C)
= 10 – 4
=6

Solution 3:

Let V ≡ Play video games

I ≡ Play indoor games

O ≡ Play outdoor games

n(V) = 60, n(I) = 70, n(O) = 75

n(I ∩ O) = 30, n(V ∩ O) = 18, n(V ∩ I) = 42

n(V ∩ I ∩ O) = 8

Hence, by Venn diagram

(i) Number of students like to play only outdoor games = 35

(ii) Number of students like to play video games and indoor games but not
outdoor games = 34

Note: Always begin to fill the Venn diagram from the innermost part.

Solution 4:

Let A ≡ People who read English newspapers

B ≡ People who read Hindi newspapers

C ≡ People who read Regional Language newspapers

n(A) = 21, n(B) = 26, n(C) = 29

n(A ∩ B) = 14, n(B ∩ C) = 15, n(A ∩ C) = 12

n(A ∩ B ∩ C) = 8
(i) Number of people surveyed =

n(A ∪ B ∪ C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(B ∩ C) – n(A ∩ C) + n(A ∩ B ∩ C)

= 21 + 26 + 29 – 14 – 15 – 12 + 8 = 43

(ii) By the Venn diagram, number of people who only read Regional Language
newspapers = 10.