7.2: The Inclusion-Exclusion Formula

Now that we have an understanding of what we mean by a property, let's see how we can use this concept to generalize the process we used in the first two examples of the previous section.

Let \(X\) be a set and let \(\mathcal{P}=\{P_1,P_2,…,P_m\}\) be a family of properties. Then for each subset \(S \subseteq [m]\), let \(N(S)\) denote the number of elements of \(X\) which satisfy property \(P_i\) for all \(i \in S\). Note that if \(S= \emptyset\), then \(N(S)=|X|\), as every element of \(X\) satisfies every property in \(S\) (which contains no actual properties).

Returning for a moment to Example 7.1 with \(P_1\) being “is a computer science major” and \(P_2\) being “is male,” we note that ,\(N(\{1\})=47\), since there are 47 computer science majors in the class. Also, \(N(\{2\})=51\) since 51 of the students are male. Finally, \(N(\{1,2\})=45\) since there are 45 male computer science majors in the class.

In the examples of the previous section, we subtracted off \(N(S)\) for the sets \(S\) of size 1 and then added back \(N(S)\) for the set of properties of size 2, since we'd subtracted the number of things with both properties (male computer science majors or solutions with both \(x_3>7\) and \(x_4′>8\)) twice. Symbolically, we determined that the number of objects satisfying none of the properties was

\(N(\emptyset) - N(\{1\}) - N(\{2\}) + N(\{1,2\})\).

Suppose that we had three properties \(P_1,P_2\), and \(P_3\). How would we count the number of objects satisfying none of the properties? As before, we start by subtracting for each of \(P_1, P_2\), and \(P_3\). Now we have removed the objects satisfying both \(P_1\) and \(P_2\) twice, so we must add back \(N(\{1,2\})\). similarly, we must do this for the objects satisfying both \(P_2\) and \(P_3\) and both \(P_1\) and \(P_3\). Now let's think about the objects satisfying all three properties. They're counted in \(N(\emptyset)\), eliminated three times by the \(N(\{i\})\) terms, and added back three times by the \(N(\{i,j\})\) terms. Thus, they're still being counted! Thus, we must yet subtract \(N(\{1,2,3\})\) to get the desired number:

\(N(\emptyset) - N(\{1\}) - N(\{2\}) - N(\{3\}) + N(\{1,2\}) + N(\{2,3\}) + N(\{1,3\}) - N(\{1,2,3\})\).

We can generalize this as the following theorem:

Theorem 7.7. Principle of Inclusion-Exclusion.

The number of elements of \(X\) which satisfy none of the properties in \(\mathcal{P}\) is given by

\(\displaystyle \sum_{S \subseteq [m]} (-1)^{|S|}N(S)\).

Proof

We proceed by induction on the number \(m\) of properties. If \(m=1\), then the formula reduces to \(N(\emptyset)−N(\{1\})\). This is correct since it says just that the number of elements which do not satisfy property \(P_1\) is the total number of elements minus the number which do satisfy property \(P_1\).

Now assume validity when \(m \leq k\) for some \(k \geq 1\) and consider the case where \(m=k+1\). Let \(X′=\{x \in X:x\) satisfies \(P_{k+1}\}\) and \(X″=X−X′\) (i.e., \(X″\) is the set of elements that do not satisfy \(P_{k+1}\)). Also, let \(Q=\{P_1,P_2,…,P_k\}\). Then for each subset \(S \subseteq [k]\), let \(N′(S)\) count the number of elements of \(X′\) satisfying property \(P_i\) for all \(i \in S\). Also, let \(N″(S)\) count the number of elements of \(X″\) satisfying property \(P_i\) for each \(i \in S\). Note that \(N(S)=N′(S)+N″(S)\) for every \(S \subseteq [k]\).

Let \(X_0′\) denote the set of elements in \(X′\) which satisfy none of the properties in \(Q\) (in other words, those that satisfy only \(P_{k+1}\) from \(\mathcal{P}\)), and let \(X_0″\) denote the set of elements of \(X″\) which satisfy none of the properties in \(Q\), and therefore none of the properties in \(\mathcal{P}\).

Now by the inductive hypothesis, we know

\(|X_0'| = \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|}N'(S)\) and \(|X_0"| = \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|} N"(S)\).

It follows that

\(|X_0"| = \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|}N'(S) = \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|} (N(S) - N'(S))\)

\(= \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|}N(S) + \sum_{S \subseteq [k]} (-1) ^{|S|+1} N(S \cup \{k+1\})\)

\(= \displaystyle \sum_{S \subseteq [k+1]} (-1)^{|S|}N(S)\).