Combinatorial argument to prove the recurrence relation for number of derangements

Question

Give a combinatorial argument to prove that the number of derangements satisfies the following relation:

$$d_n = (n − 1)(d_{n−1} + d_{n−2})$$

for $n \geq 2$.

I am able to prove this algebraically but not able to see the combinatorial example.

Answer 1

Suppose that $f:[n]\to[n]$ is a bijection with no fixed points. Then $f(n)\in\lbrace 1,\ldots,n-1\rbrace$. All these cases are the same up to relabelling, so suppose $f(n)=n-1$. Now define $g:[n-1]\to[n-1]$ by $g(x)=f(x)$, unless $f(x)=n$ in which case define $g(x)=n-1$. If $g$ has no fixed points, fine. Otherwise, since $f$ has no fixed points, it must be that $g(n-1)=n-1$, i.e., $f(n-1)=n$. Thus $f$ just swaps $n$ and $n-1$ and $f|_{[n-2]}$ must have no fixed points.

Now just check that each of the terms in your formula are accounted for and nothing is counted twice.

Answer 2

This is directly from Wikipedia and I think is understandable enough, and hence I post it here again.

Suppose that there are $n$ persons numbered $1, 2, ..., n$. Let there be n hats also numbered $1, 2, ..., n$. We have to find the number of ways in which no one gets the hat having same number as his/her number. Let us assume that the first person takes hat $i$. There are $n − 1$ ways for the first person to make such a choice. There are now two possibilities, depending on whether or not person $i$ takes hat $1$ in return:

1. Person $i$ does not take the hat $1$. This case is equivalent to solving the problem with $n − 1$ persons $n − 1$ hats: each of the remaining $n − 1$ people has precisely $1$ forbidden choice from among the remaining $n − 1$ hats ($i$'s forbidden choice is hat $1$).
2. Person $i$ takes the hat $1$. Now the problem reduces to $n − 2$ persons and $n − 2$ hats.

Answer 3

This is simply the first method given in this answer. In that answer, three methods for computing the number of derangements are given.