Let P = (p1,...,pn) be a permutation of [n]. We say anumber i is a fixed point of p, if pi = i.
(a) Determine the number of permutations of [6] with at most threefixed points.
(b) Determine the number of 9-derangements of [9] so that each evennumber is in an even position.
(c) Use the following relationship (not proven here, but relativelyeasy to see) for the Rencontre numbers:
Dn =(n-1)-(Dn-1 +Dn-2) (?)
to perform an alternative proof of theorem 2.7. So, with the helpof (?), show that for all n ? N applies: n Dn =n! r=0 (-1)rr!
(Note: Of course, do not use Sentence 2.7 or Corollary 2.2, it isD0 = 1 and D1 = 0. Note that (?) is also valid for n = 1 because ofthe factor (n - 1), no matter how we would define D-1. Then firstlook at the numbers An = Dn-nDn-1 (??) and show that An = (-1)n isvalid. Then divide both sides of (??) by n! and deduce from thisthe assertion).
