= Solution
Let $E_i$ be the <set> of <permutations> fixing object $i$. If a specified collection of $k$ objects is fixed, the remaining $n-k$ objects can be arranged in $(n-k)!$ ways. There are $\binom nk$ such collections. Applying the <inclusion-exclusion principle> to exclude all fixed objects gives
$$
d_n=\sum_{k=0}^n(-1)^k\binom nk(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.
$$
For $n\geq1$, the terms $k=0$ and $k=1$ cancel. Thus the number of <derangements> is \b[$\displaystyle d_n=\frac{n!}{2!}-\frac{n!}{3!}+\cdots+(-1)^n\frac{n!}{n!}$], interpreting the remaining <sum> as empty when $n=1$. The full <inclusion-exclusion> formula also gives $d_0=1$.
Back to article page
