Inclusion–exclusion principle

How many letters are in the combined alphabet of English and Russian? That seems simple… just add the number of letters in the English alphabet ($26$) and the number of letters in the Russian alphabet ($33$), right? $26+33=59$ letters?

But that's wrong because there are letters, like A, B, and E, that appear in both English and Russian alphabets. So, with this approach, you count some letters twice. The problem with this example is that the two alphabets are not disjoint.

In this topic, you will learn how to use the Inclusion-Exclusion Principle to solve examples like these.

Case of two sets

In a previous topic, you looked at the Rule of Sum. This rule states that if sets $A$ and $B$ are disjoint, then the number of elements in the union of these two sets is equal to the sum of the number of elements in the individual sets.

What if sets $A$ and $B$ are not disjoint? By taking the sum, you double-count the elements that are in both sets. So, you need to correct this by subtracting the intersection of sets $A$ and $B$.

When sets $A$ and $B$ are disjoint, $|A \cap B| = 0$. This is how you get the formula for the Rule of Sum.

Let's revisit our example from the introduction. How many letters are in the combined alphabet of English and Russian? In other words, how many elements are in the union of the set of letters in the English alphabet and the set of letters in the Russian alphabet?

There are $26$ letters in the English alphabet and $33$ in Russian. There are $12$ letters in common. By the Inclusion-Exclusion Principle, there are $26 + 33 - 12 = 47$ letters in their combined alphabet.

Case of three sets

Here's how to derive this formula through reasoning. When you sum $|A| + |B| + |C|$, you are counting the elements in the intersections of each two sets twice and the elements in the intersection of all three sets three times. So, you subtract $|A \cap B|$, $|A \cap C|$, and $|B \cap C|$. However, doing this removes the counting of the intersection of all three sets, so you have to add $|A \cap B \cap C|$ back in.

Let's look at an example. Suppose that there is a programming contest that consists of three tasks A, B, and C. The total number of participants is $1000$. $700$ participants solved task A, $600$ solved task B, and $600$ solved task C. Moreover, $500$ participants solved both tasks A and B, $400$ solved both B and C, and $400$ solved both A and C. $300$ participants solved all tasks. How many participants did not solve any task? Note that when we say "$700$ participants solved task A", we mean that $700$ participants in total solved task A — these participants may have also solved other tasks.

You want to find the number of participants that solved zero tasks. That is, you want to find $|U| - |A \cup B \cup C|$.

There are $1000$ participants in total, so $|U| = 1000$.

$|A|$, $|B|$, and $|C|$ are $700$, $600$, and $600$, respectively.

Since $500$ participants solved both tasks A and B, $|A \cap B| = 500$. Likewise, $|B \cap C| = 400$ and $|A \cap C| = 400$.

$300$ participants solved all three tasks, so $|A \cap B \cap C| = 300$.

By the Inclusion-Exclusion Principle,

$$|A \cup B \cup C| = |A| + |B| + |C|- |A \cap B| - |A \cap C| -|B \cap C| + |A \cap B \cap C|$$$$= 700 + 600 + 600 - 500 - 400 - 400 + 300 = 900$$So, $900$ people solved at least one task.

Now, let's find the number of participants that did not solve any task.

$$|U| - |A \cup B \cup C| = 1000 - 900 = 100$$Therefore, $100$ participants solved zero tasks.

The following image is a Venn diagram that shows the number of the participants in each region.

Conclusion

In this topic, you looked at the Inclusion-Exclusion Principle. It allows you to determine how many elements are in the union of overlapping sets. The general idea behind this principle is that you must consider the number of elements in the overlapping regions to avoid double counting.