    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