Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 .

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

3 Answers 3

up vote 11 down vote accepted
+200

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.

share|improve this answer
    
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 at 10:44
1  
@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 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 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.

share|improve this answer
    
thanks for easy and short answer. now it looks so obvious. –  Boris Morozov Mar 9 at 10:10
3  
One can give an even easier and shorter answer using the recurrence equation $D_n=nD_{n-1}+(-1)^n$. –  bof Mar 9 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 at 10:38
    
Oh my, two bugs (both should be fixed now). –  Rebecca J. Stones Mar 9 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.