Formule du crible/Dénombrement des dérangements

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Définition

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.

Celle-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

Début d’un théorème

Théorème

• 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} }}$.

Fin du théorème

Début d'une démonstration

Démonstration

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é.

Fin de la démonstration

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

Corollaire

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!}}$.

Démonstration

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}}$

 

Remarque

Pour n suffisamment grand, cette probabilité pourra être approchée par

${\frac {1}{\mathrm {e} \ r!}}$.