## 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*}