# Recursive Derangement Formula proof

• May 27th 2013, 11:24 PM
Yuuki
Recursive Derangement Formula proof
I'm stuck on the proof in the title.

Consider a derangement on {1,2,...,n}
Let
Xk: set of derangements with the last element k
Yk: set of derangements in Xk with the k-th element n
Zk: set of derangements in Xk with the k-th element not n
Then, (i) if entries n and k are deleted in the derangements in Yk, the result is a derangement on {1,2,...,k-1,k+1,...,n} and (ii)Zk is the set of derangements on {1,2,...,n,...,n-1}

I tried to justify (i) by starting with the supposition that xi = i in the new derangement.

If http://latex.codecogs.com/gif.latex?...0i%5Cleq%20k-1, then since such xis are unaffected by the deletion, xi = i in the original derangement, so this is a contradiction.

But I don't know how to make a contradiction for http://latex.codecogs.com/gif.latex?...0i%5Cleq%20n-2.
I don't see what's wrong with having xk+2=k+1 in the original derangement (and then having xk+1=k+1 in the new arrangement, and not result in a derangement.)

For (ii), I need help getting started with the proof.