Say that a permutation a₁ a₂a_n of the numbers 1 to n is \emph{good} if there does not exist i,j{1,2,...,n} such that a_i=j and a_j=i. Note that i and j may be equal, and so every such permutation is a derangement. Let g_n be the number of good permutations of length n. Observe that g₁=0 and g₂=0.

(a) List out all of the good permutations of length 3. Why are they the only ones?

(b) Recall that d_n denotes the number of derangements of length n. For n4, how many derangements a₁ a₂a_n of length n are there such that a₁=2, a₂=1, a₃=4 and a₄=3?

(c) Let p_k be the number of ways to partition a set of size 2k into k sets of size 2. Prove that p_k=(2k)!/2^k. (Hint: Its just a multinomial coefficient).

(d) Given a real number x, let x ibe the largest integer m such that m x. Prove that

_n/2 g_n = (1)^k(n 2k)((2k)!/2^k )d_n2k

^k=0 for all n 1.