Introduction

We start this chapter with an elementary example.

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\), 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 , 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 ?

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.

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