principe van exclusie inclusie


Exclusie/Inclusie.	© h.hofstede (h.hofstede@hogeland.nl)

Je moet eigenlijk wel weten wat Venn-diagrammen voordat je deze les gaat volgen.
Dat kun je in deze les leren.

OK, je weet het???

Laten we dan bij een klas van totaal 30 leerlingen naar 2 verschillende eigenschappen kijken.
Bijvoorbeeld de eigenschappen: "meisje" (A) en de eigenschap "blond" (B) .

Dat levert het Venn-diagram hiernaast op. Je ziet dat er 10 meisjes in de klas zitten en dat er 14 leerlingen blond zijn, en dat er 4 blonde meisjes zijn.

Als je nu het aantal leerlingen dat aan BEIDE eigenschappen voldoet wilt berekenen dan zijn dat de leerlingen uit het blanco gebied hiernaast, dan kun je niet gewoon 14 + 10 doen, want dan tel je dat stukje daar in het midden twee keer.

Je berekent het blanco stuk met: 14 + 10 - 4 = 20. Daarbij is die laatste -4 dus omdat je dat middelste stuk niet twee keer moet tellen.

Een wetenschappelijke notatie

Vanaf nu noemen we n(A) = aantal dingen dat eigenschap A heeft. (die "dingen" noemen wiskundigen trouwens elementen). In bovenstaand voorbeeld is dus n(A) = 10 en n(B) = 14.

Ten tweede bestaat de doorsnede van twee verzamelingen A en B uit de elementen die in A én in B zitten. Dat noteren we als A ∩ B, en in bovenstaand voorbeeld is n(A ∩ B) = 4. Dat zijn die vier blonde meisjes.
In het vervolg zullen we dat uit luiheid trouwens ook noteren als n_AB.

Tenslotte noteren we A ∪ B als we bedoelen de "vereniging" van de verzamelingen A en B. Dat wil zeggen; alle elementen die in A óf in B zitten, óf in allebei. In bovenstaand voorbeeld is dus n(A ∪ B) = 20 (dat blanco stuk)

In een plaatje ziet het er allemaal zó uit:

En nu: Tellen maar.......!

In het voorbeeld berekenden we het aantal elementen uit de vereniging van A en B door die van A en bij B elkaar op te tellen en daarna de dubbelen er weer af te trekken. Dat gaf 14 + 10 - 4 = 20
Met de nieuwe notatie ziet dat er zó uit:

n(A ∪ B) = n(A) + n(B) - n(A ∩ B)
of ook wel:
n(A ∪ B) = n_A + n_B - n_AB

Laten we snel uitbreiden naar drie eigenschappen A, B en C.

Als je begint met n(A ∪ B ∪ C) = n_A + n_B + n_C in de figuur links, dan heb je de doorsnedes van die drie verzamelingen (figuur midden) dubbel geteld, dus die moeten er weer af: n(A ∪ B ∪ C) = n_A + n_B + n_C - n_AB - n_BC - n_ACMaar dan zit je nog met dat stukje in het midden (figuur rechts). Dat heb je eerst drie keer meegeteld (in n_A en n_B en n_C) en toen er weer drie keer afgetrokken (in n_AB en n_BC en n_AC). Kortom: netto is het nog niet meegeteld!
Dat moet er dus nog weer bij.
Samen geeft dat:

n(A ∪ B ∪ C) = n_A + n_B + n_C - n_AB- n_BC - n_AC + n_ABC

Met vier eigenschappen A, B, C, D gaat het zó:

begin met n_A + n_B + n_C + n_D

doorsnedes dubbel geteld moeten er weer af: - n_AB - n_AC - n_AD - n_BC - n_BD - n_CD

wat is er nu met de doorsnedes van drie verzamelingen (bijvoorbeeld n_ABC) gebeurd?
die is eerst drie keer meegeteld (in stap 1)
die is er vervolgens drie keer van afgetrokken (in stap 2).
kortom: die moet nog meegeteld worden: +n_ABC + n_ABD + n_BCD + n_ACD

wat is er nu met de doorsnede van alle vier de verzamelingen gebeurd?
die is eerst vier keer meegeteld (in stap 1)
die is er vervolgens 6 keer vanaf getrokken (in stap 2)
die is er toen weer 4 keer bijgeteld (in stap 3)
in totaal is die tot nu toe dus 2 keer geteld, dus die moet er nog 1 keer vanaf: -n_ABCD.

samengenomen: n(A ∪ B ∪ C ∪ D) =
n_A + n_B + n_C + n_D- n_AB - n_AC - n_AD - n_BC - n_BD - n_CD+ n_ABC + n_ABD + n_BCD + n_ACD- n_ABCD.

Het algemene geval dan maar.

Neem een aantal eigenschappen A₁A₂A₃...A_m, dan geldt:

n(A₁ ∪ A₂ ∪ A₃ ∪ ... ∪ A_m) =
+ nA₁ + nA₂ + nA₃ + ...
   - nA₁₂ - nA₁₃ - ....
