Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 2 / b

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 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ such collections. Applying the inclusion-exclusion principle to exclude all fixed objects givesFor $n\ge 1$, the terms $k=0$ and $k=1$ cancel. Thus the number of derangements is $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$.