Samenvattingen · Wiskunde DNL · HAVO

Combinatoriek

Combinatoriek beantwoordt de vraag op hoeveel verschillende manieren iets kan, en is bij wiskunde D volwaardige examenstof binnen domein B. Je leert systematisch tellen met een wegendiagram en de vermenigvuldigingsregel, en daarna rekenen met faculteit, permutaties, variaties en combinaties (de binomiaalcoëfficiënt). Omdat wiskunde D volledig via het schoolexamen (SE) wordt afgenomen, ligt de nadruk op het herkennen van de juiste telwijze, het netjes uitrekenen ervan en de stap naar de kansrekening.

4Onderdelenca. 27min leestijd4VaardighedenNiveauBasis 1 · Standaard 3

T·0333 / 13

Examenprofiel

Een telprobleem systematisch aanpakken met een wegendiagram en de vermenigvuldigingsregel toepassen, met en zonder herhaling.Rekenen met faculteit en permutaties, en beredeneren waarom de volgorde bij rangschikken meetelt.Variaties en combinaties onderscheiden en de binomiaalcoëfficiënt afleiden en toepassen (nCr/nPr op de grafische rekenmachine).Samengestelde telproblemen oplossen, permutaties met herhaling herkennen en de telling gebruiken om kansen te bepalen.

Operatoren:berekentelbepaalleg uitberedeneer

basisniveau

Beheers het systematisch tellen met een wegendiagram en de vermenigvuldigingsregel (met en zonder herhaling) — dat zijn de basisgereedschappen waarmee je elk telprobleem aanpakt.

verhoogd niveau

Reken vlot met permutaties, variaties en combinaties, leid de binomiaalcoëfficiënt af, en pak samengestelde telproblemen en permutaties met herhaling aan als opstap naar de kansrekening.

Diepte

Schrift

Inhalt · 4 onderdelen

Combinatoriek

Wegendiagram en de vermenigvuldigingsregel#

Basisexamenblad-nl

Wegendiagram van een code van twee tekens

Afb. 1Elke weg van links naar rechts is één code; met herhaling zijn er 3 · 3 = 9 wegen.

Een telprobleem stelt steeds dezelfde vraag: op hoeveel verschillende manieren kan iets? Hoeveel codes heeft een slot, hoeveel routes lopen er van

A

naar

B

, hoeveel teams kun je samenstellen? Het deel van de wiskunde dat zulke vragen beantwoordt heet combinatoriek, en bij wiskunde D — een profielkeuzevak in Natuur en Techniek, naast wiskunde B — is het volwaardige examenstof binnen domein B, geen bijzaak. Alles wat je hier leert wordt getoetst in het schoolexamen (SE), want wiskunde D wordt volledig via het SE afgenomen. De grootste valkuil bij tellen is dat je de mogelijkheden lukraak opschrijft; dan vergeet je er bijna zeker een paar of tel je dezelfde dubbel. De uitweg is systematisch tellen: je legt een vaste volgorde op waarin je alle mogelijkheden langsloopt, zodat je zeker weet dat je niets overslaat en niets dubbel telt. In deze paragraaf leer je daarvoor het wegendiagram (boomdiagram) en de rekenregel die er rechtstreeks uit volgt: de vermenigvuldigingsregel.

Een wegendiagram — ook boomdiagram genoemd — brengt een keuze die uit meerdere stappen bestaat overzichtelijk in beeld. Je begint links bij één startpunt en tekent voor elke mogelijkheid van de eerste stap een tak. Aan het eind van elke tak vertak je opnieuw voor de tweede stap, en zo verder. Elk niveau van het diagram hoort bij precies één stap, en het aantal takken op dat niveau is het aantal mogelijkheden voor die stap. Een volledig pad van de start helemaal naar rechts heet een eindweg, of kortweg een weg, en zo'n weg stelt precies één volledige mogelijkheid voor — vandaar de naam wegendiagram. Bekijk het diagram hiernaast: het hoort bij een code van twee tekens waarbij elk teken een letter

A

B

C

is. Vanuit de start splitst het eerste teken zich in drie takken, en bij elk eerste teken splitst het tweede teken zich opnieuw in drie. Elke weg door het diagram, bijvoorbeeld

A \to C

, is één complete code.

De vermenigvuldigingsregel, ook wel de productregel, is de rekenkundige samenvatting van wat het diagram laat zien. Bestaat een keuze uit twee stappen, en kun je de eerste op

a

manieren en de tweede op

