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.

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.

share|improve this question
1  
This is possibly a duplicate of this question. –  robjohn Sep 28 '12 at 19:10
add comment

3 Answers 3

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.
share|improve this answer
add comment

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

share|improve this answer
add comment

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.

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.