Combinaties

Combinaties gebruiken we als we uit een verzameling objecten een bepaald aantal objecten kiezen, waarbij de volgorde waarin we ze kiezen er niet toe doet. Een typisch voorbeeld is een loterij 6 uit 49: in de vaas zitten 49 getallen en we trekken er 6, waarbij het niet uitmaakt in welke volgorde we ze trekken.

Afleiding van de formule

Rad van fortuin

Neem een verzameling M, bijvoorbeeld M = {a, b, c, d, e}. Een combinatie van k elementen is dan een deelverzameling K ⊆ M die precies k elementen bevat. Omdat K een verzameling is, doet de volgorde vanzelfsprekend niet ter zake. Een combinatie van drie elementen uit de verzameling M zou dus {a, b, d} of {b, c, d} kunnen zijn.

Het verschil met variaties is dat bij variaties de volgorde wel telde, dus (a, b, e) en (e, b, a) zijn verschillende variaties, maar het zijn dezelfde combinaties, want (a, b, e) en (e, b, a) bevatten dezelfde elementen. Dat ze in een andere volgorde staan, interesseert ons bij combinaties niet.

We kunnen de variaties wel gebruiken om de formule voor het aantal verschillende combinaties af te leiden. We weten dat het aantal variaties van k elementen uit een verzameling van n elementen precies

$\frac{n!}{(n - k)!}$

is (het aantal permutaties van k uit n). Als we het aantal variaties van drie elementen uit de verzameling M = {a, b, c, d, e} van zonet berekenen, krijgen we $\frac{5!}{(5 - 3)!} = 60$ verschillende variaties. Maar dan hebben we bij elk drietal ook al zijn permutaties meegeteld. We hebben dus het drietal abc, maar ook de drietallen acb, bac, bca, cab en cba. Dat zijn zes verschillende variaties, maar het is één combinatie, omdat ze allemaal dezelfde elementen hebben.

Als we dus een bepaald drietal hebben, hoeveel verschillende permutaties van dit drietal bestaan er dan? Precies 3!. Met andere woorden: er zijn precies 3! keer zoveel variaties van drie elementen als combinaties van drie elementen. In plaats van één combinatie tellen we 3! variaties, namelijk elke permutatie van het gegeven drietal. Als we het aantal variaties delen door 3!, krijgen we dus het aantal combinaties.

Deze redenering kunnen we generaliseren. Als we het aantal van alle verschillende combinaties van k elementen uit een verzameling van n elementen zoeken, dan is dat aantal, dat we $(\binom{n}{k})$ noteren (hierover zo meer), gelijk aan

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

dus het aantal variaties gedeeld door k!, het aantal permutaties van elk k-tal. De formule kunnen we vereenvoudigen door de formule voor het aantal variaties uit te schrijven:

