17. One of a Billion Weeks – LAb[au]

12.
LAb[au] (BE)

One of a Billion Weeks

Teksten door Jean Rosenfeld & Raoul Sommeillier

Bij een willekeurige trekking in verschillende stappen is het vaak nuttig om het aantal mogelijke resultaten te bepalen. Daarvoor kunnen bepaalde teltechnieken worden gebruikt.

In de combinatieleer bestaat het ‘tellen’ er dus in het aantal mogelijke resultaten te berekenen bij een willekeurige trekking met verscheidene stappen.

We belichten hier kort de basisteltechnieken voor drie fundamentele concepten binnen de combinatieleer: permutatie, herhalingsvariatie en combinatie.

1. Permutatie

In de wiskunde staat het concept van permutatie voor de herschikking van waarneembare objecten. Een permutatie van waarneembare objecten gerangschikt in een bepaalde volgorde stemt overeen met de wijziging van die volgorde van de objecten.

De permutatie van een verzameling is dus de herschikking van alle elementen in die verzameling.

Twee permutaties van eenzelfde verzameling verschillen dus van elkaar door een verschillende volgorde van alle elementen waaruit ze zijn opgemaakt.

Zo zijn de mogelijke permutaties van een verzameling van de cijfers 1 tot 3 \(\left\{1, 2, 3\right\}\) de volgende:

(1, 2, 3)
(1, 3, 2)

(2, 1, 3)
(2, 3, 1)

(3, 1, 2)
(3, 2, 2)

Aangezien telkens alle elementen in de verzameling gebruikt moeten worden, spreken we hier van een willekeurige trekking zonder teruglegging. We komen later op dit concept terug.

Het aantal mogelijke permutaties van een verzameling met \(n\) verschillende elementen wordt als volgt berekend:

\[P_n=n!=n\times (n-1)\times (n-2)\times …\times 3\times 2\times 1\]

Voorbeeld

We halen vier knikkers uit een zak met één rode knikker \((R)\), één blauwe knikker \((B)\), één oranje knikker \((O)\) en één groene knikker \((G)\). Dan zijn de mogelijke volgordes waarmee we de knikkers uit de zak kunnen halen:

\((R, B, O, G)\)
\((R, B, G, O)\)
\((R, O, B, G)\)
\((R, O, O, B)\)
\((R, G, G, O)\)
\((R, G, B, B)\)

\((B, R, O, G)\)
\((B, R, G, O)\)
\((B, O, R, G)\)
\((B, O, G, R)\)
\((B, G, R, O)\)
\((B, G, O, R)\)

\((O, R, B, G)\)
\((O, R, G, B)\)
\((O, B, R, G)\)
\((O, B, G, R)\)
\((O, G, R, B)\)
\((O, G, B, R)\)

\((G, R, B, O)\)
\((G, R, O, B)\)
\((G, B, R, O)\)
\((G, B, O, R)\)
\((G, O, R, B)\)
\((G, O, B, R)\)

Er zijn dus 24 permutaties van deze verzameling mogelijk.

Om de berekening van permutaties eenvoudiger te maken, volstaat het om het aantal mogelijke elementen per trekking met elkaar te vermenigvuldigen. In dit geval is die berekening \(4\times 3 \times 2 \times 1 = 24\). Aanvankelijk hebben we inderdaad de keuze uit \(n=4\) elementen. Daarna zijn nog slechts 3 elementen beschikbaar, want één element is al getrokken (en wordt niet teruggelegd). Vervolgens blijven nog slechts 2 elementen over, en tot slot slechts 1 element.

We kunnen de voorgaande formule ook noteren als de faculteit van het aantal elementen in de verzameling:

\[n!=4!=4\times 3 \times 2 \times 1 = 24\]

2. Herhalingsvariatie

De herhalingsvariatie van een verzameling elementen is een geordende keuze van een specifiek aantal elementen uit die verzameling.

Het gaat dus om een gelijkaardige situatie als bij permutatie, zij het dat de geordende keuze minder elementen bevat dan het totale aantal beschikbare elementen ((\(k>n\))).

Als we bijvoorbeeld alle mogelijke samenstellingen van \(k=4\) van de \(n=26\) letters van het alfabet willen achterhalen, kunnen we bijvoorbeeld de samenstellingen \(ABCD\) of \(ADCB\) terugvinden. Het gaat hier wel degelijk om afzonderlijke geordende keuzes aangezien zij dezelfde letters bevatten, zij het in een andere volgorde.

