Discrete Kansrekening/Symmetrische kansruimten/Combinatorische kansrekening

2.2 Combinatorische kansrekening

Veel problemen in de kansrekening kunnen worden opgelost door gebruik te maken van symmetrie, dus door de kansdefinitie van Laplace toe te passen. Het berekenen van kansen komt dan neer op het tellen van uitkomsten. Het zal duidelijk zijn dat de theorie van het tellen, de combinatoriek, een belangrijk hulpmiddel in de kansrekening is. In dit hoofdstuk zullen we een aantal belangrijke resultaten uit de combinatoriek herhalen en toepassen in de kansrekening.

Telkens blijkt goed tellen toch meer een kunst te zijn, dan op het eerste gezicht het geval lijkt. Een eerste moeilijkheid doet zich voor als er een of andere opsplitsing van het probleem is gebruikt en de vraag opduikt of we in dat het geval het totale aantal verkrijgen door optelling dan wel door vermenigvuldiging. Het antwoord luidt - uiteraard - dat het afhangt van de aard van de opsplitsing. De beide volgende stellingen geven hierover uitsluitsel.

Stelling 2.2.1 (speciale somregel)

Voor de vereniging van een collectie disjuncte verzamelingen A₁,A₂,...,A_n geldt: #(A₁∪A₂∪...∪A_n) = #A₁+#A₂+...+#A_n.

Als we het aantal elementen van elke A_i geteld hebben en de A_i's hebben onderling geen gemeenschappelijke elementen, dan hoeven we niet opnieuw te gaan tellen om het totale aantal elementen te bepalen, maar kunnen we gewoon de afzonderlijke aantallen bij elkaar optellen. We kunnen zeggen dat we moeten optellen als de verschillende mogelijkheden naast elkaar kunnen voorkomen, dus de een of de ander.

In de bovenstaande regel ligt een bron van veel fouten besloten. Er wordt nogal eens over het hoofd gezien dat geëist wordt dat de verzamelingen disjunct zijn. Is dat niet het geval, dan moeten we de algemene somregel gebruiken. Voor twee verzamelingen luidt die:

Stelling 2.2.2 (algemene somregel)

Voor een tweetal verzamelingen A en B geldt: #(A∪B) = #A + #B – #AB

Het totale aantal elementen in A en B verkrijgen we door de afzonderlijke aantallen bij elkaar optellen en te verminderen met het aantal gezamenlijke elementen; die gezamenlijke elementen zouden we anders dubbel tellen.

De algemene somregel kan, op analoge wijze als de overeenkomstige somregel voor kansen, op voor de hand liggende wijze worden uitgebreid naar meer dan twee verzamelingen. We geven alleen een voorbeeld.

Voorbeeld 1 (ONS DORP; vervolg)

In ONS DORP zijn drie toneelverenigingen, A met 42 leden, B met 30 leden en C met 57 leden. Hoeveel dorpsbewoners spelen toneel? Dat zijn er niet 30+42+57, want 10 dorpsbewoners zijn lid van A zowel als van B, 12 zijn lid van A zowel als van C, 9 van B zowel als van C en 8 zijn zelfs lid van alle drie toneelverenigingen. We vinden dus: #(A∪B∪C) = #A + #B + #C – #AB – #AC – #BC + #ABC = 106.

Voorbeeld 2

We werpen driemaal een zuivere dobbelsteen. Voor de uitkomstenruimte S geldt #S = 6³ = 216. Zij A de gebeurtenis dat we tenminste één keer zes gooien. Er geldt dat A = A₁∪ A₂∪ A₃, waarin A_i de gebeurtenis is dat de ie worp (i=1,2,3) een zes opleverde. Omdat de gebeurtenissen A₁, A₂ en A₃ geen disjunct drietal vormen, mogen we niet de speciale somregel toepassen op dit drietal. Wel kunnen we deze regel toepassen op een partitie van A. Daartoe delen we A op in disjuncte stukken:

$A=A_{1}A_{2}^{c}A_{3}^{c}\cup A_{1}^{c}A_{2}A_{3}^{c}\cup A_{1}^{c}A_{2}^{c}A_{3}\cup A_{1}A_{2}A_{3}^{c}\cup A_{1}A_{2}^{c}A_{3}\cup A_{1}^{c}A_{2}A_{3}\cup A_{1}A_{2}A_{3}$