b

manieren doen, dan is het totale aantal mogelijkheden

a \cdot b

. Je ziet meteen waaróm: in het diagram splitst elk van de

a

takken van de eerste stap zich in

b

vervolgtakken, dus krijg je

a

groepjes van elk

b

wegen, samen

a \cdot b

. De regel telt zo precies de eindwegen, maar zonder dat je het hele diagram hoeft te tekenen. En hij stopt niet bij twee stappen: bij

k

stappen achter elkaar vermenigvuldig je alle aantallen,

N = n_1 \cdot n_2 \cdots n_k

. Een pincode van vier cijfers maak je in vier stappen van elk tien mogelijkheden, dus zijn er

10 \cdot 10 \cdot 10 \cdot 10 = 10000

pincodes. Je hoeft het probleem alleen in losse stappen te ontleden en per stap te tellen hoeveel mogelijkheden er zijn.

Een cruciaal onderscheid is of bij elke stap dezelfde mogelijkheden beschikbaar blijven. Mogen ze zich herhalen (met herhaling), dan is het aantal per stap steeds gelijk: bij een pincode mag elk cijfer opnieuw gekozen worden, dus blijft het tien per positie. Mogen ze zich níét herhalen (zonder herhaling), dan neemt het aantal per stap met één af, want wat je al gebruikt hebt valt af. Moet een code uit drie verschillende cijfers bestaan, dan heb je tien keuzes voor het eerste cijfer, negen voor het tweede en acht voor het derde:

10 \cdot 9 \cdot 8 = 720

. Dezelfde drie posities, maar de eis „verschillend” verandert

10 \cdot 10 \cdot 10 = 1000

720

. Lees een opgave daarom altijd scherp: de woorden „mag herhaald worden” en „moeten verschillend zijn” leiden tot heel verschillende berekeningen, en ze door elkaar halen is een van de meest gemaakte fouten in dit onderwerp.

Wanneer je

r

stappen hebt die elk dezelfde

n

mogelijkheden hebben (met herhaling), wordt het product een macht:

n \cdot n \cdots n = n^r

. Zo zijn er

26^3 = 17576

lettercombinaties van drie letters en

10^4 = 10000

pincodes van vier cijfers — handig, want je hoeft de factoren niet uit te schrijven. In het diagram hiernaast is

n = 3

r = 2

, dus

3^2 = 9

wegen. De vermenigvuldigingsregel is je standaardgereedschap zodra een keuze in losse stappen uiteenvalt en je alleen het áántal mogelijkheden wilt, niet de hele lijst. Pas wel op met situaties waarin de volgorde juist niet meetelt of waarin je maar een deel van de objecten rangschikt — dan heb je de fijnere telregels van de volgende paragrafen nodig: permutaties, variaties en combinaties. Maar die bouwen allemaal voort op deze ene regel, dus beheers hem eerst grondig.

N = n_1 \cdot n_2 \cdots n_k

vermenigvuldigingsregel

Het totale aantal mogelijkheden van een keuze in k opeenvolgende stappen is het product van het aantal mogelijkheden per stap.

N = n^r

r gelijke stappen, met herhaling

Zijn er r stappen die elk dezelfde n mogelijkheden hebben, dan is het totaal n tot de macht r, bijvoorbeeld tien tot de macht vier oftewel 10000 pincodes.

Uitgewerkt voorbeeld

Een code tellen — met en zonder herhaling

Een kluis heeft een code van 3 tekens. Elk teken is een letter uit het rijtje A, B, C, D, E (5 letters). Bereken het aantal mogelijke codes (a) als letters herhaald mogen worden en (b) als de drie letters onderling verschillend moeten zijn.

Stap 1 — Ontleed in stappen
De code ontstaat in drie stappen: kies het 1e teken, dan het 2e, dan het 3e. Per stap tel je hoeveel letters je mag kiezen, en die aantallen vermenigvuldig je.
Stap 2 — (a) met herhaling
Mag elke letter herhaald worden, dan heb je bij elke stap alle 5 letters beschikbaar. Het aantal codes is het product van drie keer 5, oftewel 5 tot de macht 3.
$5 \cdot 5 \cdot 5 = 5^3 = 125$
Stap 3 — (b) zonder herhaling
Moeten de letters verschillen, dan valt na elke keuze één letter af: 5 keuzes voor het 1e teken, 4 voor het 2e en 3 voor het 3e.
$5 \cdot 4 \cdot 3 = 60$

