8.2 Permutasjoner

Spiller rekkefølgen noen rolle?

Ti løpere stiller til start. På hvor mange måter kan gull, sølv og bronse fordeles? Og et annet spørsmål: på hvor mange måter kan tre av de ti velges ut til dopingkontroll? Ved første øyekast ligner spørsmålene – begge handler om å plukke tre av ti. Men svarene er vilt forskjellige: 720 mot 120.

Forskjellen ligger i ett eneste ord: rekkefølge. På seierspallen betyr rekkefølgen alt – gull til Anna og sølv til Bo er noe annet enn omvendt. I dopingkontrollen betyr den ingenting – de samme tre personene blir testet uansett. Når rekkefølgen teller, snakker vi om permutasjoner; når den ikke teller, om kombinasjoner.

I dette kapittelet lærer du å beregne begge deler med formler bygget på fakultet, du møter binomialkoeffisientene $\binom{n}{r}$ – kombinatorikkens mest berømte symbol – og du ser hvordan de ordner seg i det vakre mønsteret som kalles Pascals trekant.

Fakultet og permutasjoner

Først trenger vi en notasjon for det synkende produktmønsteret fra forrige kapittel. For et positivt heltall $n$ definerer vi $n$ fakultet:

$$n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1$$

For eksempel er $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ og $3! = 6$. Per definisjon setter vi $0! = 1$ – det kan virke rart, men det får alle formlene til å stemme. En nyttig egenskap er at fakultetet kan skrelles trinnvis: $n! = n \cdot (n-1)!$.

Nå til permutasjoner – ordnede utvalg. Skal alle $n$ elementer ordnes, gir multiplikasjonsprinsippet $n$ valg for første plass, $n-1$ for andre, og så videre: totalt $n!$ måter. Fem bøker på en hylle kan altså ordnes på $5! = 120$ måter.

Skal vi velge og ordne bare $r$ av de $n$ elementene, stopper vi den synkende trappen etter $r$ steg:

$$P(n, r) = \frac{n!}{(n-r)!} = n \cdot (n-1) \cdot \ldots \cdot (n-r+1)$$

Brøken er bare en kompakt skrivemåte: $\displaystyle \frac{10!}{7!}$ betyr at faktorene fra $7$ og nedover forkortes bort, og igjen står $10 \cdot 9 \cdot 8$. Dermed kan medaljespørsmålet besvares: gull, sølv og bronse blant ti løpere kan fordeles på $P(10, 3) = 10 \cdot 9 \cdot 8 = 720$ måter.

Kombinasjoner – når rekkefølgen er likegyldig

Tilbake til dopingkontrollen. Vi skal velge 3 av 10 løpere, men nå er {Anna, Bo, Carl} det samme utvalget som {Carl, Anna, Bo}. Permutasjonstallet 720 teller hver slik trio flere ganger – nøyaktig $3! = 6$ ganger, én for hver rekkefølge de kunne vært trukket i. Det riktige antallet uordnede utvalg blir derfor $\displaystyle \frac{720}{6} = 120$.

Dette er den generelle ideen bak kombinasjoner: tell de ordnede utvalgene, og del bort rekkefølgene. Antall måter å velge $r$ elementer fra $n$ uten hensyn til rekkefølge er

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

Symbolet $\binom{n}{r}$ kalles en binomialkoeffisient og leses «$n$ over $r$». Noen egenskaper følger nesten gratis: $\binom{n}{0} = \binom{n}{n} = 1$ (bare én måte å velge ingen eller alle), $\binom{n}{1} = n$, og symmetrien $\binom{n}{r} = \binom{n}{n-r}$ – å velge ut $r$ er det samme som å peke ut de $n-r$ som blir igjen.

Et klassisk eksempel: en komité på 4 skal velges blant 12 personer. Rekkefølgen er likegyldig, så svaret er $\displaystyle \binom{12}{4} = \frac{12 \cdot 11 \cdot 10 \cdot 9}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{11\,880}{24} = 495$.

Testspørsmålet du alltid skal stille deg: betyr rekkefølgen noe? Førsteplass-andreplass-tredjeplass: ja – permutasjon. Komité, dopingkontroll, kortspillhånd: nei – kombinasjon. Det er den vanligste feilkilden i hele kombinatorikken.

Pascals trekant og pokerens matematikk

Skriv binomialkoeffisientene i rader: rad $n$ inneholder $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Resultatet er Pascals trekant: toppen er $1$, neste rad $1 \; 1$, så $1 \; 2 \; 1$, så $1 \; 3 \; 3 \; 1$, så $1 \; 4 \; 6 \; 4 \; 1$, og så videre. Mønsteret: hvert tall er summen av de to tallene rett over. Dette er ikke magi, men Pascals regel:

$$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$

Det finnes et vakkert argument for regelen. Skal du velge $r$ av $n$ personer, kan du sortere mulighetene etter hva som skjer med den siste personen: enten er hun med (da må du velge $r-1$ av de $n-1$ andre) eller ikke (da velger du alle $r$ blant de $n-1$ andre). To utelukkende tilfeller – addisjonsprinsippet gir regelen. Binomialkoeffisientene dukker forresten også opp i algebraen, i binomialformelen $(a+b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^r$ – det er derfor de heter det de heter.

Til slutt et eksempel der kombinatorikken møter spillbordet. En pokerhånd er 5 kort av 52, og siden hånden er den samme uansett utdelingsrekkefølge, er antall hender $\binom{52}{5} = 2\,598\,960$. Hvor mange av dem er flush – fem kort i samme farge? Her kombinerer vi prinsippene fra forrige kapittel: velg først farge (4 muligheter), velg deretter 5 av de 13 kortene i fargen ($\binom{13}{5} = 1287$ måter). Multiplikasjonsprinsippet gir $4 \cdot 1287 = 5148$ flush-hender. Bare en drøy promille av alle hender – nå vet du hvorfor flush slår så mye annet.

Oppsummering: rekkefølgens pris

Alt i dette kapittelet springer ut av ett spørsmål: betyr rekkefølgen noe? Fakultetet $n! = n \cdot (n-1) \cdot \ldots \cdot 1$ (med $0! = 1$) er byggesteinen. Når rekkefølgen teller, bruker du permutasjoner: $n!$ for å ordne alt, $\displaystyle P(n,r) = \frac{n!}{(n-r)!}$ for å velge og ordne $r$ av $n$. Når rekkefølgen er likegyldig, deler du bort de $r!$ rekkefølgene og får kombinasjonene $\displaystyle \binom{n}{r} = \frac{n!}{r!(n-r)!}$ – binomialkoeffisientene, med egenskapene $\binom{n}{0} = \binom{n}{n} = 1$ og symmetrien $\binom{n}{r} = \binom{n}{n-r}$.

Binomialkoeffisientene ordner seg i Pascals trekant, der Pascals regel $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ forklarer hvorfor hvert tall er summen av de to over – og de samme tallene dukker opp som koeffisienter i binomialformelen $(a+b)^n = \sum_{r=0}^{n}\binom{n}{r}a^{n-r}b^r$.

Og som pokereksempelet viste: de store telleproblemene løses ved å kombinere alt – «og» gir multiplikasjon, «eller» gir addisjon, og $\binom{n}{r}$ teller utvalgene. I neste kapittel setter vi disse tallene i arbeid der de virkelig skinner: i sannsynlighetsregningen.