400 Combinatorics of Permutations, Second Edition
37. Let A
i
be the set of n-permutations in which i is a fixed point. Then
|A
i
1
∩···∩A
i
k
| =(n − k)!, and the result follows by the Principle of
Inclusion–Exclusion.
39. One of these sets is always one larger than the other. For odd n,the
set of n-permutations with exactly one fixed point is larger. For even n,
the set of derangements of length n is larger.
To see this, let G(n)bethenumberofn-permutations with exactly one
fixed point, and note that G(n)=nD
n−1
holds for all n ≥ 3. Indeed,
to find a permutation counted by G(n), first choose its only fixed point,
then choose a derangement on the remaining n−1 entries. On the other
hand, it follows from Corollary 3.57 that D
n
= nD
n−1
+(−1)
n
.This
proves our claim.
41. The ...