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

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 cant 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 dont see how i can prove its odd if and only if n is even .

-
in this question $Derangement=Number of permutations - fixed points$ – Boris Morozov Mar 9 '14 at 10:05
thanks . just fixed it . – Boris Morozov Mar 18 '14 at 7:14

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.

-
this proof is really cool . but its a question from combinatorics exam and i cant use abstract algebra in the proof . – Boris Morozov Mar 9 '14 at 10:44
@BorisMorozov: What abstract algebra? This is all combinatorics. The most non-combinatoricsy bit is the note about a determinant in the alternate proof, and that's linear algebra. Even if abstract algebra was involved, I'd be surprised if they marked down a proof for using group theory or something. – user2357112 Mar 9 '14 at 15:20
-user2357112 isn't "parity of permutation" is a definition from "group theory" ? and group theory is part of abstract algebra ? no they won't mark it down but i wanted to see how they intended us to solve it . -bof the last proof is very nice .... – Boris Morozov Mar 10 '14 at 12:22

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.

-
thanks for easy and short answer. now it looks so obvious. – Boris Morozov Mar 9 '14 at 10:10
One can give an even easier and shorter answer using the recurrence equation $D_n=nD_{n-1}+(-1)^n$. – bof Mar 9 '14 at 10:23
i found a little mistake its $(-1)^i$ and not $(-1)^n$ im still not sure if it changes anything .... – Boris Morozov Mar 9 '14 at 10:38
Oh my, two bugs (both should be fixed now). – Rebecca J. Stones Mar 9 '14 at 20:37

Yet another way of showing the result is down your original path, using the recurrence relation $!n=(n-1)\left(!(n-1)+!(n-2)\right)$. You can show the first few cases by hand, and then use induction: if $n$ is odd, then $n-1$ is even, and by the induction hypothesis $!(n-1)$ is odd; likewise, $n-2$ is odd and so by the induction hypothesis, $!(n-2)$ is even and $\bigl(!(n-1)+!(n-2)\bigr)$ is odd, leading to the result that $!n=(n-1)\cdot\bigl(!(n-1)+!(n-2)\bigr) = \mathrm{even}\cdot\mathrm{odd}$ is even. Similarly, if $n$ is even then $n-1$ is odd and $n-2$ is even, so $!(n-1)$ is even, $!(n-2)$ is odd; then once again $\bigl(!(n-1)+!(n-2)\bigr)$ is odd, and so $!n = (n-1)\cdot \bigl(!(n-1)+!(n-2)\bigr) = \mathrm{odd}\cdot\mathrm{odd}$ is odd.

-