Resultaat: Met herhaling zijn er 125 codes, zonder herhaling 60. Het verschil ontstaat doordat de eis „verschillend” bij elke volgende stap één mogelijkheid wegneemt.

Veelgemaakte fouten

De aantallen optellen in plaats van vermenigvuldigen; bij stappen achter elkaar (eerst dit, dan dat) hoort vermenigvuldigen, niet optellen.
„Met herhaling” en „zonder herhaling” verwarren; mogen de tekens verschillen, dan neemt het aantal keuzes per stap met één af (10, 9, 8, …), anders blijft het gelijk (10, 10, 10, …).

Actieve herhaling

Een toegangscode bestaat uit 2 letters (uit de 26 letters van het alfabet) gevolgd door 3 cijfers (0 t/m 9). Bereken het aantal mogelijke codes (a) als alles herhaald mag worden en (b) als de 2 letters onderling verschillend moeten zijn en de 3 cijfers ook. Geef per stap aan met hoeveel keuzes je rekent.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma wiskunde D (HAVO) (CvTE / Examenblad)

Permutaties en faculteit#

Standardexamenblad-nl

Faculteit n!

Afb. 2De faculteit groeit razendsnel: van 0! = 1 tot 7! = 5040.

Bij sommige telproblemen gaat het niet om losse keuzes maar om het rángschikken van objecten in een bepaalde volgorde: op hoeveel manieren kun je zes verschillende boeken op een plank zetten, of in welke volgorde kunnen acht hardlopers finishen? Zo'n geordende rangschikking heet een permutatie. Het kenmerkende is dat de volgorde meetelt: de rij

A, B, C

is een ándere uitkomst dan

C, B, A

, ook al staan er dezelfde elementen in. Je kunt zo'n rangschikking opvatten als een keuze in stappen — wie staat vooraan, wie daarachter, enzovoort — en daarmee valt het rangschikken precies onder de vermenigvuldigingsregel zonder herhaling uit de vorige paragraaf. Elk object dat je neerzet, kun je daarna immers niet nóg een keer gebruiken, dus loopt het aantal keuzes per plaats netjes terug. Permutaties zijn de eerste van drie verfijnde telwijzen (permutaties, variaties, combinaties) die samen het hart van combinatoriek in domein B vormen.

Bekijk het rangschikken van

n

verschillende objecten in een rij. Voor de eerste plaats heb je

n

keuzes; voor de tweede blijven er

n-1

over, want één object ligt al; voor de derde

n-2

, en zo door tot er voor de laatste plaats nog één object over is. Volgens de vermenigvuldigingsregel is het aantal rangschikkingen dan

n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1

. Dit product van alle gehele getallen van

n

tot en met

1

komt zo vaak voor dat het een eigen naam en symbool heeft: de faculteit van

n

, genoteerd

n!

en uitgesproken als „n-faculteit”. Zo is

5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120

: vijf verschillende boeken kun je dus op

120

volgordes neerzetten. Merk op dat de faculteit niets anders is dan de vermenigvuldigingsregel toegepast op het volledig rangschikken van een verzameling.

De faculteit groeit razendsnel, veel sneller dan een gewone macht. De tabel hiernaast laat dat zien:

3! = 6

, maar

7! = 5040

, en

10!

is al meer dan drie miljoen. Daarom reken je grote faculteiten beter met de grafische rekenmachine (GR) dan met de hand; daar staat de faculteit als de toets met het uitroepteken. Eén afspraak verdient bijzondere aandacht:

0! = 1

. Dat lijkt vreemd, maar het klopt met de betekenis — er is precies één manier om „niets” te rangschikken, namelijk de lege rij — en het zorgt ervoor dat de formules verderop netjes blijven kloppen. Zonder die afspraak zou de permutatie- en combinatieformule bij de randgevallen onzin geven. Onthoud

0! = 1

daarom goed; je hebt het nodig zodra je

\frac{n!}{(n-r)!}

of de binomiaalcoëfficiënt invult en

n-r

toevallig nul wordt.

Vaak rangschik je niet álle objecten, maar slechts een deel ervan. Uit acht hardlopers wil je weten hoeveel erelijsten van de eerste drie plaatsen mogelijk zijn; dan stopt het aftellen eerder. Voor de eerste plaats heb je acht keuzes, voor de tweede zeven en voor de derde zes, samen

8 \cdot 7 \cdot 6 = 336

. Dit is een permutatie van

r

uit

n

