Combinatoriek

Wil je weten hoeveel verschillende groepjes van vijf kaarten je uit een spel van 32 kaarten kunt kiezen? Dat is precies het soort opgave dat de combinatoriek oplost. Er zijn twee basisregels in de combinatoriek: de somregel en de vermenigvuldigingsregel. Alle andere methoden zijn slechts uitbreidingen van deze twee principes.

De somregel

De somregel is heel eenvoudig. Als we twee verzamelingen A, B hebben zonder gemeenschappelijk element, dan is het aantal manieren om één element uit de vereniging A ∪ B te kiezen gelijk aan |A| + |B|, dus aan de som van de aantallen elementen van de verzamelingen.

We beginnen met een makkelijk voorbeeld. We hebben 6 rode en 8 blauwe knikkers. Die doen we samen in één vaas. Hoeveel mogelijkheden hebben we als we één knikker trekken? Aan het begin hadden we de verzameling rode knikkers, die we A noemen, en de verzameling blauwe knikkers, die we B noemen. Deze verzamelingen zijn disjunct, dus er is geen knikker die in allebei zit. We willen één knikker trekken, dus we hebben in totaal |A| + |B| = 6 + 8 = 14 mogelijkheden. Dat is alles.

De vermenigvuldigingsregel

We hebben weer twee verzamelingen, V en M. Verzameling V bevat drie vrouwen en verzameling M vier mannen. Nu vragen we ons af hoeveel verschillende paren van een man en een vrouw we met deze verzamelingen kunnen maken. We doen het zo: we nemen steeds één vrouw en kiezen er een man bij. Het aantal paren tellen we als volgt: we nemen één vrouw, Emma, en koppelen er na elkaar alle mannen aan. Zo krijgen we 4 verschillende paren, want we kunnen haar aan 4 verschillende mannen koppelen. Hetzelfde doen we voor de twee andere vrouwen, ook zij vormen telkens weer 4 paren. En dat is alles, we hebben in totaal 4 + 4 + 4 = 12 paren.

Wat hebben we eigenlijk gedaan? We hebben de aantallen elementen van beide verzamelingen met elkaar vermenigvuldigd. We hadden 3 vrouwen en 4 mannen, dus het totale aantal paren is 3 · 4 = 12. Vandaar de vermenigvuldigingsregel. Als we dus twee verzamelingen hebben waaruit we paren vormen, vermenigvuldigen we gewoon het aantal elementen van de ene verzameling met het aantal elementen van de andere.

Hieronder kun je zien dat dit echt klopt. Dit zijn alle paren die we met 3 vrouwen en 4 mannen kunnen maken. Elke rij laat de mogelijkheden zien voor één van de vrouwen en elke kolom de mogelijkheden voor één van de mannen. We hebben dus drie rijen en vier kolommen, samen rijen · kolommen mogelijkheden.

$$\begin{array}{rcl}& & (V_1,M_1),(V_1,M_2),(V_1,M_3),(V_1,M_4),\\ & & (V_2,M_1),(V_2,M_2),(V_2,M_3),(V_2,M_4),\\ & & (V_3,M_1),(V_3,M_2),(V_3,M_3),(V_3,M_4)\end{array}$$

Uitgewerkte voorbeelden

1. Hoeveel verschillende tweecijferige getallen zijn er? Hoe ziet zo'n tweecijferig getal eruit? Op de eerste plaats staat een van de cijfers 1, …, 9, terwijl op de tweede plaats ook een nul kan staan: 0, …, 9. In de eerste verzameling hebben we dus 9 cijfers, in de tweede 10. We gebruiken de vermenigvuldigingsregel en krijgen het eindresultaat: 9 · 10 = 90.
2. Hoeveel verschillende driecijferige getallen zijn er waarin geen enkel cijfer twee keer voorkomt? Op de eerste plaats kunnen weer negen cijfers staan, want een getal begint niet met een nul. Op de tweede plaats mogen alle cijfers staan, ook de nul, maar niet het cijfer dat op de eerste plaats staat. Daarom trekken we één af van de tien mogelijke cijfers (als ons driecijferige getal bijvoorbeeld met een 4 begint, kan er op de tweede plaats geen 4 meer staan, want dan zou het cijfer twee keer in het getal voorkomen). Op de derde plaats mogen weer alle cijfers staan, maar niet het cijfer van de eerste of van de tweede plaats. De reden is dezelfde. Als op de eerste plaats een 4 staat en op de tweede een 7, dan kunnen we op de derde plaats een cijfer uit {0, …, 9} ∖ {4, 7} invullen. Van de tien cijfers moeten we er dus twee aftrekken. Nu vermenigvuldigen we nog: 9 · 9 · 8 = 648. In totaal zijn er dus 648 van zulke getallen.
3. We gooien twee keer na elkaar met een gewone dobbelsteen. Hoeveel verschillende uitkomsten kunnen we krijgen? Bij de eerste worp kunnen 6 verschillende uitkomsten vallen. Bij de tweede worp ook, dus het totale aantal mogelijkheden is 6 · 6 = 36.
4. We gooien twee keer na elkaar met een dobbelsteen. Hoeveel verschillende uitkomsten kunnen we krijgen als we bij de eerste worp een even getal gooiden? Bij de eerste worp viel een even getal, dus een van de getallen 2, 4, 6, en dat zijn 3 mogelijkheden. Bij de tweede worp kan elk getal vallen, dus in totaal hebben we 3 · 6 = 18 mogelijkheden.