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)