Principe van inclusie en exclusie

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
De vereniging en doorsnede van de twee verzamelingen en

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 en te bepalen. Daarvoor geldt:

waarin het aantal elementen van de eindige verzameling 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 en gegeven door

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 en van en en van en ) afgetrokken wordt van de kardinaliteiten van en te veel wordt afgetrokken. De drievoudige doorsnede van alle drie de verzamelingen en 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 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 -tupelgewijze doorsneden is ingesloten (als oneven is) of is uitgesloten (als even is).

Zie ook[bewerken]

Somregel (kansrekening)