, en met faculteiten schrijf je dat compact als

\frac{n!}{(n-r)!}

. De teller

n!

telt álle rangschikkingen; de noemer

(n-r)!

deelt de rangschikkingen van de

n-r

overgebleven objecten weer weg, die je immers niet meetelt. Voor het voorbeeld:

\frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336

, precies wat de vermenigvuldigingsregel ook gaf. Op de GR vind je dit als de functie nPr: je toetst 8 nPr 3 en krijgt 336.

Gebruik een permutatie zodra de volgorde meetelt én je objecten op genummerde of onderscheiden plaatsen zet: een startvolgorde, een erelijst, een rij voor de foto, een wachtwoord met allemaal verschillende tekens. Let bij het lezen van een opgave goed op signaalwoorden. Zit er een rangorde in — eerste, tweede, derde — of een vaste volgorde, dan is het een permutatie en gebruik je

n!

(alle objecten) of

\frac{n!}{(n-r)!}

(een deel). Tel je daarentegen een groepje waarin de onderlinge volgorde niet uitmaakt, dan heb je géén permutatie nodig maar een combinatie, en kan het ook zo zijn dat objecten herhaald mogen worden, wat een variatie geeft. Juist dat onderscheid tussen „volgorde telt wél” en „volgorde telt niet”, en tussen „met” en „zonder herhaling”, staat centraal in de volgende paragraaf en bepaalt steeds welke formule je pakt.

n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1

faculteit

Het aantal manieren om n verschillende objecten in een rij te rangschikken; spreek uit als „n-faculteit”. Afspraak: 0! = 1.

{}_{n}P_{r} = \frac{n!}{(n-r)!}

permutaties van r uit n

Het aantal geordende rangschikkingen van r objecten gekozen uit n, waarbij de volgorde meetelt; op de GR de functie nPr.

Uitgewerkt voorbeeld

Rangschikken: alle objecten én een deel

(a) Op hoeveel volgordes kun je 6 verschillende leerlingen op een rij zetten voor een groepsfoto? (b) Uit 7 atleten wordt de erelijst van de eerste drie plaatsen (goud, zilver, brons) opgemaakt; hoeveel verschillende erelijsten zijn er?

Stap 1 — (a) alle objecten rangschikken
Alle 6 leerlingen op een rij: 6 keuzes voor de 1e plaats, 5 voor de 2e, 4 voor de 3e, enzovoort tot 1 voor de laatste. Dat is 6-faculteit.
$6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$
Stap 2 — (b) een deel rangschikken
Nu vul je maar 3 van de 7 plaatsen, en de volgorde (goud, zilver, brons) telt. Dat is een permutatie van 3 uit 7.
$\frac{7!}{(7-3)!} = \frac{7!}{4!} = 7 \cdot 6 \cdot 5 = 210$
Stap 3 — Controleer met de stappenredenering
Reken (b) los na met de vermenigvuldigingsregel: 7 keuzes voor goud, 6 voor zilver, 5 voor brons, samen 7 · 6 · 5 = 210. Dezelfde uitkomst — de permutatieformule is alleen een snellere schrijfwijze.

Resultaat: (a) 720 volgordes voor de zes leerlingen; (b) 210 verschillende erelijsten van de eerste drie plaatsen.

Veelgemaakte fouten

0! per ongeluk als 0 nemen; per afspraak geldt 0! = 1, en daar reken je gewoon mee in de formules.
Een permutatie (volgorde telt) verwarren met een combinatie (volgorde telt niet); bij rangschikken op genummerde plaatsen gebruik je de faculteit of de permutatie, niet de binomiaalcoëfficiënt.

Actieve herhaling

Een klas kiest uit 6 kandidaten een voorzitter, een secretaris en een penningmeester; dit zijn drie verschillende functies. Bereken op hoeveel manieren dat kan en leg uit waarom dit een permutatie is.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma wiskunde D (HAVO) (CvTE / Examenblad)

Variaties en combinaties#

Standardexamenblad-nl

Welke telwijze?

Afb. 3Twee vragen — telt de volgorde, mag herhaling — bepalen de telwijze en de formule.

De spilvraag bij elk telprobleem is: telt de volgorde mee of niet? Het antwoord bepaalt welke van twee telwijzen je kiest. Telt de volgorde wél mee, dan heet een geordende greep van

r

objecten uit

n

een variatie; telt de volgorde níét mee, dan heet zo'n ongeordende greep een combinatie. Kies je drie leerlingen uit een klas voor een werkgroep, dan is het groepje

