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 nAB.

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)  = nA + nB - nAB

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

       
Als je begint met n(A ∪ B C) = nA + nB + nC  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) = nA + nB + nC  - nAB - nBC - nAC
Maar dan zit je nog met dat stukje in het midden (figuur rechts). Dat heb je eerst drie keer meegeteld  (in nA en nB en nC)  en toen er weer drie keer afgetrokken (in nAB en nBC en nAC). Kortom: netto is het nog niet meegeteld!
Dat moet er dus nog weer bij.
Samen geeft dat:
       

n(A ∪ B ∪ C)  = nA + nB + nC - nAB - nBC - nAC + nABC

       
Met vier eigenschappen A, B, C, D gaat het z:
       
  1. begin met  nA + nB + nC + nD  
  2. doorsnedes dubbel geteld moeten er weer af:  - nAB - nAC - nAD - nBC - nBD - nCD
  3. wat is er nu met de doorsnedes van drie verzamelingen (bijvoorbeeld nABC) 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:   +nABC + nABD + nBCD + nACD
  4. 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:    -nABCD.
       
samengenomen:   n(A B C D) =
n
A + nB + nC + nD - nAB - nAC - nAD - nBC - nBD - nCD+ nABC + nABD + nBCD + nACD - nABCD.
       
Het algemene geval dan maar.

Neem een aantal eigenschappen  A1A2A3...Am, dan geldt:
       
n(A1  A2  A3  ...  ∪ Am) =
  + nA1 + nA2 + nA3 + ...
   - nA12 - nA13 - ....
  +
nA123 + nA124 + ...
   - nA1234 - nA1235 - ...
   ....
   +
(-1)m-1 A123..m    
       
Bewijs.
       
Neem n stukje van het Venn-diagram dat x eigenschappen wl 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:
 
 
 
  .....
.....
 
    daarna niet meer.
       
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 -0x.
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 wl deelbaar zijn door 2,3 of 5:
n2 = 500 en  n3 = 333  en  n5 = 200
n23 = 166 (deelbaar door 6)  en  n25 = 100  (deelbaar door 10)  en  n35 = 66  (deelbaar door 15)
n235 = 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 Ai de gebeurtenis is dat brief nummer i in de juiste enveloppe zit. Dan is n(Ai) = (n - 1)! immers je kunt de andere n - 1 brieven nog willekeurig verdelen.

En dan is  n(Ai ∩ Aj) = (n - 2)!   en er zijn  (n nCr 2) zulke paren
En  n(Ai ∩ Aj  ∩ Ak) = (n - 3)!   en er zijn (n nCr 3) zulke drietallen


Ons inclusie-exclusie principe geeft dan het volgende aantal n0  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  n0 = 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  1/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 aks 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.

100/2 = 50 dus er zijn 50 tweevouden onder de 100.
100/3 = 33,333 dus er zijn 33 drievouden onder de 100.    Dat wordt meestal genoteerd als  100/3 = 33
100/5 = 20 dus er zijn 20 vijfvouden onder de 100
 100/7 = 14 dus er zijn 14 zevenvouden onder de 100

En daar gaat 'ie weer:  nu zijn de 23 , 25, 27, 35, 37, 57 -vouden dubbel meegeteld.
Een daarna zijn de  235, 237, 257, 357-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 - {100/2 + 100/3 + 100/5 + 100/7} + {100/23 + 100/25 + 100/27 + 100/35 + 100/37 + 100/57}
      
- {100/235 + 100/237 + 100/357 + 100/257}  + {100/2357}

= 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/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 - 1/p1) (1 - 1/p2) (1 - 1/p3) ... (1 - 1/px)}

Neem bijvoorbeeld 36.  Dat heeft priemfactoren 2 en 3,   dus 
j(36) = 36 1/2 2/3 = 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)

 
     

h.hofstede (h.hofstede@hogeland.nl)