Kombinatorik

Kombinatorik er et emne inden for sandsynlighedsregning, hvor man arbejder med at tælle kombinationer. Der er mange opgaver, der bruger kombinatorik og vi vil bruge eksempler til at vise teorien.

Hvis man for eksempel har penge til at købe fem stykker chokolade, og der er tolv forskellige slags chokolade, på hvor mange forskellige måder kan man så udvælge en kombination på fem forskellige stykker chokolade? Dette kan man udregne ved hjælp af kombinatorik.

Når man vælger første gang, har man tolv muligheder. Når man vælger anden gang, har man elleve muligheder, da vi er interesseret i fem forskellige stykker. For hver af de tolv muligheder har vi altså elleve muligheder for at vælge det andet stykke, så vi skal altså gange dem sammen for at få antallet af kombinationer. Ved næste valg har vi ti muligheder. Ved næste valg ni og ved det sidste valg har vi otte muligheder. Altså:

12\cdot11\cdot10\cdot9\cdot8 = 95040

Der er altså 95040 forskellige rækkefølger af fem stykker chokolade, man kan vælge ud af de tolv muligheder. Hvis vi er ligeglad med rækkefølgen vi vælger stykkerne i, skal vi finde ud af hvor mange måder man kan udvælge de samme fem stykker. Ved første stykke har vi fem muligheder, ved andet stykke har vi fire muligheder, og så videre:

5\cdot4\cdot3\cdot2\cdot1 = 120

For hver kombination af chokoladestykker er der altså 120 forskellige rækkefølger at vælge dem i. Så vi skal dividere med 120:

\frac{12\cdot11\cdot10\cdot9\cdot8}{5\cdot4\cdot3\cdot2\cdot1} = \frac{95040}{120} = 792

Altså, der findes 792 kombinationsmuligheder at vælge fem stykker chokolade ud fra tolv muligheder. Dette regnestykke generaliseres til:

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

n er antallet af muligheder

r er antallet vi skal udvælge

Husk at ! er tegnet for fakultetsfunktionen, som betyder at man ganger med alle heltal op til tallet (3! = 3 \cdot 2 \cdot 1).

Hvis rækkefølgen gør en forskel, skal vi ikke dividere med antal rækkefølger, og formlen ser således ud:

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

Eksempel 1

Vi vil i dette eksempel på kombinatorik se på, hvor mange mulige lottotal der kan trækkes. Der trækkes 7 tal, som kan være fra 1 til 48. Rækkefølgen er ligegyldig, så vi bruger den første formel og regner ud med lommeregner:

K_{48,7} =\frac{48!}{7!(48-7)!} = 73 629 072

Der er altså over 73 millioner kombinationer af lottotal. Dermed er chancen for, at den kombination du vælger, er den der bliver trukket én ud af 73 millioner.

Eksempel 2

Et andet eksempel på kombinatorik kunne være at udvælge dine yndlingsfag i skolen. Hvis du skal vælge dine tre favoritfag i prioriteret rækkefølge, og du i alt har 10 fag, kan du regne antallet af mulige kombinationer ud, ved at bruge den anden formel. Da vi har at gøre med en prioriteret liste, skal vi ikke dividere med antallet af forskellige rækkefølger.

K_{10,3} =\frac{10!}{(10-3)!} = \frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1} = 10\cdot9\cdot8 = 720

Der er altså 720 måder at vælge sine tre favoritfag på.