8.1 Multiplikasjonsprinsippet

Kunsten å telle uten å telle

Du står foran menyen på en kafé: to hovedretter og tre desserter. Hvor mange forskjellige måltider kan du sette sammen? Du kunne ramset opp alle – burger med is, burger med kake, burger med frukt, pasta med is... – men det finnes en snarvei: $2 \cdot 3 = 6$. Ferdig.

Dette er kombinatorikk: kunsten å telle antall muligheter uten å liste opp alle sammen. Det høres beskjedent ut, men det er selve grunnmuren under sannsynlighetsregningen du skal lære i resten av kapittel 8 – for å finne sannsynligheten for noe, må du nesten alltid telle hvor mange måter det kan skje på.

I dette kapittelet lærer du de to grunnprinsippene som nesten all telling bygger på: multiplikasjonsprinsippet (for valg som gjøres etter hverandre) og addisjonsprinsippet (for valg som utelukker hverandre). Og du får et visuelt verktøy på kjøpet: valgtreet.

Valgtre og multiplikasjonsprinsippet

Et valgtre er et kart over alle mulighetene. Hvert valg er en forgrening, og hver vei fra roten til et blad er ett komplett utfall. Si at du har 2 skjorter (hvit, blå) og 3 bukser (svart, grå, beige). Fra «hvit» går tre grener – hvit-svart, hvit-grå, hvit-beige – og fra «blå» går tre til. Seks blader, seks antrekk.

Treet avslører mønsteret: hver av de 2 skjortene gir 3 buksevalg, altså $2 \cdot 3 = 6$. Dette generaliserer til multiplikasjonsprinsippet: hvis et sammensatt valg består av $k$ delvalg som kan gjøres på henholdsvis $n_1, n_2, \ldots, n_k$ måter, og valgene er uavhengige av hverandre, er totalt antall muligheter

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

La oss skalere opp. Et kodeord består av 3 bokstaver (norsk alfabet, 29 bokstaver) etterfulgt av 2 siffer. Med gjentakelse tillatt: $29 \cdot 29 \cdot 29 \cdot 10 \cdot 10 = 29^3 \cdot 10^2 = 2\,438\,900$ kodeord. Eller bilskilt med 2 bokstaver (engelsk alfabet, 26) og 5 siffer: $26^2 \cdot 10^5 = 67\,600\,000$ muligheter. Prøv å liste opp det i et valgtre – prinsippet gjør jobben på sekunder.

Valgtreet er likevel uvurderlig når antallet er lite, eller når betingelsene endrer seg underveis i valgsekvensen. Prinsippet er motoren; treet er kartet.

Når gjentakelse ikke er lov

Hva om kodeordet ikke får ha to like tegn? Da endres spillet litt – men multiplikasjonsprinsippet gjelder fortsatt. Forskjellen er at antall muligheter krymper for hvert steg: første bokstav kan velges på 29 måter, men den andre på bare 28 (én er brukt opp), og den tredje på 27. Dette kalles valg uten tilbakelegging.

For kodeordet med 3 ulike bokstaver og 2 ulike siffer blir regnestykket $29 \cdot 28 \cdot 27 \cdot 10 \cdot 9 = 1\,973\,160$ – betydelig færre enn de 2 438 900 vi fikk med gjentakelse, naturlig nok.

Mønsteret er verdt å merke seg: uten gjentakelse blir faktorene $n$, $n-1$, $n-2$ og så videre – en synkende trapp. Dette mønsteret kommer til å spille hovedrollen i neste kapittel, der det får navnet permutasjon og sin egen notasjon med fakultet.

Tenk alltid gjennom om situasjonen tillater gjentakelse eller ikke. En PIN-kode kan ha like siffer (gjentakelse), men et stafettlag kan ikke ha samme løper på to etapper (ikke gjentakelse). Selve prinsippet – multipliser antall muligheter for hvert delvalg – er det samme i begge tilfeller; det er bare tallene som endrer seg underveis.

Addisjonsprinsippet – og kunsten å kombinere

Multiplikasjon håndterer valg som gjøres etter hverandre. Men noen ganger står valgene i stedet i et enten-eller-forhold. Skal klassen velge én representant blant 15 gutter og 12 jenter, er det ikke $15 \cdot 12$ muligheter – du velger jo bare én person! Mulighetene er $15 + 12 = 27$. Dette er addisjonsprinsippet: når en oppgave kan løses på måte $A$ (med $n_A$ muligheter) eller måte $B$ (med $n_B$ muligheter), og de to ikke overlapper, er totalen $n_A + n_B$.

Huskeregelen er språklig og forbløffende pålitelig: «og» betyr multiplikasjon, «eller» betyr addisjon. Skjorte og bukse: multipliser. Gutt eller jente: adder. Kravet for addisjon er at alternativene er gjensidig utelukkende – ingen utfall skal kunne telles to ganger.

De fleste virkelige problemer kombinerer begge prinsippene. Et passord skal bestå av enten 3 bokstaver og 2 siffer, eller 2 bokstaver og 3 siffer (engelsk alfabet, gjentakelse tillatt). Innenfor hver type bruker vi multiplikasjon: type 1 gir $26^3 \cdot 10^2 = 1\,757\,600$, type 2 gir $26^2 \cdot 10^3 = 676\,000$. De to typene utelukker hverandre (et passord kan ikke ha begge strukturer samtidig), så vi adderer: $1\,757\,600 + 676\,000 = 2\,433\,600$ passord.

Ser du arkitekturen? «Og» inni hver type, «eller» mellom typene. Lær deg å lese et telleproblem på denne måten, og selv kompliserte oppgaver faller fra hverandre i håndterlige biter.

Oppsummering: og ganger, eller adderer

Fra kafémenyen til bilskiltregisteret har vi sett samme idé i arbeid: systematisk telling uten oppramsing. Valgtreet visualiserer mulighetene – hver forgrening et delvalg, hvert blad et komplett utfall – og avslører mønsteret bak multiplikasjonsprinsippet: $k$ delvalg etter hverandre med $n_1, n_2, \ldots, n_k$ muligheter gir $n_1 \cdot n_2 \cdot \ldots \cdot n_k$ utfall totalt.

Uten gjentakelse gjelder prinsippet fortsatt, men faktorene synker trinn for trinn: $n$, $n-1$, $n-2$, ... – et mønster som får navnet permutasjon i neste kapittel.

Addisjonsprinsippet tar seg av alternativer som utelukker hverandre: da adderer vi mulighetene. Og språket leder deg riktig nesten hver gang: «og» betyr gange, «eller» betyr pluss. Sammensatte problemer – som passordet med to tillatte strukturer – løses ved å multiplisere innenfor hvert alternativ og addere mellom dem. Med disse to prinsippene i ryggraden er du klar for neste steg: permutasjoner, kombinasjoner og de store spørsmålene om rekkefølge.