7.1: Introduction

Example 7.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

Although the Venn diagrams that you've probably seen drawn many times over the years aren't always the best illustrations (especially if you try to think with some sort of scale), let's use one to get started. In Figure 7.2, we see how the groups in the scenario might overlap.

Screen Shot 2022-03-04 at 2.34.12 PM.png — Figure **7.2.** A Venn diagram for an applied combinatorics class

Now we can see that we're after the number of students in the white rectangle but outside the two shaded ovals, which is the female students not majoring in computer science. To compute this, we can start by subtracting the number of male students (the blue region) from the total number of students in the class and then subtracting the number of computer science majors (the yellow region). However, we've now subtracted the overlapping region (the male computer science majors) twice, so we must add that number back. Thus, the number of female students in the class who are not majoring in computer science is

$63-51-47+45=10$

Example 7.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

$x_1 + x_2 + x_3 + x_4 = 100$,

where $x_1>0, x_2,x_3 \geq 0$ and $2 \leq x_4 \leq 10$. However, we steered clear of the situation where we add the further restriction that $x_3 \leq 7$. 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$. This leads us to the revised problem of enumerating the integer solutions to

$x_1' + x_2 + x_3 + x_4' = 97$

with $x_1′,x_2,x_3,x_4′ \geq 0, x_3 \leq 7$, and $x_4′ \leq 8$. (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$, we must exclude any solution in which $x_3>7$ or $x_4′>8$. There are $C(92,3)$ solutions with $x_3>7$, and the number of solutions in which $x_4′>8$ is $C(91,3)$. At this point, it might be tempting to just subtract $C(92,3)$ and $C(91,3)$ from $C(100,3)$, 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>7$ and $x_4′>8$ twice. To account for this, we notice that there are $C(83,3)$ solutions with both $x_3>7$ and $x_4′>8$. If we add this number back in after subtracting, we've ensured that the solutions with both $x_3>7$ and $x_4′>8$ are not included in the total count and are not excluded more than once. Thus, the total number of solutions is

$\dbinom{100}{3} - \dbinom{92}{3} - \dbinom{91}{3} + \dbinom{83}{3} = 6516$.

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,…,P_m\}$ of properties. We intend that for every $x \in X$ and each $i=1,2,…,m$, 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}$. 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,…,n\}$ when $n$ is a positive integer.

Example 7.4

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

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

$Screen Shot 2022-03-04 at 2.47.42 PM.png$

Example 7.5

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

For example, the permutation $\sigma$ of $[5]$ given in by the table below satisfies $P_3$ and $P_5$ and no other $P_i$.

$Screen Shot 2022-03-04 at 2.52.26 PM.png$

Note that in the previous example, we could have said that $\sigma$ satisfies property $P_i$ if $\sigma(i) \neq i$. 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,…,n$, and perhaps we don't need a lot of theory to accomplish this task—the number is one, of course.

Example 7.6

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

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$. Which properties does 12 satisfy? The divisors of 12 are 1, 2, 3, 4, 6, and 12, so 12 satisfies $P_1, P_2, P_3, P_4, P_6$, and $P_{12}$. On the other end of the spectrum, notice that 7 satisfies only properties $P_1$ and $P_7$, since those are its only divisors.