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.

An $i \in [n]$ is called a fixed point of a permutation $\sigma \in S_n$ if $\sigma(i) = i$.

Let $D(n)$ be the amount of permutations $\sigma \in S_n$ without any fixed point.

Prove that

i) $D(n) = n \cdot D(n-1) + (-1)^n$ for $n \geq 2$

ii) $D(n) = (n-1)(D(n-1) + D(n-2))$ for $n \geq 3$

First I tried to write down all fixed point-less permutations (in one-line notation):

$n \leq 1 \rightarrow$: none

$n = 2$: (2 1)

$n = 3$: (2 3 1) (3 1 2)

$n = 4$ (2 1 4 3) (2 3 4 1) (2 4 1 3) (3 1 4 2) (3 4 1 2) (3 4 2 1) (4 1 2 3) (4 3 1 2) (4 3 2 1)

Unfortunately I didn't find any way of constructing these permutations by using the ones from $(n-1)$.

Could you please help me a little bit?

Thank you in advance!

share|improve this question
    
The same problem as in math.stackexchange.com/questions/14666 –  miracle173 Jun 2 '11 at 23:11
add comment

2 Answers 2

up vote 2 down vote accepted

Part (ii) is explained in the Wikipedia article that user6312 mentioned. Part (i) can be derived from part (ii) by induction.

You could also derive all of these "brute force" using the inclusion-exclusion principle. Using the principle, you write an explicit formula for $D(n)$. Then you do some algebra and you should get both parts. But Wikipedia's proof is better, since it explains why the formula is true.

Edit: More on deriving (i) from (ii): $$ \begin{align*} D(n) &= (n-1)(D(n-1)+D(n-2)) \\ &= (n-1)((n-1)D(n-2)+(-1)^{n-1} + D(n-2)) \\ &= (n-1)(nD(n-2) + (-1)^{n-1}) \\ &= n(n-1)D(n-2) + (n-1)(-1)^{n-1} \\ &= n((n-1)D(n-2) + (-1)^{n-1}) - (-1)^{n-1} \\ &= nD(n-1) + (-1)^n. \end{align*} $$

share|improve this answer
    
@user6312 @Yuval-Filmus the part (ii) is completely clear now, thank you both! @Yuval-Filmus What do you mean with " [..] can be drived from part (ii) by induction"?. If using the identity of (ii) I get $$D(n+1) = n \cdot D(n) + D(n-1)$$ but how do I transform that into something similar like the identity of (i)? –  muffel May 29 '11 at 20:13
    
@muffel: Do a proof by induction. –  Yuval Filmus May 29 '11 at 21:03
    
@Yuval-Filmus induction of what exactly? Thank you for your addition. Could you please tell me what you did to get from the first to the second line? (how you introducted the $(-1)^{(n-1)}$)? –  muffel May 29 '11 at 21:12
    
@muffel: I used a proof by induction. Assuming the formula for $n-1$, I prove it for $n$ using (ii). You also have to check the base case $D(2) = 2D(1) + 1$. –  Yuval Filmus May 29 '11 at 21:17
    
@Yuval-Filmus thank you! –  muffel May 29 '11 at 21:21
add comment

These are called derangements. For a discussion, please see for example

http://en.wikipedia.org/wiki/Derangement

share|improve this answer
add comment

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.