14.9: Inclusion-Exclusion

How big is a union of sets? For example, suppose there are 60 math majors, 200 EECS majors, and 40 physics majors. How many students are there in these three departments? Let \(M\) be the set of math majors, \(E\) be the set of EECS majors, and \(P\) be the set of physics majors. In these terms, we’re asking for \(|M \cup E \cup P|\).

The Sum Rule says that if \(M, E,\) and \(P\) are disjoint, then the sum of their sizes is

\(|M \cup E \cup P| = |M| + |E| + |P|.\)

However, the sets \(M, E,\) and \(P\) might not be disjoint. For example, there might be a student majoring in both math and physics. Such a student would be counted twice on the right side of this equation, once as an element of \(M\) and once as an element of \(P\). Worse, there might be a triple-major⁵ counted three times on the right side!

Our most-complicated counting rule determines the size of a union of sets that are not necessarily disjoint. Before we state the rule, let’s build some intuition by considering some easier special cases: unions of just two or three sets.

Union of Two Sets

For two sets, \(S_1\) and \(S_2\), the Inclusion-Exclusion Rule is that the size of their union is:

Intuitively, each element of \(S_1\) accounted for in the first term, and each element of \(S_2\) is accounted for in the second term. Elements in both \(S_1\) and \(S_2\) are counted twice—once in the first term and once in the second. This double-counting is corrected by the final term.

Union of Three Sets

So how many students are there in the math, EECS, and physics departments? In other words, what is \(|M \cup E \cup P|\) if:

\[\begin{aligned} |M| &= 60 \\ |E| &= 200 \\ |P| &= 40. \end{aligned}\]

The size of a union of three sets is given by a more complicated Inclusion-Exclusion formula:

\[\begin{aligned} |S_1 \cup S_2 \cup S_3| &= |S_1| + |S_2| + |S_3| \\ &- |S_1\cap S_2| - |S_1\cap S_3| - |S_2\cap S_3| \\ &+ |S_1 \cap S_2 \cap S_3| \end{aligned}\]

Remarkably, the expression on the right accounts for each element in the union of \(S_1, S_2,\) and \(S_3\) exactly once. For example, suppose that \(x\) is an element of all three sets. Then \(x\) is counted three times (by the \(|S_1|, |S_2|,\) and \(|S_3|\) terms), subtracted off three times (by the \(|S_1 \cap S_2|, |S_1 \cap S_3|,\) and \(|S_2 \cap S_3|\) terms), and then counted once more (by the \(|S_1 \cap S_2 \cap S_3|\) term). The net effect is that \(x\) is counted just once.

If \(x\) is in two sets (say, \(S_1\) and \(S_2\)), then \(x\) is counted twice (by the \(|S_1|\) and \(|S_2|\) terms) and subtracted once (by the \(|S_1 \cap S_2|\) term). In this case, \(x\) does not contribute to any of the other terms, since \(x \notin S_3\).

So we can’t answer the original question without knowing the sizes of the various intersections. Let’s suppose that there are:

\[\begin{aligned} 4 &\quad \text{math - EECS double majors} \\ 3 &\quad \text{math - physics double majors} \\ 11 &\quad \text{EECS - physics double majors} \\ 2 &\quad \text{triple majors} \end{aligned}\]

Then \(|M \cap E| = 4 + 2, |M \cap P| = 3 + 2, |E \cap P| = 11 + 2,\) and \(|M \cap E \cap P| = 2\). Plugging all this into the formula gives:

\[\begin{aligned} |M \cup E \cup P| &= |M| + |E| + |P| - |M\cap E| - |M\cap P| - |E\cap P| \\ &+ |M \cap E \cap P| \\ &= 60 + 200 + 40 - 6- 5- 13 + 2 \\ &= 278 \end{aligned}\]

Sequences with 42, 04, or 60

In how many permutations of the set \(\{0, 1, 2, \ldots, 9\}\) do either 4 and 2, 0 and 4, or 6 and 0 appear consecutively? For example, none of these pairs appears in:

\[\nonumber (7, 2, 9, 5, 4, 1, 3, 8, 0, 6).\]

The 06 at the end doesn’t count; we need 60. On the other hand, both 04 and 60 appear consecutively in this permutation:

