Let $D_n$ be a number of derangement of $n$ items. Prove that $D_n$ is odd if and only if $n$ is even.
I was trying to use induction on the $!n=(n-1)(!(n-1)+!(n-2))$ recurrence relation but I can't derive the parity of the $!(n-2)$.
The other way I was thinking about is direct proof using the standard sum we get from inclusion-exclusion principle $$n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$$ but I don't see how I can prove it's odd if and only if $n$ is even.
Best Answer
Generally, derangements come in pairs: the inverse of a derangement is a derangement. The exceptions are the fixed-point-free involutions, i.e., the permutations in which every cycle is a $2$-cycle. Thus the parity of the number of derangements is the same as the parity of the number of fixed-point-free involutions.
If $n$ is odd, there are no fixed-point-free involutions, so the number of derangements is even.
If $n$ is even, say $n=2k$, then the number of fixed-point-free involutions is $(2k-1)(2k-3)(2k-5)\cdots3\cdot1$, an odd number.
Alternatively: Let $A_n$ be the number of even derangements of $n$ items, i.e., derangements which are even permutations; and let $B_n$ be the number of odd derangements. Establish the identity $A_n-B_n=(-1)^{n-1}(n-1)$. (Note that this is the value of a certain determinant, namely, the determinant of an $n\times n$ matrix with zeros on the main diagonal and ones everywhere else.) It follows that$$D_n=A_n+B_n=A_n-B_n+2B_n=(-1)^{n-1}(n-1)+2B_n\equiv n-1\pmod2.$$
Yet another way using the identity $D_n=nD_{n-1}+(-1)^n$ (which is easily derivable from the familiar inclusion-exclusion formula for $D_n)$. Clearly, if $n$ is even, then $D_n=nD_{n-1}+(-1)^n$ is odd. On the other hand, if $n$ is odd, then $nD_{n-1}$ is odd, and so $D_n=nD_{n-1}+(-1)^n$ is even.