+ nA₁₂₃ + nA₁₂₄ + ...
   - nA₁₂₃₄ - nA₁₂₃₅ - ...
   ....
   +(-1)^m-1A_123.._m

Bewijs.

Neem één stukje van het Venn-diagram dat x eigenschappen wél heeft en dus m - x eigenschappen niet. (dus niet een combinatie van gebiedjes, maar precies één afgesloten stukje Venn-diagram)
Laten we tellen hoe vaak dat stukje wordt meegeteld:

Daar staan precies alle getallen van een rij van de driehoek van Pascal op een rijtje, om-en-om met een plusteken en een minteken. Alleen de eerste die mist, en dat zou -1 zijn.
Dat betekent (als je die eerste -1 toevoegt) dat je precies hetzelfde zou krijgen als je de haakjes zou wegwerken in
-{(1) + (-1)}^x en dat is natuurlijk 0, want daar staat gewoon -0^x.
Kortom, als je -1 aan bovenstaande rij toevoegt dan komt er 0 uit, dus die rij is gelijk aan 1.
Dat betekent dat elk stukje van het Venn-diagram inderdaad precies 1 keer wordt meegeteld.

q.e.d.

Voorbeeld.

Hoeveel getallen vanaf 1 tot en met 1000 zijn niet deelbaar door 2, 3 en 5?

Oplossing:
Kijk hoeveel er wél deelbaar zijn door 2,3 of 5:
n₂ = 500 en n₃ = 333 en n₅ = 200
n₂₃ = 166 (deelbaar door 6) en n₂₅ = 100 (deelbaar door 10) en n₃₅ = 66 (deelbaar door 15)
n₂₃₅ = 33 (deelbaar door 30).
Dus wel deelbaar zijn er 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734
Dus niet deelbaar zijn er 1000 - 734 = 266.

Een aardige toepassing....

Een groep van n mensen zit in een lange rij van n stoelen.
De opdracht aan deze groep is: "Ga allemaal in een andere stoel zitten"
Op hoeveel manieren kan dat gebeuren????

n = 5
Laten we het geval (om een beetje gevoel voor het probleem te krijgen) eens voor 5 mensen bekijken. Dus n = 5.
Zonder voorwaarden zijn er 5! = 120 manieren om die mensen in een rij te zetten.

Maar 4! = 24 daarvan hebben de eerste persoon op dezelfde plaats. En ook 24 de tweede persoon en ook 24 de derde .... Dus van die 120 moet je 5 • 24 aftrekken, en dan blijft er NUL over!!!!!!
HUH?

Je snapt hopelijk nu dat we weer dubbel hebben geteld.
De gevallen waarin 1 EN 2 in dezelfde stoel zitten zijn dubbel geteld. Die zijn er twee keer afgetrokken en dat moet niet. Hetzelfde geldt voor alle andere koppels. Dat zijn 5 nCr 2 = 10 dubbel getelde setjes.
Die moeten er dus weer bij. Als 1 EN 2 in dezelfde stoel zitten zijn er nog 3! = 6 manieren voor de andere drie.
Daarmee wordt het aantal nu 120 - 5 • 24 + 10 • 6

Maar ja.... Nu moet daar weer vanaf het aantal manieren waarbij DRIE mensen in dezelfde stoel zitten......

Steeds zo doorredeneren geeft uiteindelijk 120 - 5 • 24 + 10 • 6 - 10 • 2 + 5 • 1 - 1 • 1 = 44 manieren.

Wacht.... dat kan wiskundiger.......

Mooi toch?
En als je de 5 door een n vervangt heb je een nog mooiere algemene formule voor n personen.

De aap met de brieven.

Stel dat je n brieven hebt geschreven, en ook al n enveloppen hebt geadresseerd om ze in te stoppen.

Op dat moment moet je even naar het toilet, dus je verlaat de kamer. Een aap komt binnen en stopt elke brief willekeurig in een enveloppe (de aap kan helaas niet lezen)
Op hoeveel manieren kan de aap dat doen als er geen enkele brief in de juiste enveloppe zit?

Stel dat A_i de gebeurtenis is dat brief nummer i in de juiste enveloppe zit. Dan is n(A_i) = (n - 1)! immers je kunt de andere n - 1 brieven nog willekeurig verdelen.

En dan is n(A_i ∩ A_j) = (n - 2)! en er zijn (n nCr 2) zulke paren
En n(A_i ∩ A_j ∩ A_k) = (n - 3)! en er zijn (n nCr 3) zulke drietallen

Ons inclusie-exclusie principe geeft dan het volgende aantal n₀ voor nul goed:

Maar wat is dat nou? Daar tussen haakjes staat de reeksontwikkeling voor e^-1 .
Dat betekent dat als n maar groot genoeg wordt, ongeveer geldt n₀ = n! • e^-1
De kans dat zoiets gebeurt is gelijk aan dit aantal gedeeld door het totaal aantal mogelijkheden (n!)
Die kans is dus gelijk aan ¹/_e = 0,36787944...

En ja! Dit is niet zomaar een raar verhaal over apen en brieven. We komen dit elke keer ook tegen als we lootjes gaan trekken met een groep van n mensen. Immers, als niemand zichzelf mag trekken, dan moet elk lootje bij een verkeerd persoon komen.

