Permutaties en combinaties: waarom de volgorde de uitkomst verandert

Vijf mensen melden zich vrijwillig voor een project. Je hebt een voorzitter en een plaatsvervanger nodig. Kies de voorzitter op vijf manieren en daarna de plaatsvervanger op vier manieren. Er zijn twintig toewijzingen.

Verander nu één zin: je hebt een commissie van twee mensen nodig, zonder afzonderlijke rollen. Dezelfde vijf mensen leveren tien commissies op. Aan de mensen veranderde niets. De definitie van een uitkomst veranderde.

Permutaties en combinaties zijn twee manieren om uitkomsten te tellen zonder elke mogelijkheid op te sommen. De formules worden logisch zodra je bepaalt welke informatie de uitkomst bewaart. Dit artikel bouwt eerst die beslissing op en leidt daarna de notatie af.

Begin met posities, niet met een formule

Stel je twee lege vakken voor met de labels voorzitter en plaatsvervanger. Het eerste vak heeft vijf mogelijke personen. Nadat je het hebt ingevuld, blijven vier mensen over voor het tweede. Elke eerste keuze heeft vier vervolgmogelijkheden, dus:

$$5 \times 4 = 20$$

Dit is het vermenigvuldigingsprincipe. Als elke optie in een stap hetzelfde aantal mogelijke vervolgen heeft, vermenigvuldig je de aantallen per stap. Je kunt een boom voor je zien met vijf takken, die elk weer in vier takken splitsen.

De labels tellen. Alex als voorzitter en Bea als plaatsvervanger is anders dan Bea als voorzitter en Alex als plaatsvervanger. Het zijn dezelfde mensen op verschillende posities. Dat is een geordende selectie, een permutatie.

Een commissie heeft geen gelabelde posities. Alex, Bea of Bea, Alex beschrijft dezelfde groep. Gebruik je de telling van twintig toewijzingen voor commissies, dan heb je elke groep tweemaal geteld.

De verwisseltest laat zien of de volgorde telt

Vraag: krijg ik een andere uitkomst als ik twee gekozen elementen verwissel?

Bij het podium van een race wel. Goud en zilver zijn verschillende uitslagen. Bij een verzameling pizzabeleg meestal niet. Champignons met olijven is dezelfde keuze als olijven met champignons.

De vraag gaat over het model, niet over het zelfstandig naamwoord. Een opgave kan vragen om drie boeken te kiezen om te kopen, waarbij de volgorde niet telt, of drie boeken op een plank te zetten, waarbij de volgorde wordt vastgelegd. Het woord ‘boeken’ vertelt je niet welke formule van toepassing is.

Schrijf vóór het rekenen een voorbeelduitkomst op. ‘Voorzitter Alex, plaatsvervanger Bea’ bevat rollen. ‘De groep met Alex en Bea’ niet. Deze kleine stap voorkomt meer fouten dan het uit het hoofd leren van een langer formuleblad.

Situatie	Wat de uitkomst vastlegt	Model
Goud, zilver en brons toekennen	Persoon op elke plaats	Geordend, zonder herhaling
Drie commissieleden kiezen	Alleen lidmaatschap	Ongeordend, zonder herhaling
Een code van vier cijfers maken	Cijfer op elke positie	Geordend, herhaling kan toegestaan zijn
Meerdere bolletjes ijs kiezen	Aantallen per smaak	Ongeordend, herhaling kan toegestaan zijn

Bij de laatste twee rijen moet je ook naar herhaling vragen. Beslis niet alleen op basis van de volgorde.

Faculteiten tellen volledige ordeningen

Zet vier verschillende boeken op een rij. Er zijn vier keuzes voor de eerste plaats, drie voor de tweede, twee voor de derde en één voor de laatste:

$$4! = 4 \times 3 \times 2 \times 1 = 24$$

Het uitroepteken betekent faculteit. Het kort het aflopende product af. Voor een niet-negatief geheel getal $n$ telt de faculteit de ordeningen van alle $n$ verschillende elementen.

Waarom is $0! = 1$? Er bestaat één lege ordening. Je doet niets en de lege ordening is compleet. Dit is ook de waarde die $1! = 1 \times 0!$ consistent houdt.

Lees een faculteit niet als herhaalde optelling of als een macht. Vier faculteit is vierentwintig; vier tot de vierde macht is tweehonderdzesenvijftig. Bij een faculteit neemt het aantal keuzes af omdat je een element niet opnieuw mag gebruiken. Bij een macht blijft het aantal keuzes constant.

Permutaties stoppen het product eerder

Stel dat er zeven hardlopers zijn en je alleen de eerste drie finishers wilt weten, zonder gelijke eindstanden. Je hebt zeven keuzes voor de eerste plaats, zes voor de tweede en vijf voor de derde:

$$P(7,3) = 7 \times 6 \times 5 = 210$$

