In: Advanced Math
Let P = (p1,...,pn) be a permutation of [n]. We say a
number i is a fixed point of p, if pi = i.
(a) Determine the number of permutations of [6] with at most three
fixed points.
(b) Determine the number of 9-derangements of [9] so that each even
number is in an even position.
(c) Use the following relationship (not proven here, but relatively
easy 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 help
of (∗), show that for all n ∈ N applies: n Dn =n! r=0 (-1)r
r!
(Note: Of course, do not use Sentence 2.7 or Corollary 2.2, it is
D0 = 1 and D1 = 0. Note that (∗) is also valid for n = 1 because of
the factor (n - 1), no matter how we would define D-1. Then first
look at the numbers An = Dn-nDn-1 (∗∗) and show that An = (-1)n is
valid. Then divide both sides of (∗∗) by n! and deduce from this
the assertion).