3
$\begingroup$

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 number 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!

  • 0
    The same problem as in http://math.stackexchange.com/questions/146662011-06-02

2 Answers 2

4

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*} $

  • 0
    @Yuval-Filmus thank you!2011-05-29
6

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

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