Het maakt niet uit hoe de overige vier hardlopers eindigen. Helemaal tot één vermenigvuldigen zou een andere vraag beantwoorden.

Voor $r$ geordende posities die zonder herhaling uit $n$ verschillende elementen worden gevuld:

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

De noemer schrapt de ongebruikte staart van de faculteit. In het voorbeeld van de hardlopers blijft na het delen van zeven faculteit door vier faculteit precies zeven maal zes maal vijf over.

Deze formule veronderstelt $0 \le r \le n$ en verschillende beschikbare elementen. Verandert de opgave die aannames, ga dan terug naar de vakken in plaats van de getallen in de uitdrukking te dwingen.

Combinaties verwijderen dubbele ordeningen

Kies drie van de zeven mensen voor een commissie. De geordende telling is 210, maar behandelt verschillende ordeningen van hetzelfde drietal als verschillende antwoorden.

Neem één drietal: Alex, Bea en Chen. De leden kunnen in zes volgordes worden vermeld: ABC, ACB, BAC, BCA, CAB en CBA. Elk drietal komt precies zes keer in de geordende telling voor, want $3! = 6$.

Deel door het aantal dubbele ordeningen:

$$\binom{7}{3} = \frac{210}{6} = 35$$

In het algemeen:

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

Lees dit als ‘n boven r’. De eerste deling verwijdert ongebruikte elementen uit het aantal ordeningen; de tweede verwijdert volgordes die je niet meer onderscheidt.

Hier zit een nuttige symmetrie in: $\binom{7}{3} = \binom{7}{4}$. De drie mensen kiezen die deelnemen, wijst ook de vier aan die niet deelnemen. De twee beschrijvingen verwijzen naar dezelfde reeks beslissingen.

Herhaling verandert de vraag opnieuw

Een code van vier cijfers mag op elke positie elk cijfer van nul tot en met negen gebruiken, ook aan het begin. Herhaalde cijfers zijn toegestaan. Elk vak heeft tien keuzes:

$$10^4 = 10000$$

Als geen enkel cijfer mag worden herhaald, wordt de telling:

$$10 \times 9 \times 8 \times 7 = 5040$$

Als de opgave ‘getal van vier cijfers’ zegt in plaats van ‘code’, wordt een nul aan het begin normaal uitgesloten. Met herhaling toegestaan geeft dat:

$$9 \times 10 \times 10 \times 10 = 9000$$

Drie sterk gelijkende zinnen, drie verschillende aantallen. De formule werd niet onbetrouwbaar. De beperkingen veranderden.

Ongeordende selectie met herhaling, zoals bolletjes ijs kiezen waarbij smaken mogen terugkomen, vereist een andere telmethode. Gewone combinaties veronderstellen dat elk beschikbaar element hoogstens eenmaal kan worden gekozen. Herkennen dat een bekende formule niet geldt, is een juiste eerste stap.

Doorloop de beslissing in deze volgorde

Schrijf vóór het rekenen op hoe één volledige uitkomst eruitziet. Vraag daarna of volgorde of rollen uitkomsten onderscheiden, of een element mag worden herhaald en of er voor een positie een bijzondere beperking geldt.

Probeer deze drie opgaven zonder meteen naar de antwoorden te kijken:

1. Kies uit zes mensen een voorzitter en een secretaris, waarbij niemand beide rollen heeft.
2. Kies uit dezelfde zes mensen twee vertegenwoordigers met een gelijke status.
3. Maak met vier symbolen een code van drie tekens, waarbij herhaling is toegestaan.

De eerste heeft $6 \times 5 = 30$ toewijzingen. Bij de tweede deel je dat aantal door $2!$, wat vijftien paren oplevert. De derde heeft $4^3 = 64$ codes, omdat alle vier symbolen op elke positie beschikbaar blijven.

De uitleg is belangrijker dan het getal. Als je kunt uitleggen waarom je bij het ene antwoord door twee deelt en bij het andere niet, begrijp je het onderscheid.

Tellen is de basis van kansrekening

Als je even waarschijnlijke uitkomsten correct telt, kun je kansen vormen door gunstige uitkomsten met alle mogelijke uitkomsten te vergelijken. Onze intuïtieve gids over kansrekening zet die volgende stap. De verjaardagsparadox laat zien hoe een zorgvuldig gekozen telling een verrassend resultaat hanteerbaar maakt.

Houd de vaardigheid voorlopig klein: definieer een uitkomst, teken eventuele posities en leg elke factor uit. Gebruik de kansoefeningen van Math Zen voor de volgende toepassing en keer terug naar een klein voorbeeld zodra de notatie de redenering begint te verbergen.

Een permutatie bewaart de ordening. Een combinatie bewaart het lidmaatschap. Delen door een faculteit is simpelweg de ordening vergeten zonder dezelfde groep opnieuw te tellen.