19.1. The Inclusion-Exclusion Principle

The inclusion-exclusion principle allows us to solve the following type of counting problem: Let \(O\) be a set of objects and let \(\mathcal{P}\) be a set of properties. We would like to know either how many of the objects in \(O\) have none of the properties in \(\mathcal{P}\) or how many objects in \(O\) have all of the properties in \(\mathcal{P}\). These numbers may be difficult to determine directly. Inclusion-exclusion allows us to calculate these numbers by counting the numbers of objects that satisfy substantially weaker conditions. Let us focus on counting the number of objects that have none of the properties in \(\mathcal{P}\) for now.

Consider any subset \(\mathcal{Q} \subseteq \mathcal{P}\) and let \(O_\mathcal{Q}\) be the set of objects in \(O\) that have at least the properties in \(\mathcal{Q}\). Note that counting the objects that have the properties in \(\mathcal{Q}\) and possibly some other properties in \(\mathcal{P} \setminus \mathcal{Q}\) is generally much easier than counting the number of objects that have exactly the properties in \(\mathcal{Q}\) and no others. This is where the inclusion-exclusion technique draws its power from:

Lemma 19.1: For any set of objects \(O\) and a set \(\mathcal{P}\) of properties, let \(n_0\) be the number of objects in \(O\) that have none of the properties in \(\mathcal{P}\). For any subset \(\mathcal{Q} \subseteq \mathcal{P}\), let \(n_\mathcal{Q}\) be the number of objects in \(O\) that have at least the properties in \(\mathcal{Q}\) (but may have additional properties in \(\mathcal{P} \setminus \mathcal{Q}\)). Then

\[n_0 = \sum_{\mathcal{Q} \subseteq \mathcal{P}} (-1)^{|\mathcal{Q}|}n_\mathcal{Q}.\]

Proof: We can rewrite the sum as

\[\begin{aligned} \sum_{\mathcal{Q} \subseteq \mathcal{P}} (-1)^{|\mathcal{Q}|}n_\mathcal{Q} &= \sum_{\mathcal{Q} \subseteq \mathcal{P}}(-1)^{|\mathcal{Q}|}\sum_{o \in O} \chi_\mathcal{Q}(o)\\ &= \sum_{o \in O} \sum_{\mathcal{Q} \subseteq \mathcal{P}}(-1)^{|\mathcal{Q}|} \chi_\mathcal{Q}(o)\\ &= \sum_{o \in O_0} \sum_{\mathcal{Q} \subseteq \mathcal{P}}(-1)^{|\mathcal{Q}|} \chi_\mathcal{Q}(o) + \sum_{o \in O_1} \sum_{\mathcal{Q} \subseteq \mathcal{P}}(-1)^{|\mathcal{Q}|} \chi_\mathcal{Q}(o), \end{aligned}\]

where \(\chi_\mathcal{Q}(o) = 1\) if \(o\) has all the properties in \(\mathcal{Q}\) (and possibly others), and \(\chi_\mathcal{Q}(o) = 0\) otherwise. \(O_0\) is the set of elements in \(O\) that have none of the properties in \(\mathcal{P}\) and \(O_1\) is the set of elements in \(O\) that have at least one property in \(\mathcal{P}\).

We prove that

\[\sum_{\mathcal{Q} \subseteq \mathcal{P}} (-1)^{|\mathcal{Q}|}\chi_\mathcal{Q}(o) = \begin{cases} 1 & \text{if } o \in O_0\\ 0 & \text{if } o \in O_1. \end{cases}\]

Thus,

\[\begin{aligned} \sum_{\mathcal{Q} \subseteq \mathcal{P}} (-1)^{|\mathcal{Q}|}n_\mathcal{Q} &= \sum_{o \in O_0} \sum_{\mathcal{Q} \subseteq \mathcal{P}}(-1)^{|\mathcal{Q}|} \chi_\mathcal{Q}(o) + \sum_{o \in O_1} \sum_{\mathcal{Q} \subseteq \mathcal{P}}(-1)^{|\mathcal{Q}|} \chi_\mathcal{Q}(o)\\ &= \sum_{o \in O_0} 1 + \sum_{o \in O_1} 0\\ &= |O_0|\\ &= n_0. \end{aligned}\]