\{A, B, C\}

hetzelfde als

\{C, A, B\}

— dezelfde drie personen, dus een combinatie. Maak je met diezelfde drie een erelijst goud-zilver-brons, dan is

A, B, C

wél iets anders dan

C, A, B

— een variatie. Bij variaties speelt bovendien nog of objecten herhaald mogen worden; bij combinaties gaan we op de HAVO steeds uit van verschillende objecten zonder herhaling. In deze paragraaf zet je beide telwijzen netjes naast elkaar en leid je de formule voor combinaties af uit wat je al weet.

Een variatie is geordend kiezen, en de aantallen ken je daar al van. Mogen objecten herhaald worden (variatie met herhaling), dan heeft elk van de

r

plaatsen dezelfde

n

mogelijkheden, dus zijn er

n^r

variaties — denk aan een pincode of een code waarin een teken vaker mag voorkomen. Mogen objecten niet herhaald worden (variatie zonder herhaling), dan loopt het aantal keuzes per plaats terug en zijn er

\frac{n!}{(n-r)!}

variaties — precies de permutatie van

r

uit

n

uit de vorige paragraaf. Een variatie zonder herhaling is dus hetzelfde als een permutatie van een deel: de twee woorden duiden hetzelfde aan. Kies je bijvoorbeeld geordend

2

letters uit

\{A, B, C, D\}

zonder herhaling, dan zijn er

\frac{4!}{2!} = 4 \cdot 3 = 12

variaties; mág een letter herhaald worden, dan

4^2 = 16

. Het enige nieuwe woord hier is „variatie”; de formules ken je al.

Het aantal combinaties van

r

objecten uit

n

bereken je met de binomiaalcoëfficiënt

\binom{n}{r}

, uitgesproken als „n boven r”. De formule is

\binom{n}{r} = \frac{n!}{r!\,(n-r)!}

, en je begrijpt haar het best door haar uit de variatie af te leiden. Het aantal geordende grepen van

r

uit

n

(zonder herhaling) is

\frac{n!}{(n-r)!}

. Maar bij een combinatie telt de volgorde niet mee, en elk groepje van

r

objecten kun je op

r!

manieren ordenen. In de geordende telling is elk groepje dus precies

r!

keer meegeteld. Door door

r!

te delen haal je die dubbeltelling eruit:

\binom{n}{r} = \frac{1}{r!} \cdot \frac{n!}{(n-r)!} = \frac{n!}{r!\,(n-r)!}

. Die ene stap — geordend tellen en dan door

r!

delen — is de kern van bijna elk combinatieprobleem, en het loont haar te kunnen navertellen in plaats van de formule blind in te vullen.

Vergelijk twee bijna gelijke vragen over dezelfde acht hardlopers. „Hoeveel erelijsten van de eerste drie plaatsen zijn er?” — hier telt de volgorde, want goud, zilver en brons zijn verschillend, dus is het een variatie (permutatie):

\frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336

. „Op hoeveel manieren kun je drie van de acht lopers kiezen voor een interview?” — hier telt de volgorde níét, dus is het een combinatie:

\binom{8}{3}

. Omdat elk drietal op

3! = 6

volgordes te ordenen is, is de combinatie precies zes keer kleiner:

\binom{8}{3} = \frac{336}{6} = 56

. Dezelfde getallen, dezelfde acht lopers — maar de vraag óf de volgorde meetelt bepaalt of je

336

56

als antwoord geeft. Wen jezelf daarom aan om bij elke telopgave éérst hardop te zeggen of de volgorde meedoet.

Twee handigheden maken het rekenen met combinaties lichter. De eerste is de symmetrie

\binom{n}{r} = \binom{n}{n-r}

: kiezen wélke

r

objecten je meeneemt is hetzelfde als kiezen welke

n-r

je achterlaat, dus leveren beide hetzelfde aantal op. Daardoor reken je

\binom{10}{8}

sneller als

\binom{10}{2} = \frac{10 \cdot 9}{2} = 45

. De tweede is de grafische rekenmachine: daarop staat de combinatie als de functie nCr en de variatie (permutatie) als nPr. Je toetst bijvoorbeeld 10 nCr 2 en krijgt 45, of 8 nCr 3 en krijgt 56. Reken een combinatie wel een paar keer met de hand uit voordat je op de GR vertrouwt, want bij het schoolexamen (SE) moet je kunnen laten zien dát en waaróm je deelt door

