Inclusion-Exclusion Principle: Examples with Solutions

A good understanding of the inclusion-exclusion principle in Discrete Mathematics is vital for building a solid foundation in set theory. With the inclusion-exclusion principle, there are generally two types of questions that appear in introductory and lower level Discrete Mathematics syllabi. In this article, we will discuss several inclusion-exclusion principle examples and solutions for both question types. Venn diagrams, although not essential, are useful in conceptualizing these types of questions.  The two question types are:

  1. The number of elements in certain sets are given as well as how many live in certain set intersections. It is then necessary to determine – to the exclusion of other sets – the number of elements living in a certain set or subset. (Hence, the ‘exclusion’ part of this principle.)
  2. The second type is more complex. The number of elements living in the intersection of sets are unknown and need to be determined. The unknown, i.e., the number of elements in the intersection, are given an algebraic numeral (such as x) and is then solved algebraically. Three sets are often involved.

 

Inclusion-Exclusion Principle: Example One (Two Sets)

Question:

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:

The first step is to formally identify the sets and indicate the number of elements in each. This can be done purely with the given information; No calculation is necessary. With this inclusion-exclusion principle question, the three sets can be defined as follows:

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

|P| = 25

|B| = 30

|P  B| = 10

We may now create a Venn diagram. There are two sets and therefore two circles. Since we know the number of elements in the intersection of P and B ( |P  B| ) we can fill this in first:

Now we can calculate how many elements live only in P but not |P  B|:

Since |P| = 25 and |P  B| = 10, there are 15 (25-10 = 15) elements exclusive to P.

Follow the same method to calculate the number of elements living only in B but not |P  B|:

Since |B| = 30 and |P  B| = 10, there are 20 (30-10 = 20) elements exclusive to B.

This new information should be added to our Venn diagram as follows:

venn-diagram-two-sets-solution

The preliminary work is complete and we have enough information to answer the questions directly:

(a) Determine the number of patients diagnosed with pneumonia or bronchitis (or both).

This is the same as asking to determine |P ∪ B|. Looking at the Venn diagram, formulate the answer as follows:

|P ∪ B| = 15 + 10 + 20

= 45

Thus 45 patients are diagnosed with pneumonia or bronchitis.

The same answer can also be reached by using the inclusion-exclusion principle directly without referring to the Venn diagram:

|P ∪ B| = |P| + |B| – |P ∪ B|

= (25 + 30) – (10)

= 45

Thus 45 patients are diagnosed with pneumonia or bronchitis.

 (b) Determine the number of patients not diagnosed with pneumonia or bronchitis.

This is the same as asking to determine |(P ∪ B)’|. We know that there are 50 patients altogether – of which 45 are diagnosed with pneumonia or bronchitis. Use this to solve the question:

|U| = 50.

|P ∪ B| = 45

Therefore,

|(P ∪ B)’|

= 50 – 45 = 5

5 patients are not diagnosed with pneumonia or bronchitis.

 

Inclusion-Exclusion Principle: Example Two (Three Sets)

Question:

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:

As done in the first inclusion-principle exercise problem above, start with defining the given information:

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 may now use a Venn diagram. It requires three circles since three sets are involved. Begin by populating the central intersection of all the three circles first:  J C P. Then use subtraction to determine the cardinality of the remaining sections.

 3-sets-venn-example-inclusion-exclusion-principle

We now have sufficient information in order to answer the question:

 Determine the number of computer programmers that are not proficient in any of these three languages.

In other words, 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|

= 39 + 5 +20 +4 +15 + 1

= 84

Now calculate the complement:

|(J ∪ C ∪ P)’ | = |U| – |J ∪ C ∪ P|

= 100 – 84

= 16           

16 programmers are not proficient in any of the three languages.

 

Inclusion-Exclusion Principle: Example Three (Three Sets)

This inclusion-exclusion principle question example can be solved algebraically.

Question:

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:

The letters for denoting the sets have already been provided in the question itself (unlike the above example). We may therefore note the cardinality straight away:

|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|. This is the unknown which we can assign determine algebraically.. Populate a Venn diagram with the given information. Use x to represent |B Y R|.

Let x farmers farm beetroot, yams, and radish. That is, let |B Y R| = x

inclusion-exclusion principle-problems-with-solutions

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.

Leave a Reply

Your email address will not be published. Required fields are marked *