6.2 Sammensatte hendelser

Hvor mange muligheter finnes det egentlig?

Du står foran klesskapet en morgen: $4$ bukser og $5$ skjorter. Hvor mange forskjellige antrekk kan du sette sammen? Senere samme dag skal du velge en firesifret PIN-kode til en ny app, og du lurer på hvor mange koder en hacker måtte prøvd for å gjette din.

Begge spørsmålene handler om det samme: å telle muligheter. Fagfeltet heter kombinatorikk, og det er tellekunsten som ligger under all sannsynlighetsregning -- for å finne «antall gunstige» og «antall mulige» må du jo kunne telle dem! Heldigvis trenger du ikke liste opp alle mulighetene én for én. I dette kapittelet lærer du to verktøy som gjør jobben: multiplikasjonsprinsippet og valgtreet.

Multiplikasjonsprinsippet -- gang mulighetene sammen

Tilbake til klesskapet. For hver av de $4$ buksene kan du velge $5$ forskjellige skjorter. Bukse nummer én gir $5$ antrekk, bukse nummer to gir $5$ nye, og så videre. Totalt:

$$4 \cdot 5 = 20 \text{ antrekk}$$

Dette er multiplikasjonsprinsippet: når du gjør flere valg etter hverandre, og det er $n_1$ muligheter i første valg og $n_2$ i andre, er det totale antallet kombinasjoner

$$n_1 \cdot n_2$$

Prinsippet fortsetter for så mange valg du vil. Legger du til $3$ par sko, blir det $4 \cdot 5 \cdot 3 = 60$ komplette antrekk.

Og PIN-koden? Den har fire sifre, og hvert siffer kan være $0$–$9$ -- altså $10$ muligheter per posisjon. Siden samme siffer kan brukes flere ganger:

$$10 \cdot 10 \cdot 10 \cdot 10 = 10\,000 \text{ koder}$$

Men hva om appen krevde at alle sifrene var forskjellige? Da er det fortsatt $10$ muligheter for første siffer, men bare $9$ igjen for det andre, $8$ for det tredje og $7$ for det fjerde:

$$10 \cdot 9 \cdot 8 \cdot 7 = 5\,040 \text{ koder}$$

Dette er det viktige skillet mellom valg med gjentakelse -- antallet er likt i hvert ledd -- og uten gjentakelse -- antallet minker med én for hvert valg, fordi brukte muligheter forsvinner fra menyen.

Valgtreet -- å tegne seg frem til svaret

Multiplikasjonsprinsippet gir deg antallet, men noen ganger vil du faktisk se alle mulighetene. Da tegner du et valgtre: du starter i en rot og lager én gren for hver mulighet i første valg. Fra enden av hver gren forgreiner du videre for neste valg, og slik fortsetter treet å vokse.

Tenk deg at du kaster en mynt tre ganger og noterer kron (K) eller mynt (M). Fra roten går to grener: K og M. Fra hver av dem to nye: KK, KM, MK, MM. Og etter tredje kast har treet $2 \cdot 2 \cdot 2 = 8$ endepunkter: KKK, KKM, KMK, KMM, MKK, MKM, MMK og MMM.

Her ser du den fine sammenhengen: antall endepunkter i valgtreet er alltid lik svaret fra multiplikasjonsprinsippet. Treet og formelen er to språk for det samme.

Valgtreets styrke er oversikten. Vil du vite sannsynligheten for nøyaktig to kron på tre kast, kan du peke på endepunktene der det skjer: KKM, KMK og MKK -- tre av åtte, altså $\displaystyle P = \frac{3}{8}$. Den typen opptelling er nesten umulig å gjøre trygt i hodet, men triviell med treet foran deg.

I praksis velger du verktøy etter situasjonen: er det mange valg med mange muligheter, blir treet uoverkommelig stort -- bruk multiplikasjonsprinsippet. Trenger du å se og telle bestemte utfall, tegn treet. Sammen gjør de deg rustet til å telle muligheter systematisk -- selve fundamentet for å regne sannsynlighet på alt fra spill til passordsikkerhet.

Oppsummering

Fra klesskapet om morgenen til PIN-koden på kvelden -- kombinatorikk er kunsten å telle muligheter uten å liste opp alle sammen.

Multiplikasjonsprinsippet er hovedverktøyet: gjør du flere valg etter hverandre, ganger du antall muligheter i hvert valg. $4$ bukser og $5$ skjorter gir $4 \cdot 5 = 20$ antrekk; en firesifret kode gir $10^4 = 10\,000$ muligheter.

Skillet mellom med og uten gjentakelse avgjør faktorene: kan samme mulighet brukes om igjen, er antallet likt i hvert ledd ($10 \cdot 10 \cdot 10 \cdot 10$); må alt være forskjellig, minker det med én for hvert valg ($10 \cdot 9 \cdot 8 \cdot 7 = 5\,040$).

Valgtreet tegner alle mulighetene fra rot til endepunkter, og antall endepunkter stemmer alltid med multiplikasjonsprinsippet. Treet gir oversikten du trenger når bestemte utfall skal telles -- som de $3$ av $8$ myntkast-utfallene med nøyaktig to kron.

Med telleverktøyene på plass har du fundamentet for sannsynlighetsregning: nå kan du finne både «antall gunstige» og «antall mulige» -- uansett hvor mange muligheter det er snakk om.