5.1 Kombinatorikk

Tallet som avgjorde lotterimistanken

Forestill deg at du jobber i Lotteritilsynet. En dag kommer det inn en bekymringsmelding: en spiller hevder at Lotto-trekningen må være rigget, fordi «de samme tallene aldri kommer igjen». For å vurdere påstanden trenger du svar på et helt grunnleggende spørsmål: hvor mange ulike lottorekker finnes det egentlig?

Å liste opp alle rekkene er håpløst — det ville tatt år. Men med kombinatorikk, læren om systematisk telling, kan du regne ut svaret på under et minutt. Kombinatorikk er verktøykassen forskere, statistikere og tilsynsmyndigheter bruker når de skal telle muligheter uten å liste dem opp: Hvor mange PIN-koder finnes det? På hvor mange måter kan et utvalg til en spørreundersøkelse settes sammen? Hvor sannsynlig er en bestemt pokerhånd?

I dette kapittelet skal vi bygge opp denne verktøykassen steg for steg. Vi starter med multiplikasjonsprinsippet, fortsetter med fakultet og permutasjoner (ordnede utvalg), og ender opp med kombinasjoner (uordnede utvalg) — selve nøkkelen til lottospørsmålet. Til slutt ser vi hvordan tellingen lar oss beregne sannsynligheter, akkurat slik Lotteritilsynet gjør når de vurderer om et spill er rettferdig.

Multiplikasjonsprinsippet — å telle uten å liste

Vi begynner med noe du møter hver dag: PIN-koden til bankkortet ditt. En kode har fire siffer, og hvert siffer kan være alt fra 0 til 9. Hvor mange koder finnes det? Tenk på det som fire valg etter hverandre. Første siffer kan velges på 10 måter. Uansett hva du valgte, kan andre siffer også velges på 10 måter — og det samme gjelder tredje og fjerde. Totalt blir det

$$10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10\,000$$

mulige koder. Dette er multiplikasjonsprinsippet: Hvis vi skal gjøre $k$ uavhengige valg, og det første valget kan gjøres på $n_1$ måter, det andre på $n_2$ måter, og så videre, er totalt antall muligheter

$$n_1 \cdot n_2 \cdot n_3 \cdot \ldots \cdot n_k$$

Prinsippet dukker opp overalt. Skal du sette sammen et antrekk av 4 skjorter og 3 bukser, har du $4 \cdot 3 = 12$ antrekk å velge mellom. Du kan tegne det som et trediagram: fra hver skjorte går det tre greiner, én for hver bukse, og du ender med tolv blader nederst i treet.

Legg merke til ordet uavhengige: antall muligheter i hvert trinn må være det samme uansett hva du valgte i trinnene før. Når det stemmer, kan du bare gange sammen — og det er nettopp denne enkle ideen alt det følgende bygger på.

Fakultet og permutasjoner — når rekkefølgen teller

Tilbake til samfunnslivet: en valgkomité skal sette opp fem kandidater på en valgliste. Rekkefølgen er alt annet enn likegyldig — førsteplassen er nesten garantert et verv. På hvor mange måter kan listen ordnes?

Førsteplassen kan fylles av 5 kandidater. Når den er tatt, gjenstår 4 til andreplassen, så 3, så 2, og til slutt 1. Multiplikasjonsprinsippet gir $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ mulige lister. Produktet av alle heltall fra $n$ og ned til 1 er så vanlig at det har fått eget navn og symbol: fakultet,

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

For eksempel er $3! = 6$, $4! = 24$ og $5! = 120$. Per definisjon setter vi $0! = 1$ — det finnes nøyaktig én måte å ordne ingenting på.

Men hva om vi ikke skal ordne alle? I et løp med 8 deltakere skal gull, sølv og bronse deles ut. Gullet kan gå til 8 løpere, sølvet til 7, bronsen til 6: $8 \cdot 7 \cdot 6 = 336$ mulige pallplasseringer. Et slikt ordnet utvalg kalles en permutasjon, og den generelle formelen for å velge $r$ av $n$ objekter når rekkefølgen har betydning er

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

Sjekk gjerne: $\displaystyle P(8,3) = \frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336$. Divisjonen med $(n-r)!$ «kutter av» de faktorene vi ikke trenger. Og når vi ordner alle $n$ objektene, blir $P(n,n) = n!$ — akkurat som med valglisten.

Kombinasjoner — når rekkefølgen er likegyldig

Nå skifter vi situasjon. Et forskningsinstitutt skal plukke ut 4 av 10 studenter til en referansegruppe. Her er alle medlemmene likeverdige — det spiller ingen rolle hvem som ble valgt «først». Et slikt uordnet utvalg kalles en kombinasjon.

