Principe d'inclusion-exclusion et dérrangements

Solution

1. Formule par inclusion-exclusion :
   Soit $A_i$ l'ensemble des permutations où $\sigma(i) = i$.
   Par inclusion-exclusion : $|A_1 \cup \cdots \cup A_n| = \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} (n-k)!$
   Donc $D_n = n! - |A_1 \cup \cdots \cup A_n| = \sum_{k=0}^{n} (-1)^k \binom{n}{k}(n-k)! = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$.
2. Récurrence :
   Soit $\sigma$ un dérangement. L'image $\sigma(n) = j \ne n$ ($(n-1)$ choix).
   Cas 1 : $\sigma(j) = n$ — les $n-2$ éléments restants forment un dérangement : $D_{n-2}$ façons.
   Cas 2 : $\sigma(j) \ne n$ — on renomme $j \to n$, les $n-1$ éléments forment un dérangement : $D_{n-1}$ façons.
   Donc $D_n = (n-1)(D_{n-1} + D_{n-2})$.
3. Valeurs et limite :
   $D_1 = 0$, $D_2 = 1$, $D_3 = 2(D_2 + D_1) = 2$, $D_4 = 3(D_3 + D_2) = 9$.
   $D_n/n! = \sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1} = 1/e \approx 0.368$ (série de l'exponentielle en $-1$).