Principe d'inclusion-exclusion

Proposition. Soit $\Omega$ un ensemble. Soient $A_1,A_2,..., A_n$ une famille de $n$ sous-ensembles de $\Omega$. On a :

$$\begin{eqnarray*} {\mbox{\rm {\Large {\bf 1}}}}_{A_1\cup A_2\cup ...\cup A_n}&=&... ... {\bf 1}}}_{A_{i_1}}\ldots \mbox{\rm {\Large {\bf 1}}}_{A_{i_k}} \end{eqnarray*}$$

et si $A_1,A_2,..., A_n$ sont tous de cardinal fini, alors :

$$\begin{eqnarray*} card(A_1\cup .. \cup A_n)&=&\sum_1^n card(A_i)-\sum_{1\leq i<j... ...\ldots \leq i_k \leq n} card({A_{i_1}}\cap\ldots \cap {A_{i_k}}) \end{eqnarray*}$$

Preuve. Nous avons clairement :

$${\mbox{\rm {\Large {\bf 1}}}}_{A_1\cup A_2}={\mbox{\rm {\Lar... ...rm {\Large {\bf 1}}}}_{A_1}{\mbox{\rm {\Large {\bf 1}}}}_{A_2}.$$

Donc, la première relation est vraie pour $n=2$. Supposons la vraie pour $n$ et prouvons-la pour $n+1$. On a :

$$\begin{eqnarray*}{\mbox{\rm {\Large {\bf 1}}}}_{A_1\cup A_2 \cup ...\cup A_n \cu... ...{\Large {\bf 1}}}}_{A_n}{\mbox{\rm {\Large {\bf 1}}}}_{A_{n+1}}. \end{eqnarray*}$$

Pour démontrer la deuxième relation dans le cas des parties finies, il suffit d'appliquer l'égalité $card(A)=\sum_{\omega \in \Omega}{\mbox{\rm {\Large {\bf 1}}}}_A(\omega)$ au membre de la première relation.

Une application : Problème des chapeaux

Problème. En entrant, chacun des $n$ convives confie son chapeau au vestiaire et il le reprend en partant. Au moment de départ une panne d'électricité survient et chacun prend un chapeau au hasard. Quelle est la probabilité pour que, au moins, un des convives ait son propre chapeau ? Quelle en est la limite lorsque $n\rightarrow \infty$ ?

Solution. On part du principe que la probabilité d'un événement $A$ est le rapport entre le nombre de cas favorables à $A$ et le nombre total de cas possibles.
Le nombre total de répartitions possibles est $n!$. Si $A_i$ désigne l'événement ``le $i$-ème invité a eu son propre chapeau'', la probabilité $p_n$ recherchée vaut :

$$p_n=\frac {card(A_1\cup A_2\cup ... \cup A_n)}{n!}.$$

Nous avons, par ailleurs : $\forall k \geq 1$

$$\begin{eqnarray*} \sum_{1\leq i_1< i_2<...<i_k\leq n}card(A_{i_1}\cap...\cap A_... ...{1\leq i_1< i_2<...<i_k\leq n}(n-k)!\\ &=&{n\choose k} (n-k)! \end{eqnarray*}$$

En appliquant le principe d'inclusion-exclusion à $card(A_1\cup A_2\cup ... \cup A_n)$, il vient :

$$\begin{eqnarray*}p_n & = & 1- \frac 1 {2!}+ \frac 1 {3!} - ... + (-1)^n \frac 1 {n!}\\ &= & 1-\sum_{i=0}^n(-1)^i \frac 1 {i!}. \end{eqnarray*}$$

Si $n\rightarrow \infty$, $p_n$ tend vers $1-e^{-1}$, ce qui vaut approximativement $0.632.$