Le principe d’inclusion-exclusion est une formule de combinatoire qui permet de calculer le cardinal d’une réunion d’ensembles finis sans compter deux fois les éléments communs. Attribué au mathématicien Abraham de Moivre et aussi connu sous le nom de formule du crible de Poincaré, ce principe intervient chaque fois qu’on dénombre des éléments appartenant à plusieurs catégories qui se chevauchent. Mesurer ce que chaque ensemble apporte, puis corriger les doublons : voilà le mécanisme à comprendre.
Pourquoi le comptage direct échoue quand les ensembles se chevauchent
Considérons deux ensembles A et B qui partagent des éléments. Additionner leurs cardinaux revient à compter chaque élément de l’intersection exactement deux fois. Le principe d’inclusion-exclusion corrige cette erreur en soustrayant le cardinal de l’intersection.
A lire en complément : Chatgpt est-il bon en traduction ?
Le tableau ci-dessous compare le résultat d’une somme brute et celui obtenu après application de la formule, sur un exemple concret tiré du contexte classique : parmi un groupe d’étudiants, certains étudient les mathématiques, d’autres l’informatique, et une partie étudie les deux.
| Méthode | Opération | Résultat | Erreur |
|---|---|---|---|
| Somme brute |A| + |B| | 10 + 12 | 22 | Les étudiants dans A et B sont comptés deux fois |
| Inclusion-exclusion |A| + |B| – |A inter B| | 10 + 12 – 5 | 17 | Aucune : chaque étudiant est compté une seule fois |
L’écart entre les deux résultats correspond exactement au cardinal de l’intersection. Sans la correction, le sur-comptage est égal au nombre d’éléments partagés.
A lire également : Pourquoi l'hydrogène n'est pas une source d'énergie ?
Formule d’inclusion-exclusion pour deux et trois ensembles
Pour deux ensembles, la formule reste courte : |A union B| = |A| + |B| – |A inter B|. Elle se lit comme une addition corrigée d’un seul terme.
Avec trois ensembles A, B et C, le raisonnement se prolonge. Après avoir additionné les trois cardinaux, on a compté plus d’une fois les éléments situés dans deux ensembles à la fois. On retranche donc les trois intersections deux à deux. Ce faisant, les éléments présents dans les trois ensembles simultanément ont été ajoutés trois fois puis retranchés trois fois, ce qui les exclut totalement du décompte. Il faut les rajouter une dernière fois.
La formule complète pour trois ensembles devient :
|A union B union C| = |A| + |B| + |C| – |A inter B| – |A inter C| – |B inter C| + |A inter B inter C|
Le signe alterne à chaque niveau d’intersection : on ajoute les cardinaux individuels, on soustrait les intersections de paires, on ajoute l’intersection triple. Ce schéma d’alternance se généralise à un nombre quelconque d’ensembles.
Généralisation à n ensembles
Pour n ensembles, la formule additionne les cardinaux individuels, soustrait toutes les intersections de deux ensembles, ajoute toutes les intersections de trois ensembles, et ainsi de suite en alternant le signe. Le dernier terme, l’intersection de tous les ensembles, porte un signe positif si n est impair, négatif si n est pair.
- Les termes d’ordre impair (cardinaux individuels, intersections triples, etc.) sont additionnés.
- Les termes d’ordre pair (intersections de paires, intersections quadruples, etc.) sont soustraits.
- Le nombre total de termes dans la somme croît rapidement : pour n ensembles, on manipule 2^n – 1 termes.
Exemple complet avec trois ensembles en combinatoire
Prenons un groupe de vingt étudiants inscrits dans au moins une des trois matières suivantes : mathématiques (A), informatique (B) et physique (C). On sait que A contient dix étudiants, B en contient douze et C en contient huit. Les intersections sont les suivantes : A inter B compte cinq étudiants, A inter C en compte trois, B inter C en compte quatre, et A inter B inter C en compte deux.
Application directe de la formule :
|A union B union C| = 10 + 12 + 8 – 5 – 3 – 4 + 2 = 20 étudiants au total
Ce résultat confirme qu’aucun étudiant n’a été oublié ni compté en double. Chaque étape de soustraction puis d’addition corrige précisément le sur-comptage introduit par l’étape précédente.
Lecture graphique avec un diagramme de Venn
Un diagramme de Venn à trois cercles rend le mécanisme visible. Chaque zone du diagramme correspond à un sous-ensemble d’étudiants :
- La zone centrale (intersection des trois cercles) contient les deux étudiants inscrits partout.
- Les zones de chevauchement entre deux cercles seulement contiennent les étudiants inscrits dans exactement deux matières, après retrait de ceux déjà comptés au centre.
- Les zones périphériques de chaque cercle contiennent les étudiants inscrits dans une seule matière.
Le diagramme de Venn décompose visuellement chaque terme de la formule. C’est pour cette raison qu’il accompagne presque toujours la présentation du principe d’inclusion-exclusion dans les manuels de combinatoire.
Application du principe d’inclusion-exclusion en probabilités
Le principe ne se limite pas au dénombrement d’ensembles finis. Il se transpose directement aux probabilités : la probabilité de la réunion de deux événements A et B vaut P(A) + P(B) – P(A inter B). La structure est identique, seuls les cardinaux sont remplacés par des probabilités.
Les plateformes de formation en ligne présentent désormais ce principe comme un outil fondamental en probabilités et en data science, ce qui reflète une tendance à l’enseigner plus tôt et de manière plus appliquée. Calculer la probabilité qu’au moins un événement se produise parmi plusieurs événements non mutuellement exclusifs requiert exactement cette formule.
En revanche, lorsque les événements sont mutuellement exclusifs (aucune intersection), la formule se réduit à une simple somme de probabilités. L’inclusion-exclusion n’apporte de correction que lorsque les ensembles ou événements se chevauchent.
Erreurs fréquentes lors de l’application de la formule du crible
La première source d’erreur consiste à oublier un niveau d’intersection. Avec trois ensembles, omettre le terme |A inter B inter C| fausse le résultat final. Plus le nombre d’ensembles augmente, plus le risque d’omission grandit.
La seconde erreur porte sur le signe. Inverser un signe dans la somme alternée produit un décalage qui se propage à tous les termes suivants. Vérifier systématiquement que les intersections de rang pair sont soustraites et celles de rang impair sont ajoutées évite ce piège.
Le principe d’inclusion-exclusion reste la méthode de référence en combinatoire dès que des ensembles partagent des éléments. Sa transposition aux probabilités en fait un outil à double usage, mobilisé aussi bien dans un exercice de dénombrement que dans un calcul de risque appliqué.