\[\nonumber (7, 2, 5, \underline{6}, \underline{0}, \underline{4}, 3, 8, 1, 9).\]

Let \(P_{42}\) be the set of all permutations in which 42 appears. Define \(P_{60}\) and \(P_{04}\) similarly. Thus, for example, the permutation above is contained in both \(P_{60}\) and \(P_{04}\), but not \(P_{42}\). In these terms, we’re looking for the size of the set \(P_{42} \cup P_{04} \cup P_{60}\).

First, we must determine the sizes of the individual sets, such as \(P_{60}\). We can use a trick: group the 6 and 0 together as a single symbol. Then there is an immediate bijection between permutations of \(\{0, 1, 2, \ldots, 9\}\) containing 6 and 0 consecutively and permutations of:

\[\nonumber \{60,1,2,3,4,5,7,8,9\}.\]

For example, the following two sequences correspond:

\[\nonumber (7, 2, 5, \underline{6}, \underline{0}, 4, 3, 8, 1, 9) \longleftrightarrow (7, 2, 5, \underline{60}, 4, 3, 8, 1, 9)\]

There are \(9!\) permutations of the set containing 60, so \(|P_{60}| = 9!\) by the Bijection Rule. Similarly, \(|P_{04}| = |P_{42}| = 9!\) as well.

Next, we must determine the sizes of the two-way intersections, such as \(P_{42} \cap P_{60}\). Using the grouping trick again, there is a bijection with permutations of the set:

\[\nonumber \{42,60,1,3,5,7,8,9\}.\]

Thus, \(|P_{42} \cap P_{60}| = 8!\). Similarly, \(|P_{60} \cap P_{04}| = 8!\) by a bijection with the set:

\[\nonumber \{604,1,2,3,5,7,8,9\}.\]

And \(|P_{42} \cap P_{04}| = 8!\) as well by a similar argument. Finally, note that \(|P_{60} \cap P_{04} \cap P_{42}| = 7!\) by a bijection with the set:

\[\nonumber \{6042,1,3,5,7,8,9\}.\]

Plugging all this into the formula gives:

\(|P_{42} \cap P_{04} \cap P_{60}| = 9! + 9! + 9! - 8! - 8! - 8! + 7!.\)

Union of n Sets

The size of a union of \(n\) sets is given by the following rule.

Rule 14.9.1 (Inclusion-Exclusion).

\[\begin{aligned} &\quad |S_1 \cup S_2 \cup \cdots \cup S_n| = \\ &\textit{the sum of the sizes of the individual sets} \\ \text{minus} \quad &\textit{the sizes of all two-way intersections} \\ \text{plus} \quad &\textit{the sizes of all three-way intersections} \\ \text{minus} \quad &\textit{the sizes of all four-way intersections} \\ \text{plus} \quad &\textit{the sizes of all five-way intersections, etc.} \end{aligned}\]

The formulas for unions of two and three sets are special cases of this general rule.

This way of expressing Inclusion-Exclusion is easy to understand and nearly as precise as expressing it in mathematical symbols, but we’ll need the symbolic version below, so let’s work on deciphering it now.

We already have a concise notation for the sum of sizes of the individual sets, namely,

\[\nonumber \sum_{i = 1}^{n} |S_i|.\]

A “two-way intersection” is a set of the form \(S_i \cap S_j\) for \(i neq j\). We regard \(S_j \cap S_i\) as the same two-way intersection as \(S_i \cap S_j\), so we can assume that \(i < j\). Now we can express the sum of the sizes of the two-way intersections as

\[\nonumber \sum_{i \leq i < j \leq n} |S_i \cap S_j|.\]

Similarly, the sum of the sizes of the three-way intersections is

\[\nonumber \sum_{i \leq i < j < k \leq n} |S_i \cap S_j \cap S_k|.\]

These sums have alternating signs in the Inclusion-Exclusion formula, with the sum of the \(k\)-way intersections getting the sign \((-1)^{k-1}\). This finally leads to a symbolic version of the rule:

Rule (Inclusion-Exclusion).

