## Section7.2The 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]\text{,}$$ let $$N(S)$$ denote the number of elements of $$X$$ which satisfy property $$P_i$$ for all $$i\in S\text{.}$$ Note that if $$S=\emptyset\text{,}$$ then $$N(S)=|X|\text{,}$$ 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\text{,}$$ 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\text{,}$$ 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{equation*} N(\emptyset) - N(\{1\}) - N(\{2\}) + N(\{1,2\}). \end{equation*}

Suppose that we had three properties $$P_1,P_2\text{,}$$ and $$P_3\text{.}$$ How would we count the number of objects satisfying none of the properties? As before, we start by subtracting for each of $$P_1\text{,}$$ $$P_2\text{,}$$ and $$P_3\text{.}$$ Now we have removed the objects satisfying both $$P_1$$ and $$P_2$$ twice, so we must add back $$N(\{1,2\})\text{.}$$ similarly, we must do this for the objects satisfying both $$P_2$$ and $$P_3$$ and both $$P_1$$ and $$P_3\text{.}$$ Now let's think about the objects satisfying all three properties. They're counted in $$N(\emptyset)\text{,}$$ 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{equation*} N(\emptyset) - N(\{1\}) - N(\{2\}) - N(\{3\}) + N(\{1,2\}) + N(\{2,3\}) + N(\{1,3\}) - N(\{1,2,3\}). \end{equation*}

We can generalize this as the following theorem:

We proceed by induction on the number $$m$$ of properties. If $$m=1\text{,}$$ then the formula reduces to $$N(\emptyset)-N(\{1\})\text{.}$$ 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\text{.}$$

Now assume validity when $$m\le k$$ for some $$k\ge1$$ and consider the case where $$m=k+1\text{.}$$ 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 $$\mathcal{Q}=\{P_1,P_2,\dots,P_k\}\text{.}$$ Then for each subset $$S\subseteq [k]\text{,}$$ let $$N'(S)$$ count the number of elements of $$X'$$ satisfying property $$P_i$$ for all $$i\in S\text{.}$$ Also, let $$N''(S)$$ count the number of elements of $$X''$$ satisfying property $$P_i$$ for each $$i\in S\text{.}$$ Note that $$N(S)=N'(S)+N''(S)$$ for every $$S\subseteq [k]\text{.}$$

Let $$X'_0$$ denote the set of elements in $$X'$$ which satisfy none of the properties in $$\mathcal{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 $$\mathcal{Q}\text{,}$$ and therefore none of the properties in $$\mathcal{P}\text{.}$$

Now by the inductive hypothesis, we know

\begin{equation*} |X'_0| = \sum_{S\subseteq [k]} (-1)^{|S|}N'(S)\qquad \text{and} \qquad |X''_0| = \sum_{S\subseteq [k]} (-1)^{|S|}N''(S). \end{equation*}

It follows that

\begin{align*} |X''_0| \amp = \sum_{S\subseteq [k]} (-1)^{|S|}N''(S) = \sum_{S\subseteq [k]} (-1)^{|S|}\left(N(S)-N'(S)\right)\\ \amp = \sum_{S\subseteq [k]} (-1)^{|S|}N(S)+ \sum_{S\subseteq [k]} (-1)^{|S|+1}N(S\cup\{k+1\})\\ \amp = \sum_{S\subseteq [k+1]} (-1)^{|S|}N(S). \end{align*}