Exercises

Exercises

E: Prove Theorem directly.

E: Check the details of the second example .

E: Assume X to be a finite set with subsets X₁, ...,X_n. Use the Principle of Inclusion and Exclusion in order to derive the number of elements of X which lie in precisely m of these subsets X_i.

E: Show that

f(n)= å_{d | n}d m(n/d), and n= å_{d | n} f(d).

E: Evaluate the derangement number 

D_n:= | { pÎS _n | " i În:pi not =i } | ,

i.e. the number of fixed point free elementes in S_n . Derive a recursion for these numbers and show that they tend to 1/e.

E: Prove the Two Involutions' Principle.

Exercises