La formule du crible est une formule intéressante en dénombrement et probabilités. Dans cet article nous allons vous l’énoncer et la démontrer. On appelle aussi cette formule, formule de Poincaré.
Enoncé de la formule du crible
Dans le cas où n=2, c’est assez simple et connu : “Pour avoir le cardinal de l’union, on compte ce qu’il y a dans chaque ensemble et on retranche ce qu’on a compté 2 fois, c’est à dire l’intersection’
\text{card}(A \cup B) = \text{card}(A ) +\text{card}(B) +\text{card}(A \cap B) Voici la formule du crible sous sa forme la plus générale :
\text{card}\left( \bigcup_{i=1}^n A_i\right) = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n} \text{card} \left(\bigcap_{j=1}^k A_{i_j} \right)Avec une version probabiliste :
\mathbb{P}\left( \bigcup_{i=1}^n A_i\right) = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n} \mathbb{P} \left(\bigcap_{j=1}^k A_{i_j} \right)Bien sûr, on retrouve le fait que si les A_i forment une partition de E, alors on a :
\text{card}(E) = \sum_{i=1}^n A_i Démonstration de la formule du crible
Avec des fonctions indicatrices
Si vous n’êtes pas au point sur les fonctions indicatrices, allez d’abord voir notre article dédié !
On pose A = \bigcup A_i . La fonction définie sur A par \displaystyle est identiquement nulle sur A. Si on la développe, on obtient :
1 + \sum_{I \subset \{1,\ldots, n\}}(-1)^{\text{card}(I)}1_{A_I}Ce qui fait qu’on obtient en réécrivant :
1 = \sum_{I \subset \{1,\ldots, n\}}(-1)^{\text{card}(I)-1}1_{A_I}On peut ensuite passer au cardinal en sommant sur chacun des éléments de A pour obtenir la formule recherchée.
Démonstration par récurrence
Voici une démonstration plus classique : on peut démontrer la formule du crible par récurrence
Initialisation : Pour le cas n = 1, l’égalité s’écrit \text{card}(A_1) =\text{card}(A_1)
Hérédité : Soit n \in \mathbb{N}. On suppose que la propriété est vraie pour tout ensemble au rang n. Pour des facilités d’écritures, définissons \displaystyle B = \bigcup_{i=1}^n A_i
On a, en utilisant la formule au rang 2 :
\begin{array}{ll}
\text{card} \displaystyle \left( \bigcup_{i=1}^{n+1} A_i \right) &= \text{card} \displaystyle \left( B \cup A_{n+1}\right) \\
& = \text{card} \displaystyle \left( B\right)+\text{card} \displaystyle \left( A_{n+1}\right)-\text{card} \displaystyle \left( B \cap A_{n+1}\right)
\end{array}Appliquons ensuite l’hypothèse de récurrence
\begin{array}{ll}
\text{card} \displaystyle \left( \bigcup_{i=1}^{n+1} A_i \right) &=\displaystyle \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n} \text{card} \left(\bigcap_{j=1}^k A_{i_j} \right)+\text{card} \left( A_{n+1}\right)\\
& \displaystyle -\displaystyle \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n} \text{card} \left(\bigcap_{j=1}^k A_{i_j} \cap A_{n+1}\right)\\
&=\displaystyle \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n} \text{card} \left(\bigcap_{j=1}^k A_{i_j} \right)+\text{card} \left( A_{n+1}\right)\\
&\displaystyle -\displaystyle \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n, i_{k+1}=n+1} \text{card} \left(\bigcap_{j=1}^{k+1} A_{i_j} \right)\\
\end{array}On fait ensuite un petit changement d’indice dans la seconde somme, ce qui nous permet de transformer le – en + :
\begin{array}{ll}
\text{card} \displaystyle \left( \bigcup_{i=1}^{n+1} A_i \right) &=\displaystyle \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n} \text{card} \left(\bigcap_{j=1}^k A_{i_j} \right)+\text{card} \left( A_{n+1}\right)\\
&\displaystyle +\displaystyle \sum_{k=2}^{n+1} (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_{k-1} \leq n, i_{k}=n+1} \text{card} \left(\bigcap_{j=1}^{k+1} A_{i_j} \right)\\
\end{array}Remarquons ensuite que k = 1 correspond au terme \text{card} \left( A_{n+1}\right)
\begin{array}{ll}
\text{card} \displaystyle \left( \bigcup_{i=1}^{n+1} A_i \right) &=\displaystyle \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n} \text{card} \left(\bigcap_{j=1}^k A_{i_j} \right)\\
&\displaystyle +\displaystyle \sum_{k=1}^{n+1} (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_{k-1} \leq n, i_{k}=n+1} \text{card} \left(\bigcap_{j=1}^{k+1} A_{i_j} \right)\\
\end{array}Et maintenant on peut conclure en remarquant que la première somme inclut tous les termes ne contenant pas A_{n+1} et que la seconde contient tous les termes contenant A_{n+1} :
\text{card} \left( \bigcup_{i=1}^{n+1} A_i \right) =\sum_{k=1}^{n+1} (-1)^{k-1} \sum_{1 \leq i_1 \leq \ldots \leq i_k \leq n+1} \text{card} \left(\bigcap_{j=1}^k A_{i_j} \right)
\displaystyle L’hérédité est donc terminée ce qui conclut la récurrence
