.

Printable View

- Dec 10th 2010, 09:04 AMzukiasMathematical thinking proof question about derangements
.

- Dec 10th 2010, 10:48 AMSoroban
Hello, zukias!

Quote:

$\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$ isplaced in the second space.*not*

. . [2] $\displaystyle \,a$placed in the second space.*is*

[1] Suppose $\displaystyle \,a$ isin the second space.*not*

. . .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$in the second space, we have: .$\displaystyle b\,a\,\hdots\,n$*is*

. . .$\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]$

- Dec 10th 2010, 11:38 AMAlso sprach Zarathustra
Also...

With Inclusion method you can prove the following:

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