Principe van inclusie en exclusie

De vereniging en doorsnede van de twee verzamelingen $A$ en $B$

In de combinatoriek (combinatorische wiskunde), de getaltheorie en de stochastiek, is het principe van inclusie en exclusie (ook principe van insluiting en uitsluiting) een teltechniek om het aantal elementen in de vereniging van meerdere eindige verzamelingen te bepalen.

Het principe is een generalisatie van de bekende methode om het aantal elementen in de vereniging van twee eindige verzamelingen $A$ en $B$ te bepalen. Daarvoor geldt:

$|A\cup B|=|A|+|B|-|A\cap B|,$

waarin $|S|$ het aantal elementen van de eindige verzameling $S$ aangeeft. De formule toont aan dat de som van de aantallen elementen van beide verzamelingen mogelijk te groot is, doordat de gemeenschappelijke elementen tweemaal geteld worden. De dubbelgetelde elementen zijn die in de doorsnede van de twee verzamelingen en de telling wordt gecorrigeerd door de grootte van de doorsnede van het resultaat af te trekken.

Het principe is gemakkelijker te begrijpen in het geval van drie verzamelingen. Het principe wordt voor de verzamelingen $A,B$ en $C$ gegeven door

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.$

Principe van insluiting en uitsluiting geïllustreerd aan de hand van een venndiagram voor drie verzamelingen

Deze formule kan worden geverifieerd door te tellen hoe vaak elke regio in het plaatje van het venndiagram hiernaast wordt meegeteld aan de rechterzijde van deze formule. Merk op dat als het aantal elementen in de paarsgewijze doorsneden van de drie verzamelingen (respectievelijk van $A$ en $B,$ van $A$ en $C,$ en van $B$ en $C$) afgetrokken wordt van de kardinaliteiten van $A,B$ en $C$ te veel wordt afgetrokken. De drievoudige doorsnede van alle drie de verzamelingen $A,B$ en $C$ moet er weer bij opgeteld worden om het juiste resultaat te krijgen.

Het generaliseren van de resultaten van deze voorbeelden geeft het principe van insluiting en uitsluiting. Ga als volgt te werk om de kardinaliteit van de vereniging van $n$ verzamelingen te vinden:

1. Sluit de kardinaliteiten van de verzamelingen in.
2. Sluit de kardinaliteiten van de paarsgewijze doorsneden uit.
3. Sluit de kardinaliteiten van de tripelgewijze doorsneden in.
4. Sluit de kardinaliteiten van de viervoudige doorsneden uit.
5. Sluit de kardinaliteiten van de vijfvoudige doorsneden in.
6. Ga door totdat de kardinaliteit van de $n$-tupelgewijze doorsneden is ingesloten (als $n$ oneven is) of is uitgesloten (als $n$ even is).

Zie ook

Somregel (kansrekening)