exo7 5286

Soit $E$ un ensemble fini et non vide. Soient $n$ un entier naturel non nul et $A_1$,..., $A_n$, $n$ parties de $E$. Montrer la  formule du crible  :

$$\begin{align*}\ensuremath \mbox{card}(A_1\cup...\cup A_n)&=\sum_{i=1}^{n}\mbox{card}(A_i)-\sum_{1\leq i_1< i_2\leq n}^{}\mbox{card}(A_{i_1}\cap A_{i_2})\\ &+...+(-1)^{k-1}\sum_{1\leq i_1<i_2<...<i_k\leq n}^{}\mbox{card}(A_{i_1}\cap A_{i_2}\cap...\cap A_{i_k})\\ &+...+(-1)^{n-1}\mbox{card}(A_1\cap...\cap A_n). \end{align*}$$

Combien y a-t-il de permutations $\sigma$ de $\{1,...,n\}$ vérifiant $\forall i\in\{1,...,n\},\;\sigma(i)\neq i$ ? (Ces permutations sont appelées dérangements (permutations sans point fixe)). Indication : noter $A_i$ l’ensemble des permutations qui fixent $i$ et utiliser 1).

On peut alors résoudre un célèbre problème de probabilité, le problème des chapeaux. $n$ personnes laissent leur chapeau à un vestiaire. En repartant, chaque personne reprend un chapeau au hasard. Montrer que la probabilité qu’aucune de ces personnes n’ait repris son propre chapeau est environ $\frac{1}{e}$ quand $n$ est grand.