Prove: Number of derangement is odd if and only if number of items is even .

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.

It is possible to find the parity from the formula $$\sum_{i=0}^n (-1)^i \frac{n!}{i!}=\sum_{i=0}^n (-1)^i n(n-1)\cdots(i+1).$$

Working modulo $2$:

• If $n$ is even, then there is one non-zero contribution to the sum is when $i=n$, so we have an odd number.

• If $n$ is odd, then there are two non-zero contributions to the sum, when $i=n$ and when $i=n-1$, so we have an even number.