\[\begin{aligned} \bigg| \bigcup_{i=1}^{n} S_i \bigg| &= \sum_{i = 1}^{n} |S_i| \\ &- \sum_{i \leq i < j \leq n} |S_i \cap S_j| \\ &+ \sum_{i \leq i < j < k \leq n} |S_i \cap S_j \cap S_k| + \cdots \\ &+ (-1)^{n-1} \bigg| \bigcap_{i=1}^{n} S_i \bigg|. \end{aligned}\]

While it’s often handy express the rule in this way as a sum of sums, it is not necessary to group the terms by how many sets are in the intersections. So another way to state the rule is:

Rule (Inclusion-Exclusion-II).

\[\bigg| \bigcup_{i=1}^{n} S_i \bigg| = \sum_{\emptyset \neq I \subseteq \{1,\ldots,n\}} (-1)^{|I| + 1} \bigg| \bigcap_{i \in I} S_i \bigg|\]

A proof of these rules using just highschool algebra is given in Problem 14.52.

Computing Euler’s Function

We can also use Inclusion-Exclusion to derive the explicit formula for Euler’s function claimed in Corollary 8.10.11: if the prime factorization of \(n\) is \(p_1^{e_1} \cdots p_m^{e_m}\) for distinct primes \(p_i\), then

\[\label{14.9.2} \phi(n) = n \prod_{i = 1}^{m} \left( 1 - \dfrac{1}{p_i}\right).\]

To begin, let \(S\) be the set of integers in \([0..n)\) that are not relatively prime to \(n\). So \(\phi (n) = n - |S|\). Next, let \(C_a\) be the set of integers in \([0..n)\) that are divisible by \(a\):

\[\nonumber C_a ::= \{k \in [0..n) \mid a | k\}.\]

So the integers in \(S\) are precisely the integers in \([0..n)\) that are divisible by at least one of the \(p_i\)’s. Namely,

\[S = \bigcup_{i = 1}^{m} C_{pi}.\]

We’ll be able to find the size of this union using Inclusion-Exclusion because the intersections of the \(C_{pi}\)’s are easy to count. For example, \(C_p \cap C_q \cap C_r\) is the set of integers in \([0..n)\) that are divisible by each of \(p, q\) and \(r\). But since the \(p, q, r\) are distinct primes, being divisible by each of them is the same as being divisible by their product. Now if \(k\) is a positive divisor of \(n\), then there are exactly \(n/k\) multiples of \(k\) in \([0..n)\). So exactly \(n /pqr\) of the integers in \([0..n)\) are divisible by all three primes \(p, q, r\). In other words,

\[\nonumber |C_p \cap C_q \cap C_r| = \dfrac{n}{pqr}.\]

This reasoning extends to arbitrary intersections of \(C_p\)’s, namely,

\[\bigg| \bigcap_{j \in I} C_{p_j}\bigg| = \dfrac{n}{\prod_{j \in I} p_j}.\]

for any nonempty set \(I \in [1..m]\). This lets us calculate:

\[\begin{aligned}
|S| &=\left|\bigcup_{i=1}^{m} C_{p_{i}}\right| & \text{(by 14.9.3)} \\
&=\sum_{\emptyset \neq I \subseteq[1 . . m]}(-1)^{|I|+1}\left|\bigcap_{i \in I} C_{p_{i}}\right| & \text{(by Inclusion-Exclusion (14.9.1))}\\
&=\sum_{\emptyset \neq I \subseteq[1 . . m]}(-1)^{|I|+1} \frac{n}{\prod_{j \in I} p_{j}} & \text{(by 14.9.4)}\\
&=-n \sum_{\emptyset \neq I \subseteq[1 . . m]} \frac{1}{\prod_{j \in I}\left(-p_{j}\right)} \\
&=-n\left(\prod_{i=1}^{m}\left(1-\frac{1}{p_{i}}\right)\right)+n,
\end{aligned}\]

so

\[\nonumber \phi(n) = n - |S| = n \prod_{i = 1}^{m} \left(1-\frac{1}{p_{i}}\right),\]

which proves (\ref{14.9.2}).

Yikes! That was pretty hairy. Are you getting tired of all that nasty algebra? If so, then good news is on the way. In the next section, we will show you how to prove some heavy-duty formulas without using any algebra at all. Just a few words and you are done. No kidding.

⁵ ...though not at MIT anymore.