1. ## Mathematical thinking proof question about derangements

.

2. Hello, zukias!

$\text{]Given }n\text{ distinct objects how many ways is it possible to arrange them}$
$\text{so that none is in its original position?}$

$\text{Such a rearrangement is called a }derangement.$

$\text{It's easy to see that the number of rearrangements of }n\text{ objects is }n!,$
. . $\text{but what about the number of derangements?}$

$\text{Show that }d(n)\text{ satisfies the recurrence relation:}$

. . $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: . $a\,b\,c\,\hdots\,n$ . in their original positions.

For the first position, there are $\,n-1$ choices for the replacement for $\,a.$

Suppose it is $\,b$. .We have: . $b\,\_\,\_\,\hdots\,n$

What is placed in the second space?
There are two basic choices:
. . [1] $\,a$ is not placed in the second space.
. . [2] $\,a$ is placed in the second space.

[1] Suppose $\,a$ is not in the second space.
. . .Then we have $\,n-1$ objects $\{a,\,c,\,d,\,\hdots n\}$ to derange.
. . .There are: . $d(n-1)$ ways.

[2] If $\,a$ is in the second space, we have: . $b\,a\,\hdots\,n$
. . . $\,a$ and $\,b$ has swapped places; they are already deranged.
. . .We must derange the other $n-2$ objects: . $d(n-2)$ ways.

Hence, if $\,b$ is in the first space,
. . there are: . $d(n-1) + d(n-2)$ possible derangements.

Since there are $\,n-1$ choices for $\,b$, the number of derangements is:

. . $d(n) \;=\;(n-1)\bigg[d(n-1) + d(n-2)\bigg]$

3. Also...

With Inclusion method you can prove the following:

$\displaystyle d(n)=n![1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...(-1)^n\frac{1}{n!}]=n!\Sigma^{n}_{k=0}\frac{(-1)^k}{k!} \approx \frac{n!}{e} \approx 0.37n!$