The Inclusion-Exclusion Principle

Consider a two finite sets $A$ and $B$. Suppose that we want to determine the number of elements in $A \cup B$. If $A$ and $B$ are disjoint sets then we know by The Addition and Subtraction Principles that $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert$, so what do we do if $A$ and $B$ are not disjoint?

To explain this, consider the following venn-diagram representing the sets $A$ and $B$. If we count the number of elements in set $A$ which is $\lvert A \rvert$ and then add it to the number of elements in set $B$ which is $\lvert B \rvert$ then the sum $\lvert A \rvert + \lvert B \rvert$ over counts the total number of elements in $A \cup B$. In fact, as we can see in the diagram below, the number of elements in $A \cap B$ is counted twice:

It's not hard to therefore see that thus the total number of elements in $A \cup B$ is given by the formula:

(1)

\begin{align} \quad \lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert \end{align}

Note that the addition principle is simply a case of the formula above. If $A$ and $B$ are disjoint sets then $A \cap B = \emptyset$ and $\lvert A \cap B \rvert = \lvert \emptyset \rvert = 0$.

Now consider three finite sets and suppose once again we want to determine the number of elements in $A \cup B \cup C$. Once again, the sum $\lvert A \rvert + \lvert B \rvert + \lvert C \rvert$ over counts the total number of elements in this set. If we subtract the number of elements in the intersections between every set, i.e, subtraction $\lvert A \cap B \rvert$, $\lvert A \cap C$, and $\lvert B \cap C$ then we will need to add back the number of elements in $A \cap B \cap C$ as shown in the following venn diagram.

Therefore the total number of elements in $A \cup B \cup$ is given by:

(2)

\begin{align} \quad \lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert + \lvert C \rvert - \lvert A \cap B \rvert - \lvert A \cap C \rvert - \lvert B \cap C \rvert + \lvert A \cap B \cap C \rvert \end{align}

If we now consider four finite sets $A_1, A_2, A_3, A_4$ and we want to determine the number of elements in $A_1 \cup A_2 \cup A_3 \cup A_4$, then it's not hard to see by drawing a venn diagram that:

(3)

\begin{align} \quad \lvert A_1 + A_2 + A_3 + A_4 \rvert = \sum_{i \in \{ 1, 2, 3, 4 \}} \lvert A_i \rvert - \sum_{i, j \in \{1, 2, 3, 4\}}_{i \neq j} \lvert A_i \cap A_j \rvert + \sum_{i, j, k \in \{1, 2, 3, 4 \}}_{i \neq j, i\neq k, j \neq k} \lvert A_i \cap A_j \cap A_k \rvert - \sum_{i, j, k, l \in \{1, 2, 3, 4 \}}_{i \neq j, i \neq k, i \neq l, j \neq k, j \neq l, k \neq l} \lvert A_i \cap A_j \cap A_k \cap A_l \rvert \end{align}

The inclusion-exclusion principle given in the theorem below generalizes the pattern we have seen above for the number of elements in the union of a finite collection $A_1$, $A_2$, …, $A_n$ of finite sets.

Theorem 1 (The Inclusion-Exclusion Principle): Let $A_1, A_2, ..., A_n$ all be finite sets. Then $\displaystyle{\biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert = \sum_{i=1}^{n} \lvert A_i \rvert - \sum_{1 \leq p_1 < p_2 \leq n} \lvert A_{p_1} \cap A_{p_2} \rvert + \sum_{1 \leq p_1 < p_2 < p_3 \leq n} \lvert A_{p_1} \cap A_{p_2} \cap A_{p_3} \rvert - ... + (-1)^{n+1} \sum_{1 \leq p_1 < p_2 < ... < p_n \leq n} \lvert A_{p_1} \cap A_{p_2} \cap ... \cap A_{p_n} \rvert}$.

A more compact way to write the formula above is by noting that the inner sum below for $j$ ranging from $1$ to $k$ is over all of the subsets $A_{i_1}, A_{i_2}, ..., A_{i_k}$ where $i_k \in \{ 1, 2, ..., n \}$ so that:

(4)

\begin{align} \quad \biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert = \sum_{k=1}^{n} \left ( (-1)^k \cdot \sum \biggr \lvert \bigcap_{j=1}^{k} A_{i_j} \biggr \rvert \right ) \end{align}