zodat volgt:

$\#A=\#A_{1}A_{2}^{c}A_{3}^{c}+\#A_{1}^{c}A_{2}A_{3}^{c}+\#A_{1}^{c}A_{2}^{c}A_{3}+\#A_{1}A_{2}A_{3}^{c}+\#A_{1}A_{2}^{c}A_{3}+\#A_{1}^{c}A_{2}A_{3}+\#A_{1}A_{2}A_{3}=$

$=25+25+25+5+5+5+1=91$.

Dit antwoord kan ook verkregen worden door op te merken dat A de gebeurtenis is dat er geen zes bij de drie worpen is; dan is dus #A^c = 5³ = 125 en #A = #S – #A^c = 216 – 125 = 91. We kunnen #A ook door toepassing van de algemene somregel bepalen:

$\#A=\#A_{1}+\#A_{2}+\#A_{3}-\#A_{1}A_{2}-\#A_{1}A_{3}-\#A_{2}A_{3}+\#A_{1}A_{2}A_{3}=$

$=36+36+36-6-6-6+1=91$.

Als een experiment bestaat uit het uitvoeren van n deelexperimenten en het aantal mogelijke uitkomsten van elk deelexperiment is onafhankelijk van het resultaat van de overige deelexperimenten, dan vinden we het totale aantal mogelijke uitkomsten door de afzonderlijke aantallen met elkaar te vermenigvuldigen. We moeten vermenigvuldigen als de verschillende mogelijkheden tegelijkertijd moeten voorkomen, dus de een en de ander.

Het kan echter ook zijn dat we iedere mogelijkheid van het ene experiment weliswaar niet kunnen combineren met alle mogelijkheden van een ander, maar wel met een gelijk aantal mogelijkheden van het andere experiment. Ook dan krijgen we het totale aantal mogelijkheden door vermenigvuldiging. De productregel zegt hierover:

Stelling 2.2.3 (productregel)

Als ieder van de n₁ uitkomsten van een eerste experiment gecombineerd kan worden met een gelijk aantal uitkomsten n₂ van een tweede experiment en elk van deze combinaties weer met een gelijk aantal uitkomsten n₃ van een derde, etc., dan wordt het totale aantal uitkomsten gegeven door het product n₁× n₂× n₃×... van deze aantallen.

Een toepassing van de productregel is:

Stelling 2.2.4

Voor het Cartesisch product van de verzamelingen A₁,A₂,...,A_n geldt dus volgens de productregel: #(A₁× A₂×...× A_n) = #A₁× #A₂× ... × #A_n.

Voorbeeld 3

Op een menukaart staan 3 voorgerechten, 5 hoofdgerechten en 4 nagerechten. Hoeveel menu's van 3 gangen kunnen we van de kaart samenstellen? De productregel zegt dat er 3 × 5 ×4 = 60 menu's mogelijk zijn.

Voorbeeld 4

De 3 voorgerechten op de menukaart laten zich elk combineren met 4 van de 5 hoofdgerechten en elk van deze combinaties met slechts 2 van de 4 nagerechten. Volgens de productregel zijn er dan nog 3×4×2 = 24 menu's van 3 gangen mogelijk.

De productregel maakt het mogelijk te bepalen hoeveel verschillende rangschikkingen er mogelijk zijn van een aantal onderscheidbare objecten. Een rangschikking heet permutatie en het aantal permutaties van n dingen blijkt volgens de productregel gelijk te zijn aan n! (n faculteit, het product van de getallen 1 tot en met n).

Definitie 2.2.1

Onder een permutatie van n onderscheidbare objecten verstaan we een rangschikking op volgorde van die objecten.

Voorbeeld 5

De permutaties van de cijfers 1, 2 en 3 zijn: 123, 132, 213, 231, 312 en 321.

Stelling 2.2.5

Het aantal permutaties van n onderscheidbare objecten is gelijk aan n!.

Voorbeeld 5 (vervolg)

Inderdaad bleken er 3! = 6 permutaties te zijn van de drie getallen 1, 2 en 3.

