# Formule du crible/Dénombrement des dérangements
## Définition

Un dérangement d’un ensemble E est une permutation de E sans point fixe.
Nous désignerons par N$_n$ le nombre de dérangements d'un ensemble E à n éléments.
Sans nuire à la généralité, nous pouvons supposer que E = {1, 2, … , n}.
Nous savons qu’il y a n! permutations de E.
Dans cette étude, nous noterons A$_i$ l’ensemble des permutations de E laissant fixe au moins le point i.
A$_i$ ∩ A$_j$ représente alors l’ensemble des permutations de E laissant au moins i et j fixes.
A$_i$ ∪ A$_j$ représente l’ensemble des permutations laissant au moins i ou j fixes.
L’ensemble des dérangements de E est alors :
    ${\overline {\bigcup _{i=1}^{n}A_{i}}}$.

## Exemple

Soit E = {1, 2, 3, 4} de cardinal 4. Il y a 4! = 24 permutations de cet ensemble.
Celles-ci peuvent être représentées par :
En répartissant les différentes permutations dans les ensembles A$_1$, A$_2$, A$_3$, A$_4$, nous obtenons :
Nous voyons alors qu’il y a 9 dérangements de E, à savoir h, j, l, n, q, r, s, w et x.

## Cas général

* Le nombre $N_{n}$ de dérangements d’un ensemble à n éléments est donné par :
    $N_{n}=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}$.
* Pour $n\in \mathbb {N} ^{*}$, $N_{n}$ est l'entier le plus proche de ${\frac {n!}{\mathrm {e} }}$.
Pour tout ensemble d'indices $I\subset E=\{1,\dots ,n\}$, notons $A_{I}:=\bigcap _{i\in I}A_{i}$ l'ensemble des permutations de E qui fixent tous les éléments de I. La formule du crible donne :
    ${\begin{aligned}N_{n}&=\operatorname {card} \left({\overline {\bigcup _{i=1}^{n}A_{i}}}\right)\\&=n!-\operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)\\&=n!-\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset E \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\\&=n!+\sum _{k=1}^{n}(-1)^{k}\sum _{I\subset E \atop \operatorname {card} (I)=k}(n-k)!\\&=n!+\sum _{k=1}^{n}(-1)^{k}{\binom {n}{k}}(n-k)!\\&=n!+\sum _{k=1}^{n}(-1)^{k}{\frac {n!}{k!}}\\&=n!(\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}).\end{aligned}}$
On trouvera une autre démonstration de cette égalité dans la leçon : Formule d'inversion de Pascal.
Quant à la propriété d'approximation de ${\frac {n!}{\mathrm {e} }}$, elle fait l'objet d'un exercice corrigé.
Pour un calcul de probabilité, N$_n$ sera divisé par le nombre de permutations de E, à savoir n! ; il restera :
    $p\left({\overline {\bigcup _{i=1}^{n}A_{i}}}\right)=\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}$.
Nous remarquons que
    $\lim _{n\to \infty }p\left({\overline {\bigcup _{i=1}^{n}A_{i}}}\right)=\mathrm {e} ^{-1}$.
La convergence est très rapide puisque nous avons des factorielles en dénominateur. À tel point que pour un ensemble d'au moins six éléments, la probabilité de tomber sur un dérangement parmi ces permutations pourra être prise égale à e$^{–1}$ avec une erreur inférieure au millième. (Avec un ensemble à 4 éléments, l'erreur est inférieure au centième.)

## Probabilité qu'une permutation laisse r points fixes

Soit r un nombre entier vérifiant : 0 ≤ r ≤ n. La probabilité de laisser exactement r éléments fixes lorsqu'on effectue au hasard une permutation d'un ensemble à n éléments est :
    ${\frac {1}{r!}}\sum _{k=0}^{n-r}{\frac {(-1)^{k}}{k!}}$.
Soient E un ensemble à n éléments, et X la variable aléatoire qui prend pour valeur le nombre r d'éléments fixes lors d'une permutation hasardeuse de E. Calculons p(X = r).
Pour cela, nous choisissons les r éléments devant rester fixes, soit ${\binom {n}{r}}$ possibilités. Nous dérangeons les n – r éléments restants, soit N$_{n–r}$ possibilités. Pour avoir la probabilité, il nous faut ensuite diviser par le nombre total de permutations de E, c'est-à-dire n!. On a donc :
    ${\begin{aligned}p(X=r)&={\frac {{\binom {n}{r}}\times N_{n-r}}{n!}}\\&={\frac {1}{n!}}\times {\frac {n!}{r!(n-r)!}}\times (n-r)!\sum _{k=0}^{n-r}{\frac {(-1)^{k}}{k!}}\\&={\frac {1}{r!}}\sum _{k=0}^{n-r}{\frac {(-1)^{k}}{k!}}.\end{aligned}}$
Pour n suffisamment grand, cette probabilité pourra être approchée par
    ${\frac {1}{\mathrm {e} \ r!}}$.
| Dénombrement des surjections | Rencontre du second type |