A fixed point of a permutation f is an element x of the domain such that f(x) = x. A derangement is a permutation f with no fixed points; i.e., f(x) x for all x. (a)Prove that the probability that a random permutation f of n has f(k) = k equals 1/n. (b)If we treat the n events f(1) 1, f(n) #n as independent, what is the probability that fis a derangement? Conclude that we might expect approximately n!/e derangements of n. (c)Let D, be the number of derangements of n. Prove that the number of permutations of n with exactly k fixed points is Dn-k () - kl e: n!