De berekening van het aantal mogelijke volgordes verschilt naargelang de keuze voor een trekking met of zonder teruglegging. In een trekking zonder teruglegging mogen we elk van de  beschikbare elementen slechts één keer selecteren. In een trekking met teruglegging mogen we elk van de  beschikbare elementen meer dan één keer selecteren.

Wanneer \(n\) het aantal elementen in een verzameling voorstelt en \(k\) het aantal geselecteerde elementen in die verzameling, dan kunnen we het aantal mogelijke herhalingsvariaties berekenen met de volgende formules:

Voor een trekking zonder teruglegging

Voor een trekking met teruglegging

\[A_n^k=\frac{n!}{(n-k)!}\]

\[A_n^k=n^k\]

De tweede formule stemt overeen met de formule uit het voorgaande niveau, waarmee we het aantal mogelijke resultaten hebben berekend voor onze opstellingen met lampen en met het schermpje uit het werk One of a Billion Weeks van LAb[au].

Voorbeeld

We kiezen 4 willekeurige letters uit de verzameling \(\left\{D,E,F,G\right\}\).
Als we deze trekking uitvoeren zonder teruglegging, dan kunnen we uit 4 letters trekken bij de eerste trekking, uit 3 letters bij de tweede trekking (aangezien 1 letter al werd getrokken bij de eerste trekking). De volgende samenstellingen zijn mogelijk:

\((D,E) (D,F) (D,G)\)

\((E,D) (E,F) (E,G)\)

\((F,D) (F,E) (F,G)\)

\((G,D) (G,E) (G,F)\)

Er zijn in totaal dus 12 resultaten mogelijk.
We kunnen het ‘tellen’ van de mogelijke resultaten vereenvoudigen door het aantal mogelijke elementen bij elke trekking te vermenigvuldigen: \(4\times 3=12\) mogelijke samenstellingen.

Met de formule waarin \(n=4\) (het aantal beschikbare letters) en \(k=2\) (het aantal te trekken letters), voeren we de berekening uit: \(A_n^k=\frac{n!}{(n-k)!}=A_4^2=\frac{4!}{(4-2)!}=12\) mogelijke samenstellingen.

Als we deze trekking uitvoeren met teruglegging, dan kunnen we uit 4 letters trekken bij de eerste trekking, en opnieuw uit 4 letters bij de tweede trekking (aangezien elke letter meerdere keren getrokken kan worden). De volgende samenstellingen zijn mogelijk:

\((D,D)\)
\((D,E)\)
\((D,F)\)
\((D,G)\)

\((E,D)\)
\((E,E)\)
\((E,F)\)
\((E,G)\)

\((F,D)\)
\((F,E)\)
\((F,F)\)
\((F,G)\)

\((G,D)\)
\((G,E)\)
\((G,F)\)
\((G,G)\)

Er zijn in totaal dus 16 resultaten mogelijk.
We kunnen het ‘tellen’ van de mogelijke resultaten vereenvoudigen door het aantal mogelijke elementen bij elke trekking te vermenigvuldigen: \(4 \times 4 = 16\) mogelijke herhalingsvariaties.

Met de formule waarin \(n=4\) en \(k=2\), voeren we de berekening uit: \(A_n^k=n^k=A_4^2=16\) mogelijke samenstellingen.

3. Combinatie

De combinatie van elementen uit een verzameling is een ongeordende keuze van een specifiek aantal elementen uit die verzameling.

In tegenstelling tot herhalingsvariaties, gaat het bij combinaties om een keuze van elementen waarbij geen rekening wordt gehouden met de plaats van die elementen naargelang hun volgorde van trekking. Een voorbeeld: een trekking levert de ballen \(a\), \(b\) en \(c\) op. In het geval van een combinatie, betekent dit dat ook \(abc\) en \(acb\) resultaten zijn van diezelfde trekking. Er zijn bijgevolg minder combinaties mogelijk dan herhalingsvariaties.

Ook hier verschilt de berekening van het aantal mogelijke combinaties naargelang de keuze voor een trekking met of zonder teruglegging.

Wanneer \(n\) het aantal elementen in een verzameling voorstelt en \(k\) het aantal geselecteerde elementen uit die verzameling, dan kunnen we het aantal mogelijke combinaties berekenen met de volgende formules:

Voor een trekking zonder teruglegging

Voor een trekking met teruglegging

\(C_n^k=\frac{Het\ aantal\ mogelijke\ samenstellingen}{Het\ aantal\ mogelijke\ permutaties\ van\ elke\ samenstelling}\)
\(C_n^k=\frac{A_n^k}{P_n^k}=\frac{n!}{k!\times (n-k)!}\)

\(C_n^k=\frac{(n+k-1)!}{k!\times (n-1)!}\)

