Next: Introduction to graphs Up: Special Sequences of Integers Previous: Bell numbers   Contents

## Inclusion-Exclusion Principle

Note that .

Theorem 8.6.15 (Principle of Inclusion-Exclusion)   Given then

 where .

Proof. We consider and note that

Summing over we obtain the result

which is equivalent to the required result.

Just for the sake of it, we'll prove it again!

Proof. For each we calculate the contribution. If but is in no then there is a contribution to the left. The only contribution to the right is when . If and is non-empty then the contribution to the right is , the same as on the left.

Example 8.6.16 (Euler's Phi Function)

Proof. [Solution] Let , where the are distinct primes and . Let be the set of integers less than which are divisible by . Hence . Now , in fact for we have . Thus

Example 8.6.17 (Derangements)   Suppose we have mathematicians at a meeting. Leaving the meeting they pick up their overcoats at random. In how many ways can this be done so that none of them has his own overcoat. This number is , the number of derangements of objects.

Proof. [Solution] Let be the number of ways in which mathematician number collects his own coat. Then . If with then . Thus

Thus is the nearest integer to , since as .

Next: Introduction to graphs Up: Special Sequences of Integers Previous: Bell numbers   Contents
root 2002-06-10