Inclusion-and-exclusion principle

A method for calculating the number $N( a _ {1} ^ \prime {} \dots a _ {r} ^ \prime )$ of objects which do not have any of the given properties $a _ {1} \dots a _ {r}$, according to the following formula:

$$\tag{1 } N ( a _ {1} ^ \prime \dots a _ {r} ^ \prime ) = \ N - \sum _ {i = 1 } ^ { r } N ( a _ {i} ) +$$

$$+ \sum _ \begin {array}{c} {i, j = 1 } \\ {i < j } \end{array} ^ { r } N ( a _ {i} a _ {j} ) - \dots + (- 1) ^ {r} N ( a _ {1} \dots a _ {r} ),$$

where $a _ {i} ^ \prime$ denotes the absence of property $a _ {i}$, $N$ is the total number of objects, $N( a _ {i} )$ is the number of objects having property $a _ {i}$, $N( a _ {i} a _ {j} )$ is the number of objects having both properties $a _ {i}$ and $a _ {j}$, etc. (see [3]). The inclusion-and-exclusion principle yields a formula for calculating the number of objects having exactly $m$ properties out of $a _ {1} \dots a _ {r}$, $m = 0 \dots r$:

$$\tag{2 } e _ {m} = \ \sum _ {i = 0 } ^ { {r } - m } (- 1) ^ {i} \left ( \begin{array}{c} m + i \\ i \end{array} \right ) s _ {m+} i ,$$

where $s _ {0} = N$, $s _ {k} = \sum N ( a _ {i _ {1} } {} \dots a _ {i _ {k} } )$, and the summation is performed over all $k$- tuples $( i _ {1} \dots i _ {k} )$ such that $i _ {1} \neq \dots \neq i _ {k}$, $k = 1 \dots r$, i.e.

$$s _ {1} = \sum _ { i } N ( a _ {i} ),\ s _ {2} = \sum _ \begin {array}{c} {i, j } \\ {i \neq j } \end{array} N ( a _ {i} a _ {j} ) \dots s _ {r} = N ( a _ {1} \dots a _ {r} ).$$

The method for calculating $e _ {m}$ according to (2) is also referred to as the inclusion-and-exclusion principle. This principle is used in solving combinatorial and number-theoretic problems [1]. For instance, given a natural number $a$ and natural numbers $a _ {1} \dots a _ {N}$ such that $( a _ {i} , a _ {j} ) = 1$ if $i \neq j$, the number of natural numbers $k$, $0 < k \leq n$, that are not divisible by $a _ {i}$, $i = 1 \dots N$, is, according to (1):

$$n - \sum _ {1 \leq i \leq N } \left [ { \frac{n}{a} _ {i} } \right ] + \sum _ {1 \leq i \leq j \leq N } \left [ { \frac{n}{a _ {i} a _ {j} } } \right ] - \dots$$

$$\dots + (- 1) ^ {N} \left [ { \frac{n}{a _ {1} \dots a _ {N} } } \right ] .$$

The inclusion-and-exclusion principle also serves to solve problems of inversion [2], [3].

References

[1]	M. Hall jr., "Combinatorial theory" , Wiley (1986)
[2]	H.J. Ryser, "Combinatorial mathematics" , Wiley & Math. Assoc. Amer. (1963)
[3]	J. Riordan, "An introduction to combinational analysis" , Wiley (1958)