r!

. De GR geeft alleen het getal; de redenering moet van jou komen.

Pak bij elk telprobleem dus eerst de hoofdvraag aan voordat je een formule kiest. Stap één: telt de volgorde mee? Zo ja, dan is het een variatie of permutatie; zo nee, een combinatie. Stap twee: mogen objecten herhaald worden? Dat onderscheidt

n^r

van

\frac{n!}{(n-r)!}

. De tabel hiernaast vat deze beslissing samen: per telwijze lees je af of de volgorde telt, of herhaling mag, en welke formule erbij hoort. Wie deze twee vragen consequent stelt, kiest vrijwel altijd vanzelf de juiste telwijze, ook bij lastig geformuleerde opgaven. In de volgende paragraaf bouwen we hierop voort: dan combineren we telwijzen (eerst het ene groepje, dán het andere), behandelen we het rangschikken van objecten die deels gelijk zijn, en zien we hoe deze tellingen de basis vormen voor de kansrekening.

V = n^r

variatie met herhaling

Geordend kiezen van r uit n waarbij elk teken herhaald mag worden; elke van de r plaatsen heeft dezelfde n keuzes.

V = \frac{n!}{(n-r)!}

variatie zonder herhaling (= permutatie van r uit n)

Geordend kiezen van r uit n zonder herhaling; het aantal keuzes per plaats loopt terug. Op de GR: nPr.

\binom{n}{r} = \frac{n!}{r!\,(n-r)!}

combinatie (binomiaalcoëfficiënt)

Ongeordend kiezen van r uit n; de geordende telling gedeeld door r!. Spreek uit „n boven r”, op de GR de functie nCr.

\binom{n}{r} = \binom{n}{n-r}

symmetrie

Kiezen welke r je meeneemt is hetzelfde als kiezen welke n − r je weglaat; reken met de kleinste van de twee.

Uitgewerkt voorbeeld

Een groepje kiezen — met getalcontrole

Uit een selectie van 9 spelers wordt een team van 4 gekozen; de volgorde maakt niet uit. Bereken op hoeveel manieren dat kan, en controleer je antwoord via de bijbehorende geordende telling.

Stap 1 — Herken het type
De volgorde binnen het team doet er niet toe (een team is een team), dus dit is een combinatie van 4 uit 9.
Stap 2 — Vul de binomiaalcoëfficiënt in
Gebruik de binomiaalcoëfficiënt met n = 9 en r = 4, en reken de breuk uit.
$\binom{9}{4} = \frac{9!}{4!\,5!} = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{3024}{24} = 126$
Stap 3 — Controleer via de variatie
Zou de volgorde wél tellen, dan waren er 9 · 8 · 7 · 6 = 3024 geordende viertallen. Elk team van 4 is op 4! = 24 volgordes te ordenen, dus deel je 3024 door 24: dat geeft opnieuw 126. De getallen kloppen.

Resultaat: Er zijn 126 verschillende teams van 4 spelers. De controle 3024 ÷ 24 = 126 bevestigt het: de combinatie is precies 4! keer kleiner dan de bijbehorende geordende telling.

Veelgemaakte fouten

Een variatie of permutatie gebruiken waar de volgorde niet meetelt, of omgekeerd; vraag je telkens af of „A, B, C” en „C, B, A” als hetzelfde of als verschillend tellen.
De binomiaalcoëfficiënt verkeerd invullen door r! in de noemer te vergeten; de noemer is r! · (n − r)!, niet alleen (n − r)! — dat laatste hoort bij de variatie zonder herhaling.

Actieve herhaling

In een vereniging van 12 leden wordt een commissie van 4 personen gekozen, zonder rangorde. Bereken het aantal mogelijke commissies, en leg uit waarom dit een combinatie is en geen variatie. Controleer je antwoord door de bijbehorende geordende telling door 4! te delen.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma wiskunde D (HAVO) (CvTE / Examenblad)

Permutaties met herhaling en toepassingen#

Standardexamenblad-nl

Beslisschema telwijzen

Afb. 4Twee vragen — telt de volgorde mee, en mag er herhaald worden — leiden naar de juiste telwijze.

Tot nu toe waren alle objecten verschillend. Maar wat als sommige identiek zijn? Denk aan het aantal verschillende „woorden” (letterrijtjes) dat je kunt maken met de letters van een woord waarin een letter vaker voorkomt. Dit heet een permutatie met herhaling. Het probleem is dat je dan niet zomaar

