Kombinatorik

Kombinatorik er læren om at tælle kombinationer. Det lyder måske åndssvagt, at der er en hel videnskab om dette, da det virker så banalt at tælle (selv børnehavebørn kan det!). Men kombinationer kan hurtigt blive uoverskuelige.

Tænk f.eks. på hvis du har lektier for i 8 fag, men du kun har tid til at lave lektier i 3 af dem. Hvor mange måder kan du udvælge de 3 fag, du skal lave dine lektier i? Pludselig er det ikke så lige til at tælle, hvor mange kombinationer, der er.

Lad os regne lidt på dette eksempel.

Når vi vælger det første fag, er der 8 muligheder. Når vi skal vælge fag nummer to, er der 7 valgmuligheder. Ved valget af nummer tre, er der kun 6 muligheder tilbage.

Vi bruger mulitplikationsprincippet:

$$8\cdot7\cdot6=336\:\text{muligheder}$$

Et stort tal, hva? Imidlertid er vi ikke helt færdige! Hvis vi siger, at fagene hver er repræsenteret af et bogstav, og vi nu har valgt fagene a, b og c, så er der flere forskellige måder, vi kan have trukket de samme fag på:  (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b) og (c,b,a). Vi er ligeglade med i hvilken rækkefølge, vi laver lektierne i de tre fag, så alle kombinationerne ovenfor er egentlig den samme for os.

For at se, hvor mange måder, vi kan bytte om på de tre fag, må vi tænke at det første fag, vi laver lektier i er der 3 muligheder, det næste fag er der kun 2 muligheder, og det sidste er der kun 1 mulighed. Altså kan de tre fag byttes rundt på

$$3\cdot2\cdot1=6\:\text{måder}$$

Hver kombination af 3 fag går altså igen 6 gange blandt de 336 muligheder, vi fandt frem til ovenfor. Vi må altså dividere med 6 for at når frem til det rigtige svar.

$$\frac{8\cdot7\cdot6}{3\cdot2\cdot1}=56$$

Så der er altså 56 forskellige kombinationer af tre-fags-pakker, du kan lave lektier i.

Lad os se lidt nærmere på udtrykket ovenfor

$$\frac{8\cdot7\cdot6}{3\cdot2\cdot1}$$

Vi får den idé at forlænge brøken med 5\(\cdot\)4\(\cdot\)3\(\cdot\)2\(\cdot\)1.

$$\frac{8\cdot7\cdot6}{3\cdot2\cdot1}=\frac{8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\:\cdot5\cdot4\cdot3\cdot2\cdot1}$$

Dette kan vi omskrive ved hjælp af fakultetsfunktionen:

$$\frac{8\cdot7\cdot6}{3\cdot2\cdot1}=\frac{8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\:\cdot5\cdot4\cdot3\cdot2\cdot1}=\frac{8!}{3!\cdot5!}=\frac{8!}{3!\cdot(8-3)!}$$

Vi har altså fundet en formel til, hvordan man kan udvælge 3 elementer ud af en mængde på 8, hvis man kun må vælge den samme ting én gang, og hvis rækkefølgen er ligegyldig.

Denne formel kan generaliseres til hvis man ønsker at udvælge r elementer af en mængde, der består af n elementer.

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

Hvis man f.eks. ville finde ud af, hvor mange pokerhænder, der eksisterer, altså hvor mange måder man kan uddele 5 kort fra en bunke på 52, hvor rækkefølgen er ligegyldig (vi er jo ligeglade med om vi får Spar Es som første eller sidste kort), bruger man formlen herover

$$K_{52,5}=\frac{52!}{5!\cdot(52-5)!}=\frac{52!}{5!\cdot47!}=2.598.960$$

Der er altså over 2,5 millioner forskellige pokerhænder!

Hvis rækkefølgen betyder noget

Det er imidlertid ikke alle tilfælde, hvor rækkefølgen er ligegyldig. Det kunne f.eks. være, at du blev bedt om at vælge dine top-10 yndlings-CD'er ud fra en liste på 25 CD'er. Her er det i hvert fald ikke ligegyldigt, hvad du vælger som 1'er og som 10'er.

På hvor mange måder, kan man lave sådan en liste?

Jo ser du, på førstepladsen kan du vælge din favorit af de 25 CD'er. På andenpladsen kan du vælge din næst-yndlings af de 24 tilbageværende. På tredjepladsen kan du vælge blandt de 23 tilbageværende. Og så videre indtil du til sidst har 16 valgmuligheder til din tiendeplads.

Kombinationerne er derfor

$$25\cdot24\cdot23\cdot22\cdot21\cdot20\cdot19\cdot18\cdot17\cdot16=11.861.676.288.000$$

Altså næsten 12 billioner måder at sammensætte en top-10 på!

Vi får en idé og ganger og dividerer med 15\(\cdot\)14\(\cdot\)13\(\cdot\)...\(\cdot\)3\(\cdot\)2\(\cdot\)1.

$$\frac{25\cdot24\cdot23\cdot22\cdot21\cdot20\cdot19\cdot18\cdot17\cdot16\cdot15\cdot14\cdot13\cdot...\cdot3\cdot2\cdot1}{15\cdot14\cdot13\cdot...\cdot3\cdot2\cdot1}$$

Vi omskriver igen ved hjælp af fakultetsfunktionen

$$\frac{25\cdot24\cdot23\cdot22\cdot21\cdot20\cdot19\cdot18\cdot17\cdot16\cdot15\cdot14\cdot13\cdot...\cdot3\cdot2\cdot1}{15\cdot14\cdot13\cdot...\cdot3\cdot2\cdot1}=$$

$$=\frac{25!}{15!}=\frac{25!}{(25-10)!}$$

Vi kan generalisere. Hvis vi vil udvælge r elementer fra en mængde på n mulige, hvor vi kun må vælge hvert element én gang, og hvor rækkefølgen betyder noget, kan det gøres på følgende antal måder:

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

Vi spiller Mastermind, hvor man skal vælge en kode bestående af 4 farver ud af de 8, der er med i spillet. Hvis hver farve kun må vælges én gang, og rækkefølgen af farverne tæller, så spekulerer på, hvor mange forskellige kombinationer, man kan komme frem til. Svaret er

$$P_{8,4}=\frac{8!}{(8-4)!}=\frac{8!}{4!}=1680\text{ forskellige koder}$$