$(\binom{n}{k}) = \frac{\frac{n!}{(n - k)!}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Voorbeeld: het aantal combinaties van twee elementen uit de verzameling {a, b, c} is

$(\binom{3}{2}) = \frac{3!}{1! \cdot 2!} = 3$

en het zijn deze combinaties: {a, b}, {a, c} en {b, c}. Bij de combinaties van drie elementen uit de oorspronkelijke verzameling M = {a, b, c, d, e} zouden we het aantal

$(\binom{5}{3}) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

krijgen en het zijn deze combinaties: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

De binomiaalcoëfficiënt

De schrijfwijze met een breuk is wat omslachtig. Daarom gebruiken we de zogenoemde binomiaalcoëfficiënt. Die heeft deze vorm

$(\binom{n}{k})$

en je kunt hem zien als een breuk zonder breukstreep (die je er uit gewoonte toch bij zult schrijven), maar met haakjes (die zijn niet optioneel, die moeten er staan). We spreken de binomiaalcoëfficiënt uit als “n boven k”. Zijn waarde is hetzelfde als het aantal combinaties van k uit n:

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

Als we dus een verzameling van 5 elementen hebben en we kiezen daaruit viertallen, dan is hun totale aantal

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Op je rekenmachine tik je dit in als 5 nCr 4 en in Excel als =COMBINATIES(5; 4) (Engels: COMBIN).

Basisrelaties

Voor de binomiaalcoëfficiënt en n ∈ ℕ geldt:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Verder geldt voor n, k ∈ ℕ₀ en k ≤ n

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

En voor n, k ∈ ℕ₀ en k < n geldt

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Rekenmachine

De volgende rekenmachine berekent de binomiaalcoëfficiënt n boven k.

Uitgewerkte voorbeelden

We beginnen met de al genoemde loterij 6 uit 49. Daarbij worden uit een vaas met 49 balletjes in totaal 6 balletjes getrokken. Hoeveel verschillende uitkomsten kunnen er worden getrokken?

Allereerst: doet de volgorde van het trekken van de getallen ertoe? Nee, we kiezen alleen de getallen, niet hun volgorde. We gebruiken dus combinaties. We hebben 49 balletjes en we trekken er 6, dus we krijgen de binomiaalcoëfficiënt

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13 983 816$

Er zijn dus in totaal 13 983 816 mogelijke uitkomsten van de trekking. Dat geeft ons trouwens de kans om met één inzet te winnen: 1/13 983 816, en dat is 0,00000715112%.
Daan is op een schoolfeest waar 13 leuke klasgenoten zijn met wie hij graag zou dansen. Daan weet dat hij op één avond met 4 verschillende klasgenoten kan dansen. Uit hoeveel verschillende viertallen kan Daan kiezen?

Dit is weer een eenvoudig voorbeeld over combinaties: de volgorde doet er niet toe, want Daan danst met de eerste even goed als met de laatste. We hebben dus een verzameling van 13 klasgenoten, waaruit we steeds 4 kiezen. Dat leidt tot de binomiaalcoëfficiënt

$(\binom{13}{4}) = 715.$
Je hebt een groep van vijftig mensen, de helft mannen en de helft vrouwen. Hoeveel verschillende drietallen mensen zijn er als ze niet allemaal van hetzelfde geslacht mogen zijn (dus er mogen niet drie mannen of drie vrouwen in het drietal zitten)?

Dit is een iets lastigere combinatie. Als we de drietallen van één geslacht uitsluiten, blijven er maar twee mogelijkheden over voor de samenstelling van het drietal: twee mannen en één vrouw, of één man en twee vrouwen, waarbij het aantal combinaties van de eerste groep (twee mannen en één vrouw) gelijk is aan het aantal combinaties van de tweede groep. Het is dus genoeg om het aantal combinaties van de eerste groep te berekenen en dat daarna met twee te vermenigvuldigen. Nu is het weer een koud kunstje. We bepalen het aantal combinaties van verschillende tweetallen mannen, en dat is 25 boven 2, en vermenigvuldigen dat met het aantal combinaties van één vrouw (dat is 25, zie de basisrelaties hierboven, namelijk de tweede regel). Dit resultaat vermenigvuldigen we ten slotte met twee en we hebben het eindresultaat.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
In een doos zitten 15 producten, waarvan er 4 defect zijn. Op hoeveel manieren kunnen we 6 producten kiezen zodat
- geen enkel product defect is? Dan kiezen we 6 producten uit de 15 − 4 = 11 producten die niet defect zijn. We krijgen dus de binomiaalcoëfficiënt
  
  $(\binom{11}{6}) = 462.$
- precies één product defect is? We kiezen dan een verzameling die 5 werkende producten en 1 defect product bevat. Er zijn in totaal 11 werkende en 4 defecte producten. We gebruiken de vermenigvuldigingsregel en krijgen het resultaat:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- hoogstens één product defect is? Om dit op te lossen gebruiken we de vorige resultaten. We weten dat er 462 mogelijkheden zijn om precies 6 werkende producten te kiezen en 1848 mogelijkheden om vijf werkende en één defect product te kiezen. We gebruiken dus de somregel, tellen deze resultaten op en hebben het gevraagde resultaat, dus hoogstens één defect product (= of geen enkel defect product, of precies één). Het resultaat is dus: 462 + 1848 = 2310.

Hoofdstukken: Combinatoriek, Variaties, Permutaties, Combinaties, Variaties met herhaling, Combinaties met herhaling, Hoeveel verschillende pincodes zijn er?

« Vorige: Permutaties

Volgende: Variaties met herhaling »