The Inclusion-Exclusion Principle again !! RMO basics

Some refresher of motivation(s) and simple applications of the inclusion-exclusion principle. Remember that: (1) We owe a lot to the Indians who taught us how to count. — Albert Einstein. (2) Everything that can be counted is countable, but everything that is countable does not count. — Albert Einstein.

We will derive and apply an important counting formula called the inclusion-exclusion principle. Recall that the addition principle gives a simple formula for counting the number of objects in a union of sets, provided that the sets do not overlap (that is, provided that the sets determine a partition). The inclusion-exclusion principle gives a formula for the most general of circumstances in which the sets are free to overlap without restriction. The formula is necessarily complicated, but, as a result is more widely applicable.

1. The Inclusion-Exclusion Principle:

We know of several examples in which it is easier to make an indirect count of the number of objects in a set rather than to count the objects directly. Below are two more examples:

Example:

Count the permutations $\{ i_{1}i_{2}\ldots i_{n}\}$ of $\{ 1,2, \ldots ,n\}$ in which 1 is not in the first position (that is, $i_{1} \neq 1$ ).

We could make a direct count by observing that the permutations with 1 not in the first position can be divided into $(n-1)$ parts according to which of the $(n-1)$ integers k from $\{ 2,3,\ldots, n\}$ is in the first position. A permutation with k in the first position consists of k followed by a permutation of the $(n-1)-$ element set $\{ 1, \ldots, k-1, k+1, \ldots, n\}$ . Hence, there are $(n-1)!$ permutations of $\{ 1,2,3 \ldots, n\}$ with k in the first position. By the addition principle, there are $(n-1)!(n-1)$ permutations of $\{ 1,2, \ldots, n\}$ with 1 not in the first position.

Alternatively, we could make an indirect count by observing that the number of permutations of $\{1, 2, \ldots, n \}$ with 1 in the first position is the same set as the number $(n-1)!$ of permutations of $\{ 2,3,\ldots,n\}$ . Since the total number of permutations of $\{ 1,2,\ldots, n\}$ is n!, the number of permutations of $\{ 1,2,\ldots,n\}$ in which 1 is not in the first position is $n!-(n-1)!=(n-1)!(n-1)$ .

Example:

Count the number of integers between 1 and 600, inclusive, which are not divisible by 6.

We can do this indirectly as follows: The number of integers between 1 and 600 which are divisible by 6 is 600/6 which is equal to 100 since every sixth integer is divisible by 6. Hence, $600-100=500$ of the integers between 1 and 600 are not divisible by 6.

Some further notes:

The rule used to obtain an indirect count in these examples is the following: If A is a subset of a set S, then the number of objects in A equals the number of objects in S minus the number not in A. Recall that

$A^{'}=S-A= \{ x: x \in S, x \notin A\}$

is the complement of A in S: that is, the set consisting of those objects in S which are not in A. The rule can then be written as

$|A| = |S| - |A^{'}|$ , or equivalently, $|A^{'}|=|S|-|A|$ . This formula is the simplest instance of the inclusion-exclusion principle.

We shall formulate the inclusion-exclusion principle in a manner in which it is convenient to apply. As a first generalization of the preceding rule, let S be a finite set of objects, and let $P_{1}$ and $P_{2}$ be two “properties” that each object in S may or may not possess. We wish to count the number of objects in S that have neither property $P_{1}$ nor property $P_{2}$ . We can do this by first including all objects of S in our count, then excluding all objects that have property $P_{1}$ and excluding all objects which have property $P_{2}$ , and then, noting that we have excluded objects having both properties $P_{1}$ and $P_{2}$ twice, readmitting all such objects once. We can write this symbolically as follows: Let $A_{1}$ be the subset of objects of S that have property $P_{1}$ , and let $A_{2}$ be the subset of objects of S that have property $P_{2}$ . Then, $A_{1}^{'}$ consists of those objects of S not having property $P_{1}$ and let $A_{2}^{'}$ consists of those objects of S not having property $P_{2}$ . The objects of the set $A_{1}^{'}\bigcap A_{2}^{'}$ are those having neither property $P_{1}$ nor property $P_{2}$ . We then have $|A_{1}^{'} \bigcap A_{2}^{'}|=|S|-|A_{1}|-|A_{2}|+|A_{1}\bigcap A_{2}|$ .

Since the left side of the preceding equation counts the number of objects of S that have neither property $P_{1}$ nor property $P_{2}$ , we can establish the validity of this equation by showing that an object with neither of the two properties $P_{1}$ and $P_{2}$ makes a net contribution of 1 to the right side, and every other object makes a net contribution of zero. If x is an object with neither of the properties $P_{1}$ and $P_{2}$ , it counted among the objects of S, not counted among the objects of $A_{1}$ or of $A_{2}$ , and not counted among the objects of $A_{1}\bigcap A_{2}$ . Hence, its net contribution to the right side of the equation is $1-0-0+0=1$ .

If x has only the property $P_{1}$ , it contributes $1-1-0+0=0$ to the right side, while it has only the property $P_{2}$ , it contributes $1-0-1+0=0$ to the right side. Finally, if x has both properties $P_{1}$ and $P_{2}$ , it contributes $1-1-1+1=0$ to the right side of the equation. Thus, the right side of the equation also counts the number of objects of S with neither property $P_{1}$ nor property $P_{2}$ .

More generally, let $P_{1}$ , $P_{2}$ , $P_{3}$ , $\ldots$ , $P_{m}$ be m properties referring to the objects in S, and let

$A_{i}=\{ x: x \in S, \hspace{0.1 in} x \hspace{0.1 in} has \hspace{0.1 in} property \hspace{0.1 in} P_{i}\}$ , and $\{ i= 1,2,\ldots,m\}$

be the subset of objects of S that have property S (and possibly other properties). Then, $A_{i}\bigcap A_{j}$ is the subset of objects that have both properties $P_{1}$ and $P_{2}$ (and, possibly others), $A_{i}\bigcap A_{j}\bigcap A_{k}$ is the subset of objects which have properties $P_{i}$ , $P_{j}$ , $P_{k}$ and so on. The subset of objects having none of the properties is $A_{1}^{'}\bigcap A_{2}^{'} \bigcap \ldots \bigcap A_{m}^{'}$ . The inclusion exclusion principle shows how to count the number of objects in this set by counting objects according to the properties they do have. Thus, in this sense, it “inverts” the counting process.

Theorem 1.1:

The number of objects of S that have none of the properties $P_{1}$ , $P_{2}$ , $\ldots$ , $P_{m}$ is given by:

$|A_{1}^{'}\bigcap A_{2}^{'} \bigcap A_{3}^{'}\bigcap \ldots A_{m}^{'}| = |S|-\sum|A_{i}|+\sum|A_{i}\bigcap A_{j}|-\sum|A_{i} \bigcap A_{j} \bigcap A_{k}|+ \ldots + (-1)^{m}|A_{1}\bigcap A_{2}\bigcap A_{3}\ldots \bigcap A_{m}|$ ,

where the first sum is over all 1-combinations $\{ i\}$ of $\{ 1,2,3, \ldots, m \}$ , the second sum is over all 2-combinations $\{ i,j\}$ of $\{ 1,2,\ldots, m\}$ , the third sum is over all 3-combinations $\{i,j,k\}$ of $\{ 1,2,\ldots, m\}$ , and so on.