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

 

 

 

 

 

 

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: