Principe d'inclusion-exclusion

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.