Number of derangements of size $n$

We denote by $\mathfrak{D}_n$ the number of derangements of size $n\geqslant1$, that is, the number of permutations without fixed points of the permutation group $\mathfrak{S}_n$. We want to show that that $\mathfrak{D}_n = \sum_{k=0}^{n} (-1)^k \cdot \dfrac{n!}{k!}$.

1. By considering the number of fixed points of an arbitrary permutation of $\mathfrak{S}_n$, show the relation $n! = \sum_{k=0}^{n} \binom{n}{k} \mathfrak{D}_{n-k}$ for all integer $n\geqslant1$. Assume also that $\mathfrak{D}_0=1=0!$ so this relation also holds for $n=0$.

2. Show that $S(x) := \sum_{n\geqslant0} \dfrac{\mathfrak{D}_n}{n!} x^n$ has a radius of convergence greater than $1$.

3. Show that for all $x \in \, ]-1,1[$, we have $S(x) = \dfrac{e^{-x}}{1-x}$.

4. Recover the result.

Let us now consider some applications of this result.

5. Consider $n$ lords who go out to a party and leave their hats at the entrance. Coming back completely drunk, they no longer know which hat is theirs and each takes one at random. What is the probability, for $n$ very large, that none of the lords leaves with his own hat?

6. Show that the number of derangements of size $n$ is the integer closest to $\dfrac{n!}{e}$.