We beschouwen nu het volgende - klassieke en karakteristieke - combinatorische probleem: hoeveel verschillende resultaten zijn er mogelijk als we uit een verzameling van n onderscheidbare elementen er k kiezen? Het antwoord zal afhangen van de wijze waarop we de trekkingen verrichten, nl. met of zonder terugleggen, en van de manier waarop we tegen de resultaten aankijken, nl. geordend of ongeordend. In figuur 2.1 is dit schematisch in beeld gebracht. De volgende voorbeelden illustreren de diverse mogelijkheden.

Voorbeeld 6

Uit de 100 leden van de vereniging COMBI moet een bestuur van 3 leden gekozen worden. Het bestuur bestaat uit voorzitter, secretaris en penningmeester. Twee functies kunnen niet in één persoon verenigd zijn. We moeten dus trekkingen zonder terugleggen verrichten en het resultaat moet geordend zijn. Hoeveel besturen zijn er mogelijk? Dat zijn er 100×99×98 = 100!/(100-3)!; we kunnen het bestuur samenstellen door eerst de voorzitter te kiezen, hiervoor zijn 100 mogelijkheden, daarna de secretaris, waarvoor nog 99 mogelijkheden zijn en tenslotte de penningmeester, met nog 98 mogelijkheden. We kunnen een mogelijkheid beschrijven door de namen van de bestuursleden in volgorde van de functies te vermelden; zo'n mogelijkheid heet variatie.

Voorbeeld 7

Voor het komende lustrum kiest COMBI een feestcommissie bestaande uit 3 leden. De leden van de feestcommissie hebben geen verschillende taak. We moeten trekken zonder terugleggen, maar het resultaat hoeft niet geordend te zijn. Net als in het vorige voorbeeld kunnen we op 100!/97! een geordend drietal kiezen; echter de ordening is nu niet van belang, zodat de 3! rangschikkingen van elk zo'n drietal dezelfde commissie voorstelt. Er zijn dus $100!/(3!97!)={\tbinom {100}{3}}$ mogelijkheden. We kunnen een mogelijkheid beschrijven door de namen van de drie leden te vermelden; de volgorde van de namen is niet van belang. Een mogelijkheid heet combinatie (of greep).

Voorbeeld 8

Bij COMBI moeten 3 verschillende klussen gedaan worden. Het bestuur vraagt de leden om vrijwilligers. Omdat een lid best meer dan één klus kan doen, moeten we nu trekken met terugleggen; wel moet het resultaat geordend zijn aangezien de klussen verschillen. We kiezen nu achtereen- volgens steeds een lid uit de 100 voor elk der klussen; er zijn dus 100×100×100 = 100³ mogelijkheden. We kunnen een mogelijkheid beschrijven door bij elke klus de naam te vermelden van degene die de klus uitvoert; de vermelde namen hoeven nu niet verschillend te zijn. Een mogelijkheid heet hier herhalingsvariatie.

Voorbeeld 9

Voor het lustrum bij COMBI moeten 3 biertonnen opgeschilderd worden. De feestcommissie vraagt de leden om vrijwilligers. Nu zijn de klussen niet van elkaar te onderscheiden, zodat het resultaat niet geordend hoeft te zijn; we moeten wel weer trekken met terugleggen. We beschrijven het resultaat op eenduidige wijze door voor elk van de 100 leden te vermelden hoeveel biertonnen hij zal opschilderen. We kunnen dit schematisch doen door de biertonnen voor te stellen door een o en de biertonnen voor de opgestelde leden neer te zetten; tussen de leden zetten we een streep |. Een mogelijkheid is dan bv.

1

2

3

4

5

$\cdots$

100

$\mid$

$\mid$

$\circ$

$\mid$

$\mid$

$\circ \circ$

$\mid$

$\cdots$

$\mid$

hetgeen wil zeggen dat lid 1 geen bierton opschildert, evenals lid 2; nr 3 schildert één ton op, nr 4 weer geen, nr 5 schildert 2 tonnen op en de overigen geen. Elke mogelijkheid bestaat dus uit een rijtje van 3 nullen (de tonnen) en 99 enen (de scheidingsstrepen); er zijn

${100-1+3 \choose 3}={102 \choose 3}$

van zulke rijtjes. Hier heet een mogelijke uitkomst herhalingscombinatie.