Hoeveel priemgetallen?

Stel; dat we willen weten hoeveel priemgetallen er onder de 100 zijn (oké het zijn er 25, maar dat weten we nog niet).
Dan kun je dat makkelijk berekenen als je weet hoeveel priemgetallen er onder de 10 zijn.
Dat zijn natuurlijk 2, 3, 5, 7 dus dat zijn er 4.

Maar nou komt het idee: alle getallen die NIET één van deze vier in hun priemfactor ontbinding hebben zitten zijn priemgetal! Immers als een getal NIET deelbaar door 2, 3, 5, 7 is, dan is het ook niet deelbaar door een ander getal onder de 100, want de uitkomst van die deling zou onder de 10 moeten liggen (100 = 10 • 10 dus als een getal als a • b geschreven kan worden en a > 10 dan moet wel b < 10)
Kortom: als we alle veelvouden van 2, 3, 5, 7 onder de 100 wegstrepen, dan houden we vanzelf de priemgetallen over.

¹⁰⁰/₂ = 50 dus er zijn 50 tweevouden onder de 100.
¹⁰⁰/₃ = 33,333 dus er zijn 33 drievouden onder de 100. Dat wordt meestal genoteerd als ë¹⁰⁰/₃û = 33
100/5 = 20 dus er zijn 20 vijfvouden onder de 100
ë¹⁰⁰/₇û = 14 dus er zijn 14 zevenvouden onder de 100

En daar gaat 'ie weer: nu zijn de 2•3 , 2•5, 2•7, 3•5, 3•7, 5•7 -vouden dubbel meegeteld.
Een daarna zijn de 2•3•5, 2•3•7, 2•5•7, 3•5•7-vouden weer dubbel geteld

Voel je het al?
Inclusie en Exclusie!!

Het aantal getallen onder de 100 dat GEEN veelvoud van 2, 3, 5, 7 onder de 100 is gelijk aan:

100 - {ë¹⁰⁰/₂û + ë¹⁰⁰/₃û + ë¹⁰⁰/₅û + ë¹⁰⁰/₇û} + {ë¹⁰⁰/₂_•3û + ë¹⁰⁰/₂_•5û + ë¹⁰⁰/₂_•7û + ë¹⁰⁰/₃_•5û + ë¹⁰⁰/₃_•7û + ë¹⁰⁰/₅_•7û}
- {ë¹⁰⁰/₂_•3•5û + ë¹⁰⁰/₂_•3•7û + ë¹⁰⁰/₃_•5•7û + ë¹⁰⁰/₂_•5•7û} + {ë¹⁰⁰/₂_•3•5•7û}

= 100 - {50 + 33 + 20 + 14} + {16 + 10 + 7 + 6 + 4 + 2} - {3 + 2 + 0 + 1} + {0}
= 100 - 117 + 45 - 6 + 0
= 22

Er zijn dus 22 getallen onder de 100 die GEEN veelvoud van 2, 3, 5, 7 zijn
Maar nu is 1 ook meegeteld en dat is geen priemgetal. En verder zijn 2, 3, 5, 7 NIET meegeteld terwijl dat wel priemgetallen zijn.
Dus we houden 22 - 1 + 4 = 25 priemgetallen onder de 100 over.

Het lijkt misschien nogal omslachtig op deze manier, en misschien kun je sneller gewoon alle getallen onder de 100 langslopen en kijken of het priemgetallen zijn. Maar stel je voor dat je wilt weten hoeveel priemgetallen er onder 1000000 zijn! Dan is dat nogal een werk. Met deze inclusie-exclusie methode kun je dat doen als je de priemgetallen onder de 1000 hebt.

Een speciaal geval hiervan krijg je als je voor een getal N niet alle priemgetallen onder N neemt, maar alleen de priemfactoren van N zelf. Dan bereken je op deze manier dus hoeveel getallen er kleiner dan N zijn die GEEN priemfactor met N gemeenschappelijk hebben. Dat wordt ook wel de Euler-totient functie j(N) genoemd.

Dat geeft (je kunt de ëû weglaten want omdat de p's priemfactoren van N zijn komt er altijd een geheel getal uit)

j(N) =

N
- {^N/_p1 + ^N/_p2 + ^N/_p3 + ....}

+ {^N/_p1p2 + ^N/_p2p3 + ....}

- {^N/_p1p2p3 + ^N/_p1p2p4 + ....}
....
+ (-1)^x ^N/_p1p2p3...px

Haal de N buiten haakjes, dan krijg je precies dit:
j(N) = N • {1 - ¹/_p1) • (1 - ¹/_p2) • (1 - ¹/_p3) • ... • (1 -¹/_px)}

Neem bijvoorbeeld 36. Dat heeft priemfactoren 2 en 3, dus j(36) = 36 • ¹/₂ • ²/₃ = 12
Er zijn dus 12 getallen onder de 36 die geen priemfactor met 36 gemeenschappelijk hebben.
(klopt, kijk maar; het zijn 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35)