The involution principleThe Garsia-Milne bijectionExercises

Exercises

E: Prove Theorem directly.
E: Check the details of the second example .
E: Assume X to be a finite set with subsets X1, ...,Xn. 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 Xi.
E: Show that
f(n)= åd | nd m(n/d), and n= åd | n f(d).
E: Evaluate the derangement number 
Dn:= | { pÎS n | " i În:pi not =i } | ,
i.e. the number of fixed point free elementes in Sn . Derive a recursion for these numbers and show that they tend to 1/e.
E: Prove the Two Involutions' Principle.

harald.fripertinger "at" uni-graz.at http://www-ang.kfunigraz.ac.at/~fripert/
UNI-Graz Institut für Mathematik
UNI-Bayreuth Lehrstuhl II für Mathematik
last changed: January 19, 2005

The involution principleThe Garsia-Milne bijectionExercises