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.