Reference: Combinatorial Techniques by Sharad Sane, Hindustan Book Agency.
Theorem:
The inclusion-exclusion principle: Let X be a finite set and let and let be a set of n properties satisfied by (s0me of) the elements of X. Let
denote the set of those elements of X that satisfy the property
. Then, the size of the set
of all those elements that do not satisfy any one of these properties is given by
.
Proof:
The proof will show that every object in the set X is counted the same number of times on both the sides. Suppose 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
. 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
and
. Thus, X is counted only once in the first summand and is not counted in any other summand since
for all i. Now let x have k properties say
,
,
,
(and no others). Then x is counted once in X. In the next sum, x occurs
times and so on. Thus, on the right hand side, x is counted precisely,
times. Using the binomial theorem, this sum is which is 0 and hence, x is not counted on the right hand side. This completes the proof. QED.
More later,
Nalin Pithwa