Hvordan teller vi? Vi kan starte med permutasjonene: $P(10,4) = 10 \cdot 9 \cdot 8 \cdot 7 = 5040$ ordnede utvalg. Men hver gruppe på fire personer er nå telt mange ganger — én gang for hver rekkefølge de kan stilles opp i, altså $4! = 24$ ganger. Det riktige antallet grupper blir derfor $5040 / 24 = 210$. Generelt:

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

Symbolet $\binom{n}{r}$ leses «$n$ over $r$» og kalles binomialkoeffisienten. Divisjonen med $r!$ er hele forskjellen på permutasjoner og kombinasjoner: vi deler bort rekkefølgen.

Og nå kan vi endelig svare Lotteritilsynet. I en forenklet lottotrekning trekkes 6 tall blant tallene 1 til 34, og rekkefølgen de trekkes i er uten betydning. Antall mulige rekker er

$$\binom{34}{6} = \frac{34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29}{6!} = \frac{968\,330\,880}{720} = 1\,344\,904$$

Over 1,3 millioner rekker! At samme vinnerrekke «aldri kommer igjen» er altså ikke mistenkelig — det er nøyaktig hva vi forventer.

En enkel huskeregel skiller de to begrepene: Permutasjon — posisjonen teller (pallplasser, PIN-koder, valglister). Kombinasjon — bare kolleksjonen teller (lottorekker, komiteer, utvalg til undersøkelser).

Fra telling til sannsynlighet

Hvorfor bryr Lotteritilsynet, forsikringsselskaper og forskere seg så mye om telling? Fordi telling er broen til sannsynlighet. Når alle utfall er like sannsynlige, gjelder den klassiske formelen

$$P(A) = \frac{\text{antall gunstige utfall}}{\text{antall mulige utfall}}$$

Kombinatorikken lar oss telle både teller og nevner systematisk — selv når tallene blir astronomiske.

La oss teste det på et klassisk eksempel: en kortstokk. Den har 52 kort fordelt på fire farger — hjerter og ruter (røde), spar og kløver (sorte) — med 13 kort i hver farge, deriblant 4 ess totalt. Du trekker 5 kort tilfeldig. Hva er sannsynligheten for nøyaktig 3 ess?

Først nevneren: antall mulige pokerhender er $\binom{52}{5} = 2\,598\,960$. Så telleren, og her bruker vi multiplikasjonsprinsippet på to kombinasjoner: vi må velge 3 av de 4 essene, $\binom{4}{3} = 4$ måter, og 2 av de 48 øvrige kortene, $\displaystyle \binom{48}{2} = \frac{48 \cdot 47}{2} = 1128$ måter. Antall gunstige hender er dermed $4 \cdot 1128 = 4512$, og

$$P(3 \text{ ess}) = \frac{4512}{2\,598\,960} \approx 0{,}0017 \approx 0{,}17\,\%$$

Det skjer altså i færre enn 2 av 1000 hender. Ser du mønsteret? Velg de «spesielle» objektene med én binomialkoeffisient, resten med en annen, og gang sammen. Akkurat denne strukturen møter du igjen i kapittelet om hypergeometrisk fordeling — der blir den satt i system for kvalitetskontroll og stikkprøver.

Oppsummering: tellekunsten

Lotterimistanken fra innledningen løste seg med ren telling: med over 1,3 millioner mulige lottorekker er det ingenting mystisk i at vinnerrekkene aldri gjentar seg. Underveis bygde vi opp hele den kombinatoriske verktøykassen.

Alt hviler på multiplikasjonsprinsippet: uavhengige valg med $n_1, n_2, \ldots, n_k$ muligheter gir $n_1 \cdot n_2 \cdot \ldots \cdot n_k$ kombinasjoner totalt. Skal vi ordne $n$ objekter i rekkefølge, finnes det $n! = n(n-1)\cdots 2 \cdot 1$ måter, der vi husker spesialtilfellet $0! = 1$.

Når vi velger $r$ av $n$ objekter, må vi alltid stille kontrollspørsmålet: teller rekkefølgen? Gjør den det — som ved pallplasser og valglister — bruker vi permutasjoner, $\displaystyle P(n,r) = \frac{n!}{(n-r)!}$. Er rekkefølgen likegyldig — som ved lottorekker og utvalg til undersøkelser — bruker vi kombinasjoner, $\displaystyle \binom{n}{r} = \frac{n!}{r!(n-r)!}$. De to henger sammen ved at $C(n,r) = P(n,r)/r!$: vi deler bort rekkefølgen.

Til slutt så vi at tellingen er springbrettet til sannsynlighet. Med like sannsynlige utfall er $P(A)$ antall gunstige delt på antall mulige, og kombinatorikken teller begge deler — som da vi fant at sannsynligheten for nøyaktig 3 ess i en pokerhånd er omtrent $0{,}17\,\%$. Denne måten å telle gunstige utfall på, med binomialkoeffisienter for hver gruppe, blir grunnmuren når vi senere møter den hypergeometriske fordelingen og binomisk fordeling.