Math Home
Combinatorics

Inclusion-exclusion

The addition rule only applies to disjoint sets. If the sets are not disjoint, you can count the total using inclusion-exclusion.



Inclusion-exclusion principle for \(2\) sets: For any \(2\) sets \(A\) and \(B,\) \[|A \cup B| = |A| + |B| - |A \cap B|\]

▼ Proof for \(2\) sets. We prove \[|A \cup B| = |A| + |B| - |A \cap B|\]

The elements of \(A\) are all either elements of \(B\) or they are not. The elements of \(A\) that are elements of \(B\) are elements of \(A \cap B.\) The elements of \(A\) that are not elements of \(B\) are elements of \(A \cap B^C.\) Therefore, \[A = (A \cap B) \cup (A \cap B^C).\] Therefore, we can write \[A \cup B = (A \cap B) \cup (A \cap B^C) \cup B\] Also, \((A \cap B) \cup B = B\) since \(A \cap B \subset B.\) So, \[A \cup B = (A \cap B^C) \cup B\] The sets \(A \cap B^C\) and \(B\) are disjoint, so by the addition rule \[|(A \cap B^C) \cup B| = |A \cap B^C| + |B|\] which implies \[|A \cup B| = |A \cap B^C| + |B|\] Since \(A\) can be written as the union of two disjoint sets as \(A = (A \cap B) \cup (A \cap B^C),\) the addition rule also gives us \[|A| = |A \cap B| + |A \cap B^C|\] Rearranging, we have \[|A \cap B^C| = |A| - |A \cap B|\] So, \begin{align} |A \cup B| & = |A \cap B^C| + |B| \\ & = |A| + |B| - |A \cap B| \end{align}


Inclusion-exclusion principle for \(3\) sets: For any \(3\) sets \(A, B\) and \(C,\) \[|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cup B \cup C|\]

Inclusion-exclusion principle for \(n\) sets: Suppose you have sets \(A_1, A_2, \dots, A_n\) with index set \(I = \{1, 2, \dots, n\}.\) For each \(i \in I,\) let \(J_i\) be the set of all subsets of \(I\) of cardinality \(i.\) Then \[\left|\bigcup_{i = 1}^n A_i\right| = \sum_{i=1}^n \left[(-1)^{i-1}\sum_{J \in J_i}\left|\bigcap_{j \in J}A_j\right|\right]\]



Examples:

Example to explain the formula:
Let \(A_1 = \{1,2,3,4\},\) \(A_2 = \{2,4,5,6\},\) and \(A_3=\{4,5,7\}.\) The index set is \(I = \{1,2,3\}.\)

The set \(J_1\) is the set of all one point subsets of the index set: \(J_1 = \{\{1\}, \{2\}, \{3\}\}\)
The set \(J_2\) is the set of all two point subsets of the index set: \(J_2 = \{\{1,2\}, \{1,3\}, \{2,3\}\}\)
The set \(J_3\) is the set of all three point subsets of the index set: \(J_3 = \{\{1,2,3\}\}\)

