Nombre de dérangements en taille $n$

On désigne par $\mathfrak{D}_n$ le nombre de dérangements en taille $n\geqslant1$, c’est-à-dire, le nombre de permutations sans point fixe du groupe de permutations $\mathfrak{S}_n$. On veut montrer que $\mathfrak{D}_n = \sum_{k=0}^{n} (-1)^k \cdot \dfrac{n!}{k!}$.

1. En considérant le nombre de points fixes d’une permutation arbitraire de $\mathfrak{S}_n$, montrer la relation $n! = \sum_{k=0}^{n} \binom{n}{k} \mathfrak{D}_{n-k}$ pour tout entier $n\geqslant1$. Supposons aussi que $\mathfrak{D}_0=1=0!$ de sorte que la relation soit toujours vérifiée pour $n=0$.

2. Montrer que $S(x) := \sum_{n\geqslant0} \dfrac{\mathfrak{D}_n}{n!} x^n$ a un rayon de convergence supérieur ou égal à $1$.

3. Montrer que pour tout $x \in \, ]-1,1[$, on a $S(x) = \dfrac{e^{-x}}{1-x}$.

4. Retrouver le résultat.

Considérons maintenant quelques applications de ce résultat.

5. Imaginons $n$ seigneurs qui se rendent à une fête et laissent leurs chapeaux à l’entrée. De retour, complètement ivres, ils ne savent plus quel chapeau est le leur et chacun en prend un au hasard. Quelle est la probabilité, pour $n$ très grand, qu’aucun des seigneurs ne reparte avec son propre chapeau ?

6. Montrer que le nombre de dérangements en taille $n$ est l’entier le plus proche de $\dfrac{n!}{e}$.