Formule du crible/Exercices/sur le dénombrement des dérangements

Exercice 3-1

Une secrétaire dispose de 12 enveloppes portant chacune l’adresse d’un client différent. Elle a aussi 12 lettres différentes à envoyer à chacun des 12 clients. Ne sachant pas pour chaque client quelle lettre doit lui être destinée, elle met au hasard chacune des 12 lettres dans chacune des 12 enveloppes et les poste en priant le ciel que chaque client reçoive sa lettre.

1. Quelle est la probabilité que son vœu soit exaucé ?
2. Quelle est la probabilité qu’aucun des clients ne reçoivent sa lettre ?
3. Quelle est la probabilité que deux clients exactement reçoivent leur lettre ?

Solution

1. Il y a une seule permutation favorable pour que tous les clients reçoivent leur lettre, et il y a 12 ! = 479001600 permutations possibles.

La probabilité que tous les clients reçoivent leurs lettres est donc :

${\frac {1}{479001600}}$.

2. La probabilité qu’aucun clients ne reçoivent sa lettre est :

$\sum _{k=0}^{12}{\frac {(-1)^{k}}{k!}}={\frac {16019531}{43545600}}\approx 0{,}368$.

3. La probabilité que deux clients exactement reçoivent leur lettre est la probabilité que la secrétaire n’ait pas permuté leur lettre en les mettant dans l'enveloppe. c'est-à-dire :

${\frac {1}{2!}}\sum _{k=0}^{12-2}{\frac {(-1)^{k}}{k!}}\approx {\frac {1}{\mathrm {e} \times 2!}}\approx 0{,}184$.

 

Exercice 3-2

Montrer que pour $n\in \mathbb {N} ^{*}$, le nombre de dérangements d'un ensemble à n éléments est l'entier le plus proche de ${\frac {n!}{\mathrm {e} }}$.

Solution

Ce nombre de dérangements $N_{n}$ est entier et vérifie :

${\frac {n!}{\mathrm {e} }}-N_{n}=n!\sum _{k=n+1}^{\infty }{\frac {(-1)^{k}}{k!}}$.

On voit apparaître le reste d'une série exponentielle alternée dont la valeur absolue du terme général est une suite strictement décroissante. La valeur absolue de ce reste est strictement majorée par celle de son premier terme, donc

$\left|{\frac {n!}{\mathrm {e} }}-N_{n}\right|<{\frac {1}{n+1}}\leq {\frac {1}{2}}$.