De bovenstaande voorbeelden beschrijven we wel mbv. een vaasmodel. We trokken drie keer uit een vaas met 100 genummerde knikkers, de ene keer met terugleggen, de andere keer zonder terugleggen. In twee gevallen beschouwden we geordende drietallen als uitkomsten, in twee andere gevallen ongeordende. In de volgende figuur is een en ander schematisch weergegeven.

Figuur 2.1. Trekkingen uit een vaas.

In de voorbeelden kwamen de volgende begrippen en resultaten aan de orde.

Definitie 2.2.2

Onder een variatie van k uit n (onderscheidbare objecten) verstaan we de uitkomst van een geordende trekking zonder terugleggen van k van de n objecten.

Stelling 2.2.6

Het aantal variaties van k uit n is gelijk aan n!/(n–k)!.

Definitie 2.2.3

Onder een combinatie (of greep) van k uit n onderscheidbare objecten verstaan we de uitkomst van een ongeordende trekking zonder terugleggen van k van de n objecten.

Stelling 2.2.7

Het aantal combinaties van k uit n is gelijk aan:

${n \choose k}={\frac {n!}{k!(n-k)!}}$.

Definitie 2.2.4

Onder een herhalingsvariatie van k uit n onderscheidbare objecten verstaan we de uitkomst van een geordende trekking met terugleggen van k van de n objecten.

Stelling 2.2.8

Het aantal herhalingsvariaties van k uit n is gelijk aan n^k.

Definitie 2.2.5

Onder een herhalingscombinatie van k uit n onderscheidbare objecten verstaan we de uitkomst van een ongeordende trekking met terugleggen van k van de n objecten.

Stelling 2.2.9

Het aantal herhalingscombinaties van k uit n is gelijk aan:

${n-1+k \choose k}$.

In het volgende schema geven we een overzicht van het trekken van k elementen uit een verzameling (vaas) van n onderscheidbare elementen (knikkers).

uitkomst	trekking
	zonder terugleggen	met terugleggen
geordend	variatie	herhalings- variatie
ongeordend	combinatie	herhalings- combinatie

In het volgende voorbeeld hebben we het geval n=4 en k=3 helemaal uitgeschreven.

Voorbeeld 10

123 132 213 231 312 321	124 142 214 241 412 421	134 143 314 341 413 431	234 243 324 342 423 432|	24 variaties (rijtjes) 4 combinaties (hokjes)									64 herhalings─ variaties (rijtjes) 20 herhalings─ combinaties (hokjes)
112 121 211	113 131 311	114 141 411	221 212 122	223 232 322	224 242 422	331 313 133	332 323 233	334 343 433	441 414 144	442 424 244	443 434 344
111	222	333	444

In het vaasmodel denken we ons de trekkingen altijd aselect, dwz. bij iedere trekking hebben de resterende knikkers alle gelijke kans om getrokken te worden. We realiseren aselecte trekkingen door de vaas goed te schudden en er willekeurig (blindelings, lukraak) een knikker uit te trekken.

Definitie 2.2.6

Onder een aselecte trekking uit een populatie verstaan we een symmetrisch experiment met die populatie als uitkomstenruimte.

Aselecte trekkingen leiden in de gevallen van variaties, combinaties en herhalingsvariaties tot symmetrische kansruimten. We zullen pas in een volgend hoofdstuk, na de invoering van het begrip voorwaardelijke kans, het waarom hiervan goed kunnen inzien. Voorlopig, en dat ligt ook in de lijn van dit hoofdstuk, zullen we ons moeten beroepen op de symmetrie van de situatie. In het geval van herhalingscombinaties ontstaat geen symmetrie ondanks aselect trekken!

Stelling 2.2.10

Als we k keer aselect trekken uit een verzameling van n verschillende elementen, dan is de kansruimte in de volgende gevallen symmetrisch:

(a) trekken zonder terugleggen, geordende uitkomsten:

S={variaties}, $\#S={\frac {n!}{(n-k)!}}$;

(b) trekken zonder terugleggen, ongeordende uitkomsten:

S={combinaties}, $\#S={n \choose k}={\frac {n!}{k!(n-k)!}}$;

(c) trekken met terugleggen, geordende uitkomsten:

S={herhalingsvariaties}, $\#S=n^{k}$;