Since there are 3 sets, \(n = 3.\) The left hand side of the inclusion-exclusion formula is \begin{align} \left|\bigcup_{i = 1}^3 A_i\right| & = \left|A_1 \cup A_2 \cup A_3\right| \\ & = \left|\{1,2,3,4\} \cup \{2,4,5,6\} \cup \{4,5,7\}\right| \\ & = \left|\{1,2,3,4,5,6,7\}\right| \\ & = 7 \end{align} The left hand side is \begin{align} \sum_{i=1}^3 \left[(-1)^{i-1}\sum_{J \in J_i}\left|\bigcap_{j \in J}A_j\right|\right] & = \left[(-1)^{1-1}\sum_{J \in J_1}\left|\bigcap_{j \in J}A_j\right|\right] + \left[(-1)^{2-1}\sum_{J \in J_2}\left|\bigcap_{j \in J}A_j\right|\right] + \left[(-1)^{3-1}\sum_{J \in J_3}\left|\bigcap_{j \in J}A_j\right|\right] \\ & = \left[\sum_{J \in J_1}\left|\bigcap_{j \in J}A_j\right|\right] - \left[\sum_{J \in J_2}\left|\bigcap_{j \in J}A_j\right|\right] + \left[\sum_{J \in J_3}\left|\bigcap_{j \in J}A_j\right|\right] \end{align} We will compute each summand. For \(J_1:\) \begin{align} \sum_{J \in J_1}\left|\bigcap_{j \in J}A_j\right| & = \left|\bigcap_{j \in \{1\}}A_j\right| + \left|\bigcap_{j \in \{2\}}A_j\right| + \left|\bigcap_{j \in \{3\}}A_j\right| \\ & = |A_1| + |A_2| + |A_3| \\ & = |\{1,2,3,4\}| + |\{2,4,5,6\}| + |\{4,5,7\}| \\ & = 4 + 4 + 3 \\ & = 11 \end{align} Next, for \(J_2:\) \begin{align} \sum_{J \in J_2}\left|\bigcap_{j \in J}A_j\right| & = \left|\bigcap_{j \in \{1,2\}}A_j\right| + \left|\bigcap_{j \in \{1,3\}}A_j\right| + \left|\bigcap_{j \in \{2,3\}}A_j\right| \\ & = |A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3| \\ & = |\{1,2,3,4\} \cap \{2,4,5,6\}| + |\{1,2,3,4\} \cap \{4,5,7\}| + |\{2,4,5,6\} \cap \{4,5,7\}| \\ & = |\{2,4\}| + |\{4\}| + |\{4,5\}| \\ & = 2 + 1 + 2 \\ & = 5 \end{align} For \(J_3:\) \begin{align} \sum_{J \in J_2}\left|\bigcap_{j \in J}A_j\right| & = \left|\bigcap_{j \in \{1,2,3\}}A_j\right| \\ & = |A_1 \cap A_2 \cap A_3| \\ & = |\{1,2,3,4\} \cap \{2,4,5,6\} \cap \{4,5,7\}| \\ & = |\{4\}| \\ & = 1 \\ \end{align} Finally, we can plug in the values. \begin{align} \left[\sum_{J \in J_1}\left|\bigcap_{j \in J}A_j\right|\right] - \left[\sum_{J \in J_2}\left|\bigcap_{j \in J}A_j\right|\right] + \left[\sum_{J \in J_3}\left|\bigcap_{j \in J}A_j\right|\right] & = 11 - 5 + 1 \\ & = 7 \end{align} Therefore, the left hand side equals the right hand side.



Example in practice:
Suppose we know the following about sets \(A_1, A_2,\) and \(A_3:\)

We can figure out how many elements are in the sets \(A_1, A_2\) and \(A_3\) altogether. First, add the elements in all the sets. Then, subtract the elements in any pair of sets. Last, add the elements in all 3 sets. \begin{align} |A_1 \cup A_2 \cup A_3| & = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3| \\ & = 5 + 7 + 10 - 4 - 3 - 5 + 2 \\ & = 22 - 12 + 2 \\ & = 12 \end{align} So there are 12 distince elements in the sets \(A_1, A_2,\) and \(A_3.\)

Informal explanation for \(2\) sets

This diagram shows the sets \(A\) and \(B.\)

A B
First, we count the elements in \(A.\) We number each region the number of times it has been counted.

\(|A|:\)
A B 1 1
Next, count the elements in \(B.\) The elements in both \(A\) and \(B\) will have been counted twice.

\(|A|+|B|:\)
A B 1 2 1
Finally, subtract the elements in the middle once. This will decrease the count of the elements in the middle by \(1.\) Also, it will make each region counted once, which is a count of all the elements in \(A \cup B.\)

\(|A|+|B| - |A \cap B| = |A \cup B|:\)
A B 1 1 1

The set \(A\) has \(4\) numbers. The set \(B\) has \(3\) numbers. The sets \(A\) and \(B\) have \(2\) numbers in common. How many elements are in \(A \cup B?\)

 

The set \(A\) has \(5\) numbers. The set \(B\) has \(4\) numbers. The set \(A \cup B\) has \(7\) numbers. How many numbers do \(A\) and \(B\) have in common?

 

The set \(A\) has \(11\) numbers. The set \(B\) has \(8\) numbers. The set \(C\) has \(9\) numbers. The sets \(A\) and \(B\) have \(4\) numbers in common. The sets \(A\) and \(C\) have \(5\) numbers in common. The sets \(B\) and \(C\) have \(4\) numbers in common. The sets \(A,\) \(B\) and \(C\) all have \(2\) numbers in common. How many numbers are in \(A \cup B \cup C.\)