## Inclusion Exclusion Principle theorem and examples

Reference: Combinatorial Techniques by Sharad Sane, Hindustan Book Agency.

Theorem:

The inclusion-exclusion principle: Let X be a finite set and let and let $P_{i}: i = 1, 2, \ldots n$  be a set of n properties satisfied by (s0me of) the elements of X. Let $A_{i}$ denote the set of those elements of X that satisfy the property $P_{i}$ . Then, the size of the set $\overline{A_{1}} \bigcup \overline{A_{2}} \bigcup \ldots \bigcup \overline{A_{n}}$ of all those elements that do not satisfy any one of these properties is given by

$\overline{A_{1}} \bigcup \overline{A_{2}} \bigcup \ldots \bigcup \overline{A_{n}} = |X| - \sum_{i=1}^{n}|A_{n}|+ \sum_{1 \leq i .

Proof:

The proof will show  that every object in the set X is counted the same number of times on both the sides. Suppose $x \in X$ and assume that x is an element of the set on the left hand side of above equation. Then, x has none of the properties $P_{i}$. We need to show that in this case, x is counted only once on the right hand side. This is obvious since x is not in any of the $A_{i}$ and $x \in X$. Thus, X is counted only once in the first summand and is not counted in any other summand since $x \notin A_{i}$ for all i. Now let x have k properties say $P_{i_{1}}$, $P_{i_{2}}$, $\ldots$, $P_{i_{k}}$ (and no  others). Then x is counted once in X. In the next sum, x occurs ${k \choose 2}$ times and so on. Thus, on the right hand side, x is counted precisely,

${k \choose 0}-{k \choose 1}+{k \choose 2}+ \ldots + (-1)^{k}{k \choose k}$

times. Using the binomial theorem, this sum is $(1-1)^{k}$ which is 0 and hence, x is not counted on the right hand side. This completes the proof. QED.

More later,

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.