Sign up ×
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.

This question already has an answer here:

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|cite|improve this question

marked as duplicate by Marc van Leeuwen, André Nicolas combinatorics Users with the  combinatorics badge can single-handedly close questions as duplicates and reopen them as needed. Feb 22 at 15:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

The same problem as in –  miracle173 Jun 2 '11 at 23:11

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|cite|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

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

share|cite|improve this answer

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