n!

mag nemen: als twee objecten identiek zijn, levert het onderling verwisselen ervan géén nieuwe rangschikking op, terwijl

n!

ze wél als verschillend telt. Je telt zo te veel, en die overtelling moet je er weer uit delen. De algemene formule is

\frac{n!}{n_1!\,n_2!\cdots n_k!}

, waarbij

n

het totale aantal objecten is en

n_1, n_2, \ldots, n_k

aangeven hoe vaak elk verschillend object voorkomt. De teller

n!

telt alsof alles verschillend is; elke noemerfactor

n_i!

deelt de onderlinge verwisselingen van één groep identieke objecten weer weg.

Neem het woord BANAAN. Het bestaat uit zes letters, maar niet zes verschillende: de

A

komt drie keer voor, de

N

twee keer en de

B

één keer. Als alle zes de letters verschillend waren, zouden er

6! = 720

volgordes zijn. Maar de drie A's kun je onderling op

3! = 6

manieren verwisselen zonder dat het woord verandert, en de twee N's op

2! = 2

manieren. Elke zichtbare letterrij is daardoor

3! \cdot 2! = 12

keer meegeteld in die

720

. Het werkelijke aantal verschillende rijtjes is dus

\frac{6!}{3!\,2!\,1!} = \frac{720}{6 \cdot 2 \cdot 1} = \frac{720}{12} = 60

. Merk op dat

1!

voor de enkele

B

gewoon

1

is en dus niets verandert. Deze redenering — eerst tellen alsof alles verschillend is, dan de dubbeltellingen wegdelen — is precies dezelfde als bij de binomiaalcoëfficiënt.

In veel opgaven combineer je telwijzen. Een veelvoorkomend type kiest een groepje uit de ene groep én een groepje uit een andere groep. Stel: uit zes docenten en acht leerlingen wordt een commissie gevormd van twee docenten en drie leerlingen. De twee keuzes zijn onafhankelijk, dus reken je ze apart uit en vermenigvuldig je ze (vermenigvuldigingsregel). Het aantal manieren om twee docenten te kiezen is

\binom{6}{2} = 15

; het aantal manieren om drie leerlingen te kiezen is

\binom{8}{3} = 56

. Het totale aantal commissies is dan

\binom{6}{2} \cdot \binom{8}{3} = 15 \cdot 56 = 840

. Het sleutelwoord is „én”: de docenten én de leerlingen moeten allebei gekozen worden, en bij „én” hoort vermenigvuldigen. Let op dat je binnen elke groep eerst beslist of de volgorde meetelt — hier niet, dus combinaties — en pas daarna de deelaantallen met elkaar vermenigvuldigt.

Naast „én” kom je ook „of” tegen, en dat vraagt om optellen in plaats van vermenigvuldigen. Splits een telprobleem in gevallen die elkaar uitsluiten, reken elk geval apart uit en tel de aantallen op. Wil je bijvoorbeeld uit acht ballen een greep van drie waarin minstens twee rood zijn (er zijn drie rode en vijf witte), dan splits je in „precies twee rood” of „precies drie rood”. Het eerste geval is

\binom{3}{2} \cdot \binom{5}{1} = 3 \cdot 5 = 15

, het tweede

\binom{3}{3} \cdot \binom{5}{0} = 1 \cdot 1 = 1

, samen

15 + 1 = 16

. Onthoud de vuistregel: stappen achter elkaar („eerst dit én dan dat”) betekenen vermenigvuldigen; elkaar uitsluitende gevallen („dit óf dat”) betekenen optellen. Wie deze twee woorden — én, of — bewust vertaalt naar maal en plus, maakt van een samengesteld telprobleem een reeks kleine, controleerbare stappen.

Combinatoriek is in domein B niet het eindpunt maar het gereedschap voor de kansrekening. Bij een kansexperiment waarin alle uitkomsten even waarschijnlijk zijn, geldt de regel van Laplace: de kans op een gebeurtenis is het aantal gunstige uitkomsten gedeeld door het aantal mogelijke uitkomsten,

P = \frac{\text{aantal gunstige}}{\text{aantal mogelijke}}

. Beide aantallen tel je met de telwijzen uit dit hoofdstuk. Trek je bijvoorbeeld in één keer twee ballen uit een vaas met drie rode en vijf witte (acht in totaal), dan is het aantal mogelijke grepen

\binom{8}{2} = 28

en het aantal grepen met twee rode ballen

\binom{3}{2} = 3

