The Inclusion-Exclusion Principle^{1}^{2}^{4}, Inclusion/Exclusion Rule^{3}, or similarly named technique is used in counting problems often found in mathematics and computer science. Most all Discrete Mathematics textbooks cover this rule in the topic of counting. This rule serves as a basis for later counting techniques.

As we saw with the Rule of of Sum, when there are different tasks that do not happen at the same time, we are able to add the number of ways to do each task together in order to find the total number of ways there are to perform a task. But, what happens if we need to count the number of ways when both tasks happen at the same time? In this case we can apply the Inclusion-Exclusion Principle.

The Inclusion-Exclusion Principle

If there are n ways of performing a task, and there are m ways of performing a second task, and these tasks are performed at the same time, then the total number of possible ways to perform the task is equal to (n + m) minus the elements they have in common. When n and m are added together, the elements they have in common are counting twice, hence we must subtract these out, once. This is derived from set theory, so the original formula looks like this for two sets of tasks:

N(A \cup B) = N(A) + N(B) - N(A \cap B)

where N() is the number of elements

Note this changes for more than two sets of tasks. Adding up the possible tasks from three sets looks like this:

N(A \cup B \cup C) = N(A) + N(B) + N(C) - N(A \cap B) - N(A \cap C) - N(B \cap C) + N(A \cap B \cap C)

Calculating the total number of possibilities becomes more complex as the number of sets being added together increases.

Example 1

Extending Example 1 from the post on the Rule of Sum, let us amend the original problem. One of the students is a grad student, but they are also an instructor. So, this person is being counted twice, once as a student and once as a faculty member. We need to remove the second count she is included in. So, by the Inclusion-Exclusion Principle we have:

N(A \cup B) = N(A) + N(B) - N(A \cap B)

N(students \cup faculty) = N(students) + N(faculty) - N(students \cap faculty)

N(A \cup B) = 63 + 7 - 1

From this, we know that the total number of ways to select a person for the vacancy is 69.

Example 2

How many bit strings of length 4 begins with a 11 or end with a 0?

The first criteria is to have a string that starts with a 11. From the the Rule of Product we know that there is one way to pick the first bit, 1, and one way to pick the second bit, 1. There are 2 ways to pick the third bit and 2 ways to choose the fourth bit, or 1 · 1 · 2 · 2, or 4 possible strings.

The second criteria is to choose a string that ends with a 0. From the the Rule of Product we know that there 2 ways to pick the first bit, 2 ways to pick the second bit, 2 ways to pick the third bit and 1 way to choose the fourth bit, 0, or 2 · 2 · 2 · 1, or 8 possible strings.

In this case we cannot apply the Rule of Sum as there is only one task, selecting a string that either starts with 11 or ends with a 0.

To better understand this, all strings starting with 11 are enumerated below:

0011

0111

1011

1111

And all the strings ending with 0 are enumerated below:

0000

0001

0010

0011

0100

0101

0110

0111

So, we can see the first set has 4 possibilities, and the second set has 8 possibilities. But look at the two sets, there are duplicates. Both 0011 and 0111 are shared between the sets. We don’t want to count them twice, so we will subtract these duplicates once to get the correct value. By the Inclusion-Exclusion Principle we know the total number of bit strings that start with 11 or end with a 0 is equal to N(A \cup B).

N(A \cup B) = 4 + 8 - 2

So, there are 10 strings that meet the original criteria.

*Wikipedia, The Free Encyclopedia*. Retrieved from https://en.wikipedia.org/w/index.php?title=Inclusion%E2%80%93exclusion_principle&oldid=1070925071

*Discrete mathematics and its applications*. (4th ed., pp. 239). WCB/McGraw-Hill. ISBN 0-07-289905-0.

*Discrete mathematics with applications*.(5th ed., pp.596). Cengage. ISBN 978-1-337-69419-3.

*Discrete mathematics*. (8th ed., pp.262). Pearson. ISBN-13 978-0321964687.