.
Hello, zukias!
$\displaystyle \text{]Given }n\text{ distinct objects how many ways is it possible to arrange them}$
$\displaystyle \text{so that none is in its original position?}$
$\displaystyle \text{Such a rearrangement is called a }derangement.$
$\displaystyle \text{It's easy to see that the number of rearrangements of }n\text{ objects is }n!,$
. . $\displaystyle \text{but what about the number of derangements?}$
$\displaystyle \text{Show that }d(n)\text{ satisfies the recurrence relation:}$
. . $\displaystyle d(n) \;=\; (n - 1) \bigg[d(n - 1) + d(n - 2)\bigg],\;\;\text{ for }n \ge 3.$
This is the way it was explained to me . . .
We have this set of objects: .$\displaystyle a\,b\,c\,\hdots\,n$ . in their original positions.
For the first position, there are $\displaystyle \,n-1$ choices for the replacement for $\displaystyle \,a.$
Suppose it is $\displaystyle \,b$. .We have: .$\displaystyle b\,\_\,\_\,\hdots\,n$
What is placed in the second space?
There are two basic choices:
. . [1] $\displaystyle \,a$ is not placed in the second space.
. . [2] $\displaystyle \,a$ is placed in the second space.
[1] Suppose $\displaystyle \,a$ is not in the second space.
. . .Then we have $\displaystyle \,n-1$ objects $\displaystyle \{a,\,c,\,d,\,\hdots n\}$ to derange.
. . .There are: .$\displaystyle d(n-1)$ ways.
[2] If $\displaystyle \,a$ is in the second space, we have: .$\displaystyle b\,a\,\hdots\,n$
. . .$\displaystyle \,a$ and $\displaystyle \,b$ has swapped places; they are already deranged.
. . .We must derange the other $\displaystyle n-2$ objects: .$\displaystyle d(n-2)$ ways.
Hence, if $\displaystyle \,b$ is in the first space,
. . there are: .$\displaystyle d(n-1) + d(n-2)$ possible derangements.
Since there are $\displaystyle \,n-1$ choices for $\displaystyle \,b$, the number of derangements is:
. . $\displaystyle d(n) \;=\;(n-1)\bigg[d(n-1) + d(n-2)\bigg]$