. De kans op twee rode ballen is dus

\frac{\binom{3}{2}}{\binom{8}{2}} = \frac{3}{28}

. Zo wordt elk kansprobleem met „gelijke kansen” in feite een dubbel telprobleem: tel de gunstige uitkomsten, tel de mogelijke uitkomsten, en deel.

Het beslisschema hiernaast vat het hele hoofdstuk samen tot twee vragen. Telt de volgorde mee? Zo nee, dan is het een combinatie,

\binom{n}{r}

. Zo ja, mag er dan herhaald worden? Bij herhaling krijg je een variatie met herhaling,

n^r

; zonder herhaling een permutatie,

\frac{n!}{(n-r)!}

(of

n!

als je alle objecten rangschikt). Zijn sommige objecten identiek, dan corrigeer je met

\frac{n!}{n_1!\,n_2!\cdots}

. En bestaat een opgave uit meerdere keuzes achter elkaar, dan reken je elke keuze met het juiste schema uit en verbind je ze met maal („én”) of plus („of”). Met dit ene schema en de kerntelwijzen — permutaties, variaties, combinaties en permutaties met herhaling — los je vrijwel elk combinatorisch vraagstuk van het schoolexamen (SE) gestructureerd op, en heb je tegelijk het gereedschap in handen om kansen te berekenen.

\frac{n!}{n_1!\,n_2!\cdots n_k!}

permutaties met herhaling

Het aantal verschillende rangschikkingen van n objecten waarvan er groepen identiek zijn; n_i geeft aan hoe vaak object i voorkomt.

P = \frac{\text{aantal gunstige uitkomsten}}{\text{aantal mogelijke uitkomsten}}

kans (regel van Laplace)

Geldt bij even waarschijnlijke uitkomsten; teller en noemer tel je met de combinatoriek uit dit hoofdstuk.

Uitgewerkt voorbeeld

Een samengesteld telprobleem — combinatie × combinatie

Uit 6 docenten en 8 leerlingen wordt een commissie van 5 personen gevormd, die moet bestaan uit 2 docenten en 3 leerlingen. Bereken het aantal mogelijke commissies.

Stap 1 — Splits in onafhankelijke keuzes
Je kiest 2 docenten én 3 leerlingen. Binnen elke groep telt de volgorde niet, dus zijn het combinaties; het woord „én” betekent dat je de deelaantallen vermenigvuldigt.
Stap 2 — Tel de docenten
2 docenten kiezen uit 6, zonder volgorde: een combinatie van 2 uit 6.
$\binom{6}{2} = \frac{6 \cdot 5}{2 \cdot 1} = 15$
Stap 3 — Tel de leerlingen
3 leerlingen kiezen uit 8, zonder volgorde: een combinatie van 3 uit 8.
$\binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56$
Stap 4 — Vermenigvuldig de deelaantallen
Bij elke keuze van 2 docenten horen alle 56 keuzes van 3 leerlingen, dus vermenigvuldig je de twee aantallen.
$\binom{6}{2} \cdot \binom{8}{3} = 15 \cdot 56 = 840$

Resultaat: Er zijn 840 mogelijke commissies. De twee groepen worden onafhankelijk gekozen, dus vermenigvuldig je de deelaantallen; binnen elke groep telt de volgorde niet, vandaar de combinaties.

Veelgemaakte fouten

Bij identieke objecten gewoon n! nemen; je moet delen door de faculteit van elke groep gelijke objecten, anders tel je veel te veel.
„Én” en „of” verwisselen: keuzes achter elkaar („én”) vermenigvuldig je, elkaar uitsluitende gevallen („of”) tel je op.

Actieve herhaling

(a) Hoeveel verschillende letterrijtjes kun je maken met alle letters van het woord STELLING? (b) Uit 5 jongens en 7 meisjes wordt een groepje van 2 jongens en 2 meisjes gekozen; bereken het aantal mogelijke groepjes en leg uit waarom je de deelaantallen vermenigvuldigt.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma wiskunde D (HAVO) (CvTE / Examenblad)

Referenties en bronnen

Bronnen

CvTE / Examenblad

Examenprogramma wiskunde D (HAVO)

Combinatoriek

Kernpunten

Een code tellen — met en zonder herhaling

Kernpunten

Rangschikken: alle objecten én een deel

Kernpunten

Een groepje kiezen — met getalcontrole

Kernpunten

Een samengesteld telprobleem — combinatie × combinatie

Bronnen