Le calcul du nombre de dérangements est un grand classique souvent posé lors d’exercices, notamment à l’écrit. Dans cet exercice détaillé, nous allons donc en faire le calcul.
Prérequis facultatif
Énoncé
En voici son énoncé :
Corrigé
Question 1
Le raisonnement est le suivant : on a \binom{n}{k} façon d’obtenir les k points fixes. Il reste alors n-k éléments pour lesquels nous sommes sûrs de ne pas avoir de points fixes. Donc, pour ces n-k points fixes, on a D_{n-k} choix possibles. Cela nous donne bien le résultat voulu :
P_{k,n} = \binom{n}{k} D_{n-k}Question 2
La réponse à la question est assez simple :
Toute permutation a un nombre de points fixes entre 0 et n donc en sommant les permutations ayant k points fixes en faisant varier k de 0 à n, on aura le résultat. De plus, on a n ! permutations. On a donc :
\begin{array}{ll}
n ! & = \displaystyle \sum_{k = 0}^n P_{k,n}\\
& = \displaystyle \sum_{k = 0}^n \binom{n}{k}D_{n-k}\\
\end{array}Question 3
On peut faire une récurrence (laissée au lecteur) mais on va vous démontrer le résultat avec la formule d’inversion de Pascal. On a :
\begin{array}{ll}
n ! & = \displaystyle \sum_{k = 0}^n \binom{n}{k}D_{n-k}\\
& = \displaystyle \sum_{k = 0}^n \binom{n}{n-k}D_{k}\\
& = \displaystyle \sum_{k = 0}^n \binom{n}{k}D_{k}\\
\end{array}Ainsi,
\begin{array}{ll}
D_n & = \displaystyle \sum_{k = 0}^n (-1)^{n-k}\binom{n}{k}k!\\
& = \displaystyle \sum_{k = 0}^n (-1)^{n-k}\dfrac{n!}{k!(n-k)!}k!\\
& =n! \displaystyle \sum_{k = 0}^n (-1)^{n-k}\dfrac{1}{(n-k)!}\\
& =n! \displaystyle \sum_{k = 0}^n (-1)^{k}\dfrac{1}{k!}\\
\end{array}Ce qui est bien le résultat recherché. On a donc calculé le nombre de dérangements.
Question 4
Et une dernière petite question pour le plaisir : On sait que
\lim_{n \to + \infty} \sum_{k = 0}^n (-1)^{k}\dfrac{1}{k!} = \dfrac{1}{e}On a ainsi,
D_n \sim \dfrac{n!}{e}Ce qui conclut cet exercice sur le nombre de dérangements !
