Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Principe d'inclusion-exclusion
Résumé
thumb|Exemple d'inclusion-exclusion à partir de trois ensembles.
En combinatoire, le principe d’inclusion-exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d'une réunion finie d'ensembles finis en fonction du nombre d'éléments de ces ensembles et de leurs intersections. Il se généralise en termes de probabilités.
Il est attribué au mathématicien Abraham de Moivre, et connu également (lui ou sa version probabiliste) sous le nom de formule du crible de Poincaré, formule de Poincaré, ou formule du crible.
Parmi 20 étudiants, 10 étudient les mathématiques, 11 étudient la physique, et 4 étudient les deux. Combien y a-t-il d’étudiants qui n’étudient ni les mathématiques ni la physique ?
La construction d'un diagramme de Venn permet de visualiser simplement la répartition générale des étudiants.
center
Une zone de couleur représente un groupe. E représente le groupe entier d’étudiants, M représente ceux qui ont la propriété d'« étudier les mathématiques », P représente ceux qui possèdent la propriété d'« étudier la physique ».
On note ensuite pour chaque zone le nombre d’étudiants. Étant donné que quatre personnes étudient à la fois les mathématiques et la physique, l’intersection des deux cercles compte 4 étudiants. Il reste donc 10 – 4 = 6 personnes qui étudient les mathématiques mais pas la physique et 11 – 4 = 7 personnes qui étudient la physique mais pas les mathématiques. Par suite, il reste donc 20 – (6 + 4 + 7) = 3 personnes qui n’étudient ni les mathématiques, ni la physique.
Ce résultat se retrouve facilement en utilisant le principe d’inclusion-exclusion qui donne le nombre d’étudiants ne possédant pas ces deux propriétés : 20 – 10 – 11 + 4 = 3.
Soient A et B deux ensembles finis, la formule s'écrit
où |A| et |B| représentent les cardinaux respectifs de A et B.
En d’autres termes, nous pouvons compter les éléments de la réunion de deux ensembles A et B en additionnant les cardinaux de ces deux ensembles et en soustrayant le cardinal de leur intersection.
Soient A1, ..., An n ensembles finis.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.