Probabilités et statistiquesNotion · Glossaire
Principe d'inclusion-exclusion
Le principe d'inclusion-exclusion, ou formule du crible de Poincaré, est une formule permettant de calculer le cardinal d'une union de plusieurs ensembles finis. Pour deux ensembles, il affirme que le cardinal de A union B est égal au cardinal de A plus le cardinal de B moins le cardinal de l'intersection de A et B. La formule se généralise à n ensembles en alternant additions et soustractions des cardinaux des intersections de sous-familles. Elle est utilisée en combinatoire et en probabilités.
Sommaire
Ce que vous allez apprendre
- Expliquer pourquoi les intersections doivent être alternativement soustraites et ajoutées.
- Calculer l'union de trois groupes d'élèves à partir de sept effectifs annoncés.
- Contrôler le résultat 36 par une somme de zones disjointes et retrouver les 4 élèves hors union.
- Distinguer intersections inclusives, zones exclusives et complémentaire.
- Repérer les erreurs de données et la limite du cadre fini présenté.
En clair
Dans une classe, 22 élèves suivent l'atelier de maths et 18 celui de programmation. Les additionner donne 40 inscriptions, mais pas forcément 40 élèves : ceux qui suivent les deux ateliers ont été comptés deux fois.
Le principe d'inclusion-exclusion corrige ces recouvrements. Il additionne d'abord les groupes, soustrait les intersections comptées en trop, puis les rajoute lorsque cette soustraction les a retirées trop souvent. Cette alternance donne le nombre de personnes appartenant à au moins un groupe.
Définition
Le principe d'inclusion-exclusion calcule le cardinal, c'est-à-dire le nombre d'éléments, de l'union d'ensembles finis. Si A et B sont deux ensembles, leur union rassemble les éléments appartenant à A, à B, ou aux deux. On a . L'intersection est soustraite une fois parce que l'addition l'avait comptée deux fois.
Pour trois ensembles A, B et C, il faut additionner leurs cardinaux, soustraire les trois intersections deux à deux, puis rajouter l'intersection triple. En effet, un élément commun aux trois ensembles est d'abord compté trois fois, puis retiré trois fois ; le dernier ajout lui rend son unique comptage.
Plus généralement, si A1, ..., An sont n ensembles finis, la somme porte sur toutes les intersections non vides de sous-familles :
Les intersections d'un nombre impair d'ensembles sont ajoutées ; celles d'un nombre pair sont soustraites. En probabilités, la même alternance s'applique aux probabilités d'événements et de leurs intersections.
Un exemple, pas à pas
Une classe de 40 élèves propose trois ateliers : maths, programmation et illustration. On compte 22 inscrits en maths, 18 en programmation et 15 en illustration. Les intersections comptent 9 élèves en maths et programmation, 7 en maths et illustration, 6 en programmation et illustration, dont 3 suivent les trois ateliers. Chaque intersection à deux inclut donc les 3 inscrits aux trois.
1. Additionnons les trois effectifs : 22 + 18 + 15 = 55 inscriptions comptées avec répétitions.
2. Soustrayons les intersections deux à deux : 55 − 9 − 7 − 6 = 33. Les trois élèves communs à tous les ateliers ont alors été retirés une fois de trop.
3. Rajoutons l'intersection triple : . Il y a donc 36 élèves inscrits à au moins un atelier. Le diagramme répartit exactement ces 36 élèves entre les sept zones.
4. Déduisons le complément : parmi les 40 élèves, 40 − 36 = 4 ne suivent aucun atelier.
5. Contrôlons par zones disjointes : 9 seulement en maths, 6 seulement en programmation, 5 seulement en illustration, puis 6, 4 et 3 dans exactement deux ateliers, et 3 dans les trois. La somme 9 + 6 + 5 + 6 + 4 + 3 + 3 vaut bien 36.
En pratique
En dénombrement, la formule est utile lorsque plusieurs critères peuvent être satisfaits simultanément. Si les catégories sont disjointes, une simple addition suffit ; dès qu'un objet peut appartenir à plusieurs catégories, il faut mesurer leurs intersections.
En probabilités, elle calcule la probabilité qu'au moins un événement se produise. Pour deux événements incompatibles, les probabilités s'additionnent directement ; si leur intersection est possible, sa probabilité doit être soustraite.
Pour compter des surjections vers un ensemble fini, on peut partir de toutes les fonctions et exclure celles qui omettent au moins une valeur d'arrivée. Le crible devient préférable à une liste manuelle lorsque plusieurs valeurs peuvent manquer ensemble.
À ne pas confondre
Principe additif pour des ensembles disjoints. Il additionne les cardinaux sans correction lorsque toutes les intersections sont vides. Dans l'exemple des ateliers, il ne s'appliquerait directement qu'aux sept zones exclusives, pas aux trois listes d'inscrits qui se recouvrent.
Passage au complémentaire. Compter les élèves sans atelier par 40 − 36 utilise le complément de l'union. L'inclusion-exclusion intervient auparavant pour obtenir 36, car connaître seulement les trois effectifs ne suffit pas quand les ateliers se recouvrent.
Limites et pièges
Oublier l'intersection triple. Avec trois ensembles, s'arrêter après les soustractions donne 33 au lieu de 36 dans l'exemple. Le symptôme est qu'un élément présent dans les trois groupes finit compté zéro fois ; il faut rajouter l'intersection triple.
Interpréter les intersections comme des zones exclusives. Les 9 élèves de l'intersection maths-programmation comprennent les 3 inscrits aux trois ateliers. Pour obtenir ceux qui suivent exactement ces deux ateliers, il faut calculer 9 − 3 = 6.
Employer la formule avec des données incohérentes. Une intersection ne peut pas dépasser le plus petit ensemble concerné. Si un relevé annonce 20 élèves dans l'intersection de groupes de 22 et 18, les données doivent être corrigées avant le calcul.
Oublier le domaine fini. La formule présentée ici porte sur un nombre fini d'ensembles finis. Pour une famille infinie ou des ensembles infinis, on ne transpose pas cette alternance de cardinaux telle quelle ; il faut choisir un cadre adapté au problème.
Pour aller plus loin
analyse combinatoire — Situer la formule du crible parmi les outils qui comptent des configurations finies.
surjection — Approfondir l'objet que le crible dénombre en excluant les fonctions qui omettent une valeur d'arrivée.
Les multiples facettes du dénombrement — Explorer d'autres stratégies pour organiser un comptage sans omissions ni doublons.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres