
Mean and Insensitive. Random Permutations. 265
18. Let X
n
be defined on the set of derangements of length n, and let X
n
(p)
be the number of cycles of p.Provethatforn ≥ 4, we have
(n −1)D(n −2)E(X
n−2
+1)+(n −1)D(n −1)E(X
n−1
)=D(n)E(X
n
).
19. Let Y
n
be defined on the set of derangements of length n, and let Y
n
(p)
be the size of the cycle containing the maximal entry of p.Finda
recurrence relation for E(Y
n
).
20. We know from Section 1.2 that for any fixed n, the sequence G(n, k)is
unimodal. Where is the peak of that sequence, that is, for which k is
G(n, k) maximal?
21. Let p and q be two randomly selected n-permutations, and let G
p,q
be
the graph defined in Problem ...