We start this chapter with an elementary example.

##### Example7.1

Let $X$ be the set of $63$ students in an applied combinatorics course at a large technological university. Suppose there are $47$ computer science majors and $51$ male students. Also, we know there are $45$ male students majoring in computer science. How many students in the class are female students not majoring in computer science?

Solution
##### Example7.3

Another type of problem where we can readily see how such a technique is applicable is a generalization of the problem of enumerating integer solutions of equations. In Chapter 2, we discussed how to count the number of solutions to an equation such as \begin{equation*} x_1 + x_2 + x_3 + x_4 = 100, \end{equation*} where $x_1>0\text{,}$ $x_2, x_3 \geq 0$ and $2\leq x_4\leq 10\text{.}$ However, we steered clear of the situation where we add the further restriction that $x_3\leq 7\text{.}$ The previous example suggests a way of approaching this modified problem.

First, let's set up the problem so that the lower bound on each variable is of the form $x_i\geq 0\text{.}$ This leads us to the revised problem of enumerating the integer solutions to \begin{equation*} x_1' + x_2 + x_3 + x_4' = 97 \end{equation*} with $x_1',x_2,x_3,x_4'\geq 0\text{,}$ $x_3\leq 7\text{,}$ and $x_4'\leq 8\text{.}$ (We'll then have $x_1 = x_1'+1$ and $x_4 = x_4' + 2$ to get our desired solution.) To count the number of integer solutions to this equation with $x_3\leq 7$ and $x_4'\leq 8\text{,}$ we must exclude any solution in which $x_3 \gt 7$ or $x_4' \gt 8\text{.}$ There are $C(92,3)$ solutions with $x_3 \gt 7\text{,}$ and the number of solutions in which $x_4'\gt 8$ is $C(91,3)\text{.}$ At this point, it might be tempting to just subtract $C(92,3)$ and $C(91,3)$ from $C(100,3)\text{,}$ the total number of solutions with all variables nonnegative. However, care is required. If we did that, we would eliminate the solutions with both $x_3\gt 7$ and $x_4'\gt 8$ twice. To account for this, we notice that there are $C(83,3)$ solutions with both $x_3\gt 7$ and $x_4'\gt 8\text{.}$ If we add this number back in after subtracting, we've ensured that the solutions with both $x_3\gt 7$ and $x_4'\gt 8$ are not included in the total count and are not excluded more than once. Thus, the total number of solutions is \begin{equation*} \binom{100}{3} - \binom{92}{3} - \binom{91}{3} + \binom{83}{3} = 6516. \end{equation*}

From these examples, you should start to see a pattern emerging that leads to a more general setting. In full generality, we will consider a set $X$ and a family $\mathcal{P}=\{P_1,P_2,\dots,P_m\}$ of properties. We intend that for every $x\in X$ and each $i=1,2,\dots,m\text{,}$ either $x$ satisfies $P_i$ or it does not. There is no ambiguity. Ultimately, we are interested in determining the number of elements of $X$ which satisfy none of the properties in $\mathcal{P}\text{.}$ In Example 7.1, we could have made property $P_1$ “is a computer science major” and property $P_2$ “is male”. Then the number of students satisfying neither $P_1$ nor $P_2$ would be the number of female students majoring in something other than computer science, exactly the number we were asked to determine. What would the properties $P_1$ and $P_2$ be for Example 7.3?

Let's consider three examples of larger sets of properties. These properties will come back up during the remainder of the chapter as we apply inclusion-exclusion to some more involved situations. Recall that throughout this book, we use the notation $[n]$ for the set $\{1,2,\dots,n\}$ when $n$ is a positive integer.

##### Example7.4

Let $m$ and $n$ be fixed positive integers and let $X$ consist of all functions from $[n]$ to $[m]\text{.}$ Then for each $i=1,2,\dots,m\text{,}$ and each function $f\in X\text{,}$ we say that $f$ satisfies $P_i$ if there is no $j$ so that $f(j)=i\text{.}$ In other words, $i$ is not in the image or output of the function $f\text{.}$

As a specific example, suppose that $n=5$ and $m=3\text{.}$ Then the function given by the table below satisfies $P_1$ but not $P_2$ or $P_3\text{.}$

##### Example7.5

Let $m$ be a fixed positive integer and let $X$ consist of all bijections from $[m]$ to $[m]\text{.}$ Elements of $X$ are called permutations. Then for each $i=1,2,\dots,m\text{,}$ and each permutation $\sigma\in X\text{,}$ we say that $\sigma$ satisfies $P_i$ if $\sigma(i)=i\text{.}$

For example, the permutation $\sigma$ of $$ given in by the table below satisfies $P_3$ and $P_5$ and no other $P_i\text{.}$

Note that in the previous example, we could have said that $\sigma$ satisfies property $P_i$ if $\sigma(i)\neq i\text{.}$ But remembering that our goal is to count the number of elements satisfying none of the properties, we would then be counting the number of permutations satisfying $\sigma(i)=i$ for each $i=1,2,\dots,n\text{,}$ and perhaps we don't need a lot of theory to accomplish this task—the number is one, of course.

##### Example7.6

Let $m$ and $n$ be fixed positive integers and let $X=[n]\text{.}$ Then for each $i=1,2,\dots,m\text{,}$ and each $j\in X\text{,}$ we say that $j$ satisfies $P_i$ if $i$ is a divisor of $j\text{.}$ Put another way, the positive integers that satisfy property $P_i$ are precisely those that are multiples of $i\text{.}$

At first this may appear to be the most complicated of the sets of properties we've discussed thus far. However, being concrete should help clear up any confusion. Suppose that $n=m=15\text{.}$ Which properties does $12$ satisfy? The divisors of $12$ are $1\text{,}$ $2\text{,}$ $3\text{,}$ $4\text{,}$ $6\text{,}$ and $12\text{,}$ so $12$ satisfies $P_1\text{,}$ $P_2\text{,}$ $P_3\text{,}$ $P_4\text{,}$ $P_6\text{,}$ and $P_{12}\text{.}$ On the other end of the spectrum, notice that $7$ satisfies only properties $P_1$ and $P_7\text{,}$ since those are its only divisors.