Exercice corrigé : Points fixes et dérangements (type Mines-Ponts)

Pour $n\in\mathbb N^*$, on note $\mathfrak S_n$ l'ensemble des permutations de $\llbracket1,n\rrbracket$. Un point fixe de $\sigma$ est un entier $i$ tel que $\sigma(i)=i$ ; on note $\operatorname{fix}(\sigma)$ leur nombre. Un dérangement est une permutation sans point fixe. On note $d_n$ le nombre de dérangements de $\llbracket1,n\rrbracket$ et on pose $d_0=1$. On admet que, pour tout ensemble fini $F$ à $m$ éléments, le nombre de permutations de $F$ sans point fixe vaut $d_m$ (avec $d_0=1$ si $F=\varnothing$).

1. Déterminer $d_1$, $d_2$, $d_3$ en listant les dérangements.
2. Soit $k\in\llbracket0,n\rrbracket$. Montrer que le nombre de permutations de $\llbracket1,n\rrbracket$ ayant exactement $k$ points fixes vaut $\binom nkd_{n-k}$. En déduire $n!=\sum_{k=0}^n\binom nkd_{n-k}$.
3. Calculer $d_4$ et $d_5$.
4. En dénombrant de deux façons l'ensemble des couples $(\sigma,i)\in\mathfrak S_n\times\llbracket1,n\rrbracket$ tels que $\sigma(i)=i$, montrer que $\sum_{\sigma\in\mathfrak S_n}\operatorname{fix}(\sigma)=n!$. Interpréter.
5. Soit $n\ge1$. Pour $j\in\llbracket1,n\rrbracket$, on note $D_j$ l'ensemble des dérangements $\sigma$ de $\llbracket1,n+1\rrbracket$ tels que $\sigma(n+1)=j$. a) Montrer que les $\sigma\in D_j$ tels que $\sigma(j)=n+1$ sont au nombre de $d_{n-1}$. b) Montrer que les $\sigma\in D_j$ tels que $\sigma(j)\ne n+1$ sont au nombre de $d_n$. On pourra poser $m=\sigma^{-1}(n+1)$ et définir une permutation $\tau$ de $\llbracket1,n\rrbracket$ par $\tau(m)=j$ et $\tau(i)=\sigma(i)$ pour $i\ne m$. c) En déduire que $d_{n+1}=n(d_n+d_{n-1})$.
6. Montrer que $d_n-nd_{n-1}=(-1)^n$ pour $n\ge1$, puis que $d_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ pour tout $n\in\mathbb N$.