Voorbeeld

We trekken 3 willekeurige knikkers uit een zak met 4 knikkers: een rode knikker (\(R\)), een blauwe knikker (\(B\)), een oranje knikker (\(O\)) en een groene knikker (\(G\)). Het aantal beschikbare elementen is hier dus \(n=4\), en het aantal getrokken elementen is hier \(k=3\).

Eenmaal een knikker is getrokken, kan die geen tweede keer getrokken worden (de knikker wordt niet opnieuw in de zak gestopt). Het gaat hier dus om een proef zonder teruglegging.

Als we willen bepalen hoeveel combinaties er mogelijk zijn, moeten we hier dus geen rekening houden met de volgorde waarin we de knikkers trekken.

We vinden het aantal mogelijke combinaties door het aantal herhalingsvariaties te berekenen én het aantal permutaties van elk van die herhalingsvariaties:

\[C_n^k=\frac{Het\ aantal\ mogelijke\ samenstellingen}{Het\ aantal\ mogelijke\ permutaties\ van\ elke\ samenstelling}\]

Om het aantal mogelijke herhalingsvariaties te achterhalen, kunnen we de eerder aangegeven formule \(A_4^3=\frac{4!}{(4-1)!}=24\), gebruiken, of de herhalingsvariaties oplijsten (rekening houdend met de volgorde waarin de knikkers getrokken worden):

\((R, B, O)\)
\((R, B, G)\)
\((R, O, B)\)
\((R, O, B)\)
\((R, O, G)\)
\((R, V, O)\)

\((B, R, O)\)
\((B, R, G)\)
\((B, O, R)\)
\((B, O, G)\)
\((B, G, R)\)
\((B, G, O)\)

\((O, R, B)\)
\((O, R, G)\)
\((O, B, R)\)
\((O, B, G)\)
\((O, G, R)\)
\((O, G, B)\)

\((G, R, B)\)
\((G, R, O)\)
\((G, B, R)\)
\((G, B, O)\)
\((G, O, R)\)
\((G, O, B)\)

Om het aantal mogelijke permutaties voor elke herhalingsvariatie te bepalen, volstaat het als we weten dat elke herhalingsvariatie \(k=3\) elementen bevat. Met de formule die we eerder al vermeldden, krijgen we dus \(P_3=3 !=3×2×1=6\).
We kunnen ook al snel vaststellen, dankzij de kleuren die we aanbrachten in onze lijst van herhalingsvariaties, dat er zes verschillende mogelijkheden zijn om drie knikkers te trekken wanneer we rekening houden met de volgorde. Zo zijn de mogelijke permutaties met rode, blauwe en oranje knikkers bijvoorbeeld: \((R,B,O)\), \((R,O,B)\), \((B,R,O)\), \((B,O,R)\), \((O,R,B)\), en \((O,B,R)\).

Daaruit kunnen we afleiden dat er vier combinaties mogelijk zijn: \(C_4^3=\frac{A_4^3}{P_3}=\frac{24}{6}=4\).
Namelijk:

\((R, B, O)\)

\((R, B, G)\)

\((O, B, G)\)

\((O, G, R)\)

We hadden dit aantal combinaties ook kunnen berekenen met de formule in het bovenstaand kadertje, waarin \(n=4\) en \(k=3\) :

\[Aantal\ mogelijke\ combinaties = C_4^3=\frac{4!}{3!\times(4-3)!}=\frac{4!}{3!\times 1!}=\frac{24}{6}=4\]

Als we de trekking uitvoeren met teruglegging (dus met de mogelijkheid om dezelfde knikker meerder malen te trekken), dan wordt het aantal mogelijke combinaties met de volgende formule berekend: \(C_n^k=\frac{(n+k-1)!}{k!\times (n-1)!}\).

Wat voor \(n=4\) en \(k=3\) het volgende oplevert:

\[C_4^3=\frac{(4+3-1)!}{3! (4-1)!}=\frac{6!}{3!\times 3!}=\frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (3 \times 2 \times 1)}=\frac{720}{36}=20\]

De berekening van het aantal mogelijke combinaties is een vaardigheid die bij het gokken en wedden goed van pas kan komen. Het kan een heuse troef zijn voor wie het aantal mogelijkheden kan berekenen net als de kansen om bijvoorbeeld een specifieke combinatie van kaarten te krijgen en die te toetsen aan de kansen van de andere spelers.

In die situatie is de volgorde van de kaarten niet van belang, wel hun combinatie. De formule voor combinaties uit de combinatieleer is hier dus van toepassing.

Pagina’s: 1 2 3