Formule du crible/Dénombrement des dérangements

Définition

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₁, A₂, A₃, A₄, 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

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

$\underset{n\to \mathrm{\infty }}{\lim }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.)