Ê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 GraphSearch.
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.
Concepts associés (14)
Théorie des cribles
En mathématiques, la théorie des cribles est une partie de la théorie des nombres ayant pour but d'estimer, à défaut de dénombrer, les cardinaux de sous-ensembles (éventuellement infinis) de N en approchant la fonction indicatrice du sous-ensemble considéré. Cette technique a pour origine le crible d'Ératosthène, et dans ce cas, le but était d'étudier l'ensemble des nombres premiers. Un des nombreux résultats que l'on doit aux cribles a été découvert par Viggo Brun en 1919.
Stirling numbers of the second kind
In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling. The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices.
Multiensemble
Un multiensemble (parfois appelé sac, de l'anglais bag utilisé comme synonyme de multiset) est une sorte d'ensemble dans lequel chaque élément peut apparaître plusieurs fois. C'est une généralisation de la notion d'ensemble : un ensemble ordinaire est un multiensemble dans lequel chaque élément apparaît au plus une seule fois ; ce qu'impose, pour les ensembles usuels, l'axiome d'extensionnalité. On nomme multiplicité d'un élément donné le nombre de fois où il apparaît.
Cours associés (2)
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
MATH-502: Distribution and interpolation spaces
The aim of this course is to provide a solid foundation of theory of distributions, Sobolev spaces and an introduction to the more general theory of interpolation spaces.
Séances de cours associées (11)
Comptage avancé : Inclusion-Exclusion
Couvre le principe d'inclusion-exclusion pour les ensembles et introduit les dérangements.
Théorème binomial étendu
Explore le théorème binomial étendu et les problèmes de comptage en utilisant des fonctions de génération.
Compte et probabilités avancés
Couvre les techniques de comptage avancées, les probabilités, et leurs applications en informatique.