Formule du crible/Démonstration de la formule du crible

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Début d’un théorème

Théorème

Soient n ensembles A₁, A₂, … , A_n (non nécessairement disjoints). Pour tout ensemble d'indices $I\subset \{1,\dots ,n\}$, notons $A_{I}$ l'intersection correspondant à ces indices :

$A_{I}:=\bigcap _{i\in I}A_{i}$.

Le cardinal de l'union des n ensembles est alors donné par :

$\operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)=\sum _{\varnothing \neq I\subset \{1,\dots ,n\}}(-1)^{\operatorname {card} (I)-1}\operatorname {card} \left(A_{I}\right)$.

Fin du théorème

Démonstration par récurrence sur n

Initialisation.

Dans le cas n = 1, nous avons :

$\operatorname {card} (A_{1})=\operatorname {card} (A_{1}),$

ce qui ne fait aucun doute.

Le cas n = 2 est la formule :

$\operatorname {card} (A_{1}\cup A_{2})=\operatorname {card} (A_{1})+\operatorname {card} (A_{2})-\operatorname {card} (A_{1}\cap A_{2})$,

qui est démontrée dans Introduction aux mathématiques/Rudiments de combinatoire.

Hérédité.

Soit n ≥ 2. Supposons la formule du crible vraie à l’ordre n et montrons qu'alors, elle est vraie à l’ordre n + 1. D'après le cas n = 2,

$\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)+\operatorname {card} (A_{n+1})-\operatorname {card} \left(\left(\bigcup _{i=1}^{n}A_{i}\right)\cap A_{n+1}\right)$.

L'intersection étant distributive par rapport à la réunion, on obtient :

$\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)+\operatorname {card} (A_{n+1})-\operatorname {card} \left(\bigcup _{i=1}^{n}\left(A_{i}\cap A_{n+1}\right)\right)$.

On peut alors appliquer l’hypothèse de récurrence sur le premier et le troisième terme du second membre.

${\begin{aligned}\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)&=\left(\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\right)+\operatorname {card} (A_{n+1})-\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(\bigcap _{i\in I}\left(A_{i}\cap A_{n+1}\right)\right)\\&=\left(\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\right)+\operatorname {card} (A_{n+1})+\sum _{k=1}^{n}(-1)^{k}\sum _{n+1\in J\subset \{1,\ldots ,n+1\} \atop \operatorname {card} (J)=k+1}\operatorname {card} \left(A_{J}\right).\end{aligned}}$

Faisons un glissement d’indice dans le dernier terme.

$\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\left(\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\right)+\operatorname {card} (A_{n+1})+\sum _{k=2}^{n+1}(-1)^{k-1}\sum _{n+1\in J\subset \{1,\ldots ,n+1\} \atop \operatorname {card} (J)=k}\operatorname {card} \left(A_{J}\right)$.

On remarque que si l’on fait k = 1 dans la dernière somme, on obtient card(A_n+1), qui est justement le deuxième terme du second membre. On peut donc écrire :

$\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\left(\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\right)+\sum _{k=1}^{n+1}(-1)^{k-1}\sum _{n+1\in J\subset \{1,\ldots ,n+1\} \atop \operatorname {card} (J)=k}\operatorname {card} \left(A_{J}\right)$.

Nous remarquons que le premier terme de la somme contient toutes les intersections des A_i où ne figure pas A_n+1 et le deuxième terme de la somme contient toutes les intersections des A_i où figure A_n+1. Nous pouvons donc réunir ces deux sommes en une seule de la manière suivante :

$\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\sum _{k=1}^{n+1}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n+1\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)$,

ce qui nous montre que la formule du crible est vraie à l’ordre n + 1.

Conclusion.

On a bien :

$\forall n\in \mathbb {N} ^{*}\qquad \operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)$.

 

Démonstration à l'aide des fonctions indicatrices

La fonction (définie sur $A:=\cup A_{i}$)

$(1-\chi _{A_{1}})(1-\chi _{A_{2}})\cdots (1-\chi _{A_{n}})$

étant identiquement nulle, on en déduit, en développant ce produit :

$0=1+\sum _{\varnothing \neq I\subset \{1,\dots ,n\}}(-1)^{\operatorname {card} (I)}\chi _{A_{I}}$,

ou, de façon équivalente :

$\sum _{\varnothing \neq I\subset \{1,\dots ,n\}}(-1)^{\operatorname {card} (I)-1}\chi _{A_{I}}=1$.

On conclut en faisant, de part et d'autre de cette égalité de fonctions, la somme des valeurs quand la variable parcourt $A$.

 

Remarque

L'énoncé du théorème reste valide pour n = 0, puisqu'une union indexée par ∅ est vide et qu'une somme indexée par ∅ est nulle.