2
$\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 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!

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

2 Answers 2

3

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
    @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)?2011-05-29
  • 0
    @muffel: Do a proof by induction.2011-05-29
  • 0
    @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)}$)?2011-05-29
  • 0
    @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$.2011-05-29
  • 0
    @Yuval-Filmus thank you!2011-05-29
5

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

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