5.3 Spill og strategi

Hvor mange muligheter finnes egentlig?

Emma har nettopp begynt i resepsjonen på et hotell, og personalansvarlig forklarer uniformsreglene: skjorten kan være hvit, lyseblå eller lys rosa; buksen eller skjørtet svart eller mørkeblått; og slipset eller skjerfet rødt, gråstripet eller ensfarget blått. «Du har mange kombinasjoner å velge mellom», sier han. Men hvor mange, helt nøyaktig? Emma kunne satt seg ned og listet opp alle – men det finnes en raskere vei.

Spørsmål av denne typen dukker opp overalt i yrkeslivet: Hvor mange ulike menyer kan kantinen sette sammen? Hvor mange mulige ruter har budbilen? Hvor mange koder kan alarmsystemet ha – og hvor lang tid ville det ta en innbruddstyv å prøve alle? For å svare trenger vi kombinatorikk – læren om å telle systematisk.

Det meste av kombinatorikken i dette kapittelet hviler på én eneste idé: multiplikasjonsprinsippet. I denne fortellingen lærer du prinsippet gjennom Emmas uniform og kantinens meny, ser hvordan et valgtre gjør tellingen visuell – og møter til slutt det viktige skillet mellom valg med og uten tilbakelegging, fra kodelåser til vaktlister.

Multiplikasjonsprinsippet og valgtreet

Multiplikasjonsprinsippet sier: Hvis et valg gjøres i flere trinn, der trinn 1 har $n_1$ muligheter, trinn 2 har $n_2$ muligheter og så videre, er det totale antallet muligheter produktet $n_1 \cdot n_2 \cdot n_3 \cdots n_m$.

Emmas uniform er et perfekt eksempel: 3 skjortefarger, 2 buksefarger og 3 slips- eller skjerfvarianter gir $3 \cdot 2 \cdot 3 = 18$ ulike uniformkombinasjoner. Logikken er grei å se: for hver av de 3 skjortene finnes 2 bukser – 6 kombinasjoner så langt – og for hver av disse 6 finnes 3 slipsvalg, til sammen 18.

Kantinen på hotellet bruker samme regnestykke. Lunsjen består av suppe (tomat, løk eller ertesuppe), brød (lyst, grovt eller knekkebrød) og drikke (vann, juice, melk eller kaffe): $3 \cdot 3 \cdot 4 = 36$ ulike lunsjkombinasjoner. Fjernes kaffen, blir det $3 \cdot 3 \cdot 3 = 27$; kommer en ny suppe til, $4 \cdot 3 \cdot 3 = 36$ igjen. Hvert trinn ganger – aldri pluss.

Når tallene er små, kan du også tegne et valgtre: en gren for hvert valg i første trinn, nye grener ut fra hver av dem for neste trinn, og så videre. Antall endepunkter er antall muligheter. Valgtreet er spesielt nyttig når du vil se alle mulighetene oversiktlig, eller når noen kombinasjoner er ugyldige og skal lukes bort – kanskje tillater ikke hotellet rosa skjorte med rødt skjerf. For store tall er multiplikasjonsprinsippet raskere; treet med 36 lunsjgrener blir fort uoversiktlig å tegne.

Med eller uten tilbakelegging – kodelåsen og vaktlisten

På verkstedet i kjelleren henger et verktøyskap med kodelås: 4 sifre, hvert fra 0 til 9. Hvor mange koder finnes? Hvert siffer har 10 muligheter, og samme siffer kan brukes flere ganger: $10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10\,000$ koder. Dette er valg med tilbakelegging – hvert valg «legges tilbake» og er tilgjengelig igjen i neste trinn. Generelt: $n$ symboler på $k$ plasser gir $n^k$ muligheter.

Men hva om alle sifrene må være forskjellige? Da endres spillet: første siffer har 10 muligheter, men det andre bare 9 (ett er brukt), det tredje 8 og det fjerde 7. Antallet blir $10 \cdot 9 \cdot 8 \cdot 7 = 5\,040$ koder. Dette er valg uten tilbakelegging – mulighetene minker for hvert trinn, og resultatet blir alltid færre kombinasjoner enn med tilbakelegging.

Det reneste eksempelet på «uten tilbakelegging» er å ordne en hel gruppe i rekkefølge. På sykehjemmet skal 5 ansatte fordeles på 5 ulike vakter – tidligvakt, dagvakt, seinvakt, nattevakt og bakvakt. Lederen har 5 kandidater til tidligvakten; når den er satt, gjenstår 4 til dagvakten, så 3, 2 og til slutt 1. Totalt: $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ måter. Dette produktet har eget navn og symbol: fakultet, skrevet $5! = 120$. Generelt er $n!$ antall måter å ordne $n$ objekter i rekkefølge.

Og hvis Anna skal ha nattevakten? Da er hennes plass låst, og de 4 andre fordeles på de 4 gjenværende vaktene: $4! = 24$ måter. Kombinatorikk gir oss også sannsynligheter på kjøpet: trekkes vaktlisten tilfeldig, er sjansen for akkurat én bestemt fordeling $\displaystyle \frac{1}{120}$ – gunstige delt på mulige, som alltid.

Å telle smart

Emma fant sine 18 uniformkombinasjoner uten å liste opp en eneste – og det er kombinatorikkens gave: å telle uten å telle. Grunnsteinen er multiplikasjonsprinsippet: når et valg gjøres i trinn, ganges antall muligheter i hvert trinn sammen, slik kantinens $3 \cdot 3 \cdot 4 = 36$ lunsjer viste. Valgtreet tegner de samme mulighetene som grener og er gull verdt når tallene er små eller noen kombinasjoner skal lukes bort.

Så det avgjørende skillet: Med tilbakelegging kan samme element velges igjen, og $n$ symboler på $k$ plasser gir $n^k$ – verktøyskapets $10^4 = 10\,000$ koder. Uten tilbakelegging krymper mulighetene for hvert valg, $10 \cdot 9 \cdot 8 \cdot 7 = 5\,040$ – alltid færre. Og når en hel gruppe skal ordnes i rekkefølge, lander vi på fakultetet $n! = n \cdot (n-1) \cdots 2 \cdot 1$, som sykehjemmets vaktliste med $5! = 120$ fordelinger – eller $4! = 24$ når Annas nattevakt var spikret.

Kombinatorikken er dessuten sannsynlighetsregningens beste venn: antall gunstige delt på antall mulige krever at du kan telle begge – og nå kan du det. Enten du setter sammen menyer, vurderer hvor sikker en kode egentlig er, eller fordeler vakter: gang deg gjennom trinnene, hold tunga rett i munnen på tilbakelegging, og la tallene gjøre jobben.