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,\dots,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 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 \[\begin{aligned}\end{aligned}\]

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: \[\begin{aligned}\end{aligned}\] We can generalize this as the following theorem:

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.