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 <j \leq n}|A_{i} \bigcup A_{j}|- \ldots + \{ (-1)^{k} \sum_{1 \leq i_{1} < i_{2}< \ldots < i_{k} \leq n}|A_{i_{1} \bigcup A_{i_{2}}} \ldots \bigcup A_{i_{k}}|\}+ \ldots+ (-1)^{n}|A_{1} \bigcup A_{2} \ldots \bigcup A_{n}|$ .

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

Mathematics Hothouse