De ontstane kansruimte is niet symmetrisch in geval:

(d) trekken met terugleggen, ongeordende uitkomsten.

Bewijs: De gevallen a, b en c volgen op grond van de symmetrie in de uitkomsten. In het geval d vatten we de uitkomsten op als gebeurtenissen in de kansruimte van de herhalingsvariaties. De uitkomst (k,0,...,0), dus k keer is object nummer 1 getrokken, komt dan overeen met de gebeurtenis {(1,1,...,1)} bij de herhalingsvariaties en heeft dus een kans 1/nk. De uitkomst (k-1,1,0,...,0), dus k-1 keer is object nummer 1 en 1 keer nummer2 getrokken, komt overeen met de gebeurtenis {(1,1,...,1,2),(1,1,...,1,2,1),...,(2,1,...,1)} en bevat k elementen, nl. alle herhalingsvariaties met k-1 keer een 1 en 1 keer een 2; de kans hierop is k/n^k.

We geven nu enkele toepassingen.

Voorbeeld 11

We trekken lukraak achtereenvolgens (dus geordend resultaat₀ zonder terugleggen k knikkers uit een vaas met n genummerde knikkers. Wat is de kans dat de eerste getrokken knikker nummer i is? De uitkomsten zijn variaties en de kansruimte is symmetrisch; #S = n!/(n–k)!. De gebeurtenis dat de eerste knikker nummer i heeft, noemen we A; A bevat alle variaties met op de 1e plaats nummer i. De uitkomsten uit A kunnen we krijgen door als eerste knikker nummer i te pakken en vervolgens nog k–1 andere, dus nog een variatie van k–1 uit n–1. A bevat dus (n–1)!/(n–k)! uitkomsten. De gevraagde kans is: P(A) = #A/#S = 1/n, hetgeen ons niet zal verbazen.

Hoe groot is de kans dat de tweede getrokken knikker nummer i is? Op dezelfde manier beredeneren we dat deze gebeurtenis, zeg B, de variaties bevat met op de tweede plaats nummer i. Dat zijn er evenveel als in A; zet nummer i alvast op de tweede plaats en vul de overige plaatsen met een variatie van k–1 uit n–1. We vinden dus P(B) = P(A) = 1/n.

Op analoge wijze vinden we dat de kans dat de knikker die als je getrokken wordt, nummer i is, steeds 1/n is.

De kans dat nummer i getrokken wordt, is P("nummer i") = P("nummer i als 1^e" of "als 2^e" of ... of "als k^e") = = P("als 1^e") + P("als 2^e") + ... + P("als k^e") = k/n.

Voorbeeld 12

We trekken lukraak zonder op de volgorde te letten en zonder terugleggen k knikkers uit een vaas met n genummerde knikkers. De uitkomsten zijn combinaties en de kansruimte is symmetrisch;

$\#S={n \choose k}$.

P("nummer i wordt getrokken") = ${\frac {n-1 \choose k-1}{n \choose k}}={\frac {k}{n}}$,

want de bedoelde gebeurtenis bevat de combinaties waar nummer i bij is. We krijgen die combinaties door nummer i alvast te pakken en aan te vullen met een combinatie van k–1 uit de overige n. Merk op dat deze kans dezelfde is als bij het vorige voorbeeld.

Voorbeeld 13

We trekken lukraak uit een goed geschud kaartspel een tiental kaarten. Er is dus sprake van ongeordende uitkomst en trekken zonder terugleggen. De kansruimte is symmetrisch. Wat is de kans dat bij de getrokken tien kaarten 2 azen en 3 heren zijn? We geven de situatie schematisch weer:

	azen	heren	rest	totaal
populatie	4	4	44	52
steekproef	2	3	5	10

In totaal zijn er ${52 \choose 10}$ mogelijke uitkomsten (combinaties); de genoemde gebeurtenis kan op ${4 \choose 2}{4 \choose 3}{44 \choose 5}$ manieren gerealiseerd worden, dus de gevraagde kans is:

${\frac {{4 \choose 2}{4 \choose 3}{44 \choose 5}}{52 \choose 10}}=0,0016$.

Voorbeeld 14 (sinterklaaslootjes; enveloppe-probleem)

Met sinterklaas stoppen n mensen een briefje met hun naam in een hoge hoed. Na goed schudden trekt elk er lukraak weer een lootje uit. Hoe groot is de kans p_n dat niemand z'n eigen naam trekt? (Als enveloppe-probleem: een secretaresse stopt n brieven lukraak in de reeds geadresseerde enveloppen.) Noem A_i de gebeurtenis dat nummer i z'n eigen naam trekt; dan is de gevraagde kans:

$p_{n}=P({\overline {A_{1}\cup A_{2}\cup ...\cup A_{n}}})=1-P(A_{1}\cup A_{2}\cup ...\cup A_{n})=$

$=1-\left(\sum P(A_{i})-\sum P(A_{i}A_{j})+\sum P(A_{i}A_{j}A_{k})-....\pm P(A_{1}A_{2}...A_{n})\right)=$

$=1-{n \choose 1}{\frac {(n-1)!}{n!}}+{n \choose 2}{\frac {(n-2)!}{n!}}-{n \choose 3}{\frac {(n-3)!}{n!}}+\ldots \pm {n \choose n}{\frac {0!}{n!}}=$

$=1-{\frac {n \choose 1}{n}}+{\frac {n \choose 2}{n(n-1)}}-{\frac {n \choose 3}{n(n-1)(n-2)}}+\ldots \pm {\frac {n \choose n}{n!}}=$

$=1-\left({\frac {1}{1!}}-{\frac {1}{2!}}+\ldots \pm {\frac {1}{n!}}\right)\approx {\frac {1}{e}}\approx 0{,}368$

De kans p_n verandert vanaf n = 6 à 7 niet veel meer; 1/e is dan al een goede benadering.

In een tabel:

$n$	1	2	3	4	5	6	7	...
$p_{n}$	0	0,500	0,333	0,375	0,367	0,365	0,365	...

Het geval van het ongeordend trekken zonder terugleggen van k knikkers uit een vaas met n knikkers, kunnen we ook beschrijven als het verdelen van de n knikkers uit de vaas in twee groepen ter grootte van k en n–k, nl. de wel getrokken k en de niet getrokken n–k. We generaliseren dit experiment door de knikkers te verdelen in m groepen met aantallen n₁,n₂,...,n_m, waarvoor dus geldt: n₁+ n₂+...+ n_m= n. We doen dit door de knikkers te rangschikken, hetgeen kan op n! manieren, en de eerste n₁ aan groep 1 toe te wijzen, de volgende n₂ aan groep 2, etc. Omdat de volgorde van de n₁ knikkers in groep 1 er niet toe doet (er zijn n₁! rangschikkingen) en evenzo niet voor de andere groepen, is het totaal aantal verdelingen over de m groepen, de zgn. multinomiaalcoëfficiënt.

Definitie 2.2.7

Onder de multinomiaalcoëfficiënt ${n \choose n_{1},n_{2},...,n_{m}}$ verstaan we het aantal manieren om n onderscheidbare objecten te verdelen in m groepen met aantallen n₁,n₂,...,n_m, waarvoor n₁+ n₂+...+ n_m= n.

Stelling 2.2.11

Voor de multinomiaalcoëfficiënt geldt:

${n \choose n_{1},n_{2},...,n_{m}}={\frac {n!}{n_{1}!n_{2}!\cdots n_{m}!}}$

De tweede schrijfwijze van de multinomiaalcoëfficiënt in deze stelling laat zien dat we de stelling ook kunnen bewijzen door de verschillende groepen achtereenvolgens te vullen met het juiste aantal knikkers.

Voorbeeld 15

Op hoeveel manieren kunnen we 30 personen verdelen over 4 groepen van resp. 6, 7, 8 en 9 personen? Dit kan op

${30 \choose 6,7,8,9}={\frac {30!}{6!7!8!9!}}={30 \choose 6}{24 \choose 7}{17 \choose 8}{9 \choose 9}$

manieren. De laatste schrijfwijze laat zien hoe de 4 groepen achtereenvolgens gevuld worden. We kunnen daarvoor ook schrijven:

${30 \choose 24}{24 \choose 17}{17 \choose 9}{9 \choose 0}$

daarmee suggererend dat we de gewenste verdeling tot stand brengen door steeds de overblijvende personen weg te nemen.