Consider an element \(o \in O_0\). Then \(\chi_\emptyset(o) = 1\) and \(\chi_\mathcal{Q}(o) = 0\) for all \(\mathcal{Q} \ne \emptyset\). Thus,

\[\sum_{\mathcal{Q} \subseteq \mathcal{P}}(-1)^{|\mathcal{Q}|} \chi_\mathcal{Q}(o) = (-1)^{|\emptyset|} = 1.\]

For an element \(o \in O_1\), let \(\mathcal{Q}'\) be the set of properties that \(o\) has. Then \(\chi_\mathcal{Q}(o) = 1\) if \(\mathcal{Q} \subseteq \mathcal{Q}'\), and \(\chi_\mathcal{Q}(o) = 0\) otherwise. Thus,

\[\begin{aligned} \sum_{\mathcal{Q} \subseteq \mathcal{P}}(-1)^{|\mathcal{Q}|} \chi_\mathcal{Q}(o) &= \sum_{\mathcal{Q} \subseteq \mathcal{Q}'}(-1)^{|\mathcal{Q}|}\\ &= \sum_{j=0}^{|\mathcal{Q}'|}\sum_{\substack{\mathcal{Q} \subseteq \mathcal{Q}'\\|\mathcal{Q}| = j}}(-1)^{j}\\ &= \sum_{j=0}^{|\mathcal{Q}'|}\binom{|\mathcal{Q}'|}{j}(-1)^{j}\\ &= \sum_{j=0}^{|\mathcal{Q}'|}\binom{|\mathcal{Q}'|}{j}(-1)^{j}1^{|\mathcal{Q}'|-j}\\ &= (1 - 1)^{|\mathcal{Q}'|}\\ &= 0.\quad \text{▨} \end{aligned}\]

The following corollary of Lemma 19.1 is often more useful in algorithmic applications of the inclusion-exclusion principle:

Corollary 19.2: For any set of objects \(O\) and a set \(\mathcal{P}\) of properties, let \(n_A\) be the number of objects in \(O\) that have all of the properties in \(\mathcal{P}\). For any subset \(\mathcal{Q} \subseteq \mathcal{P}\), let \(m_\mathcal{Q}\) be the number of objects in \(O\) that have none of the properties in \(\mathcal{Q}\) (but may have some of the properties in \(\mathcal{P} \setminus \mathcal{Q}\)). Then

\[n_A = \sum_{\mathcal{Q} \subseteq \mathcal{P}} (-1)^{|\mathcal{Q}|}m_\mathcal{Q}.\]

Proof: Define a new set of properties \(\bar{\mathcal{P}} = \bigl\{\bar P \mid P \in \mathcal{P}\bigr\}\) such that an object has property \(\bar P\) if and only if it does not have property \(P\). For any subset \(\mathcal{Q} \subseteq \mathcal{P}\), the objects that have none of the properties in \(\mathcal{Q}\) are exactly the objects that have at least the properties in \(\bar{\mathcal{Q}} = \bigl\{\bar P \mid P \in \mathcal{Q}\bigr\}\). Thus, \(m_{\mathcal{Q}} = n_{\bar{\mathcal{Q}}}\) for all \(\mathcal{Q} \subseteq \mathcal{P}\). Moreover, the objects having all properties in \(\mathcal{P}\) are the objects having none of the properties in \(\bar{\mathcal{P}}\). Thus, by Lemma 19.1,

\[n_A = \sum_{\bar{\mathcal{Q}} \subseteq \bar{\mathcal{P}}} (-1)^{|\bar{\mathcal{Q}}|}n_{\bar{\mathcal{Q}}} = \sum_{\mathcal{Q} \subseteq \mathcal{P}} (-1)^{|\mathcal{Q}|}m_{\mathcal{Q}}.\quad \text{▨}\]