5.1 Kombinatorikk

Hvor mange muligheter finnes det egentlig?

Tenk deg at du står foran garderoben din en morgen. Du har 4 bukser og 5 t-skjorter. Hvor mange ulike antrekk kan du lage? Du kunne prøvd å liste opp alle kombinasjonene, men det finnes en mye smartere måte.

Kombinatorikk er matematikkens verktøy for å telle muligheter på en systematisk måte -- uten å måtte liste opp hver eneste en. Det er nyttig i alt fra å beregne sjansen for å vinne i Lotto til å forstå hvor sikkert passordet ditt egentlig er.

Vi skal lære tre kraftige verktøy: multiplikasjonsprinsippet for trinnvise valg, permutasjoner når rekkefølgen betyr noe, og kombinasjoner når rekkefølgen ikke betyr noe.

Multiplikasjonsprinsippet -- å gange antall valg

La oss gå tilbake til garderoben. Du skal først velge bukse -- 4 muligheter. Deretter velger du t-skjorte -- 5 muligheter. Til hver bukse kan du pare enhver t-skjorte. Det gir $4 \cdot 5 = 20$ ulike antrekk.

Dette er multiplikasjonsprinsippet: når en handling kan gjøres på $m$ måter, og en annen uavhengig handling kan gjøres på $n$ måter, kan begge handlingene til sammen gjøres på $m \cdot n$ måter. Prinsippet kan utvides til så mange handlinger du vil: $m \cdot n \cdot p \cdot \ldots$

La oss se på noen hverdagseksempler. En PIN-kode består av 4 siffer, der hvert siffer kan være 0 til 9. Hvert av de fire sifrene har 10 valgmuligheter, så antall PIN-koder er:

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

Hva med et passord på 3 bokstaver (a-z) etterfulgt av 2 siffer (0-9)? Da får vi:

$$26^3 \cdot 10^2 = 17\,576 \cdot 100 = 1\,757\,600 \text{ mulige passord}$$

En restaurant tilbyr 3 forretter, 5 hovedretter og 4 desserter. Antall ulike 3-retters menyer blir $3 \cdot 5 \cdot 4 = 60$.

Fakultet og permutasjoner -- når rekkefølgen betyr noe

Forestill deg at 6 venner skal stille seg opp på en rekke for et bilde. På hvor mange måter kan de gjøre det?

Første plass kan fylles av hvem som helst -- 6 valg. Når den er fylt, gjenstår 5 personer for andre plass, så 4 for tredje, og så videre. Totalt:

$$6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720 \text{ måter}$$

Denne typen produkt dukker opp så ofte at det har fått et eget navn: fakultet. Vi skriver $n!$ (leses "n fakultet") og det betyr:

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

Noen nyttige verdier: $5! = 120$, $4! = 24$, $1! = 1$, og -- kanskje overraskende -- $0! = 1$ (det er definert slik).

En permutasjon er en ordnet rekkefølge av elementer. Antall permutasjoner av alle $n$ elementer er rett og slett $n!$

Men hva om vi bare skal ordne noen av elementene? I et løp med 10 deltakere skal det deles ut gull, sølv og bronse. Vi trenger ikke plassere alle 10 -- bare de 3 første. Da blir det:

$$P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720$$

Vi kan også forenkle brøk med fakultet. For eksempel: $\displaystyle \frac{8!}{6!} = \frac{8 \cdot 7 \cdot 6!}{6!} = 8 \cdot 7 = 56$.

Kombinasjoner -- når rekkefølgen ikke betyr noe

Nå kommer vi til et viktig skille. Tenk på forskjellen mellom disse situasjonene:

- Velge hvem som blir 1., 2. og 3. i et løp -- her betyr rekkefølgen noe (permutasjon)
- Velge hvilke 3 personer som skal være med i en komite -- her betyr rekkefølgen ikke noe (kombinasjon)

En kombinasjon er et utvalg der rekkefølgen ikke spiller noen rolle. Formelen for å velge $r$ elementer fra $n$ elementer er:

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

Dette leses "$n$ over $r$" eller "$n$ velg $r$".

La oss se på et konkret eksempel. En komite på 4 personer skal velges fra en gruppe på 10. Siden alle i komiteen er likestilte, bruker vi kombinasjoner:

$$\binom{10}{4} = \frac{10!}{4! \cdot 6!} = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{5040}{24} = 210$$

Et annet eksempel: i et lotteri trekkes 6 tall fra tallene 1-34. Rekkefølgen tallene trekkes i spiller ingen rolle. Antall mulige kombinasjoner:

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

En nyttig egenskap: $\binom{n}{r} = \binom{n}{n-r}$. For eksempel er $\binom{6}{2} = \binom{6}{4} = 15$. Det gir mening: å velge ut 2 av 6 er det samme som å velge bort 4 av 6.

Sammensatte problemer -- knep og strategier

I virkeligheten må vi ofte kombinere flere metoder. Her er noen nyttige strategier:

Strategi 1: Totalt minus uønskede. Hvor mange 4-tegns passord (bokstaver A-Z og siffer 0-9) inneholder minst ett siffer? Det er enklere å beregne totalt antall passord minus de uten siffer:

$$36^4 - 26^4 = 1\,679\,616 - 456\,976 = 1\,222\,640$$

Strategi 2: Del opp i tilfeller. Fra en gruppe på 6 gutter og 5 jenter skal det velges 4 personer med minst 2 jenter. Vi deler opp:

- 2 jenter, 2 gutter: $\binom{5}{2} \cdot \binom{6}{2} = 10 \cdot 15 = 150$
- 3 jenter, 1 gutt: $\binom{5}{3} \cdot \binom{6}{1} = 10 \cdot 6 = 60$
- 4 jenter, 0 gutter: $\binom{5}{4} \cdot \binom{6}{0} = 5 \cdot 1 = 5$

Totalt: $150 + 60 + 5 = 215$ måter.

Strategi 3: Betingelser. En komite på 5 fra 10 personer, men en bestemt person MÅ være med. Da er den personen allerede valgt, og vi velger 4 til fra de 9 andre: $\binom{9}{4} = 126$.

En sjakkturning med 8 deltakere der alle spiller mot alle -- antall kamper er $\binom{8}{2} = 28$, fordi hver kamp er et utvalg av 2 spillere.

Bokstavene i ordet MATTE kan ordnes på $\displaystyle \frac{5!}{2!} = 60$ måter, fordi vi må dele på $2!$ for de to like T-ene.

Oppsummering

Vi har lært tre hovedverktøy for å telle muligheter:

- Multiplikasjonsprinsippet: Når du gjør flere uavhengige valg etter hverandre, ganger du antall muligheter for hvert valg. Antrekk, PIN-koder og passord er typiske eksempler.

- Permutasjoner: Når rekkefølgen betyr noe. Alle $n$ elementer: $n!$. Velge $r$ fra $n$: $\displaystyle P(n,r) = \frac{n!}{(n-r)!}$. Pallplasser og køer er typiske eksempler.

- Kombinasjoner: Når rekkefølgen ikke betyr noe. Velge $r$ fra $n$: $\displaystyle \binom{n}{r} = \frac{n!}{r!(n-r)!}$. Komiteer, lag og lottotrekninger er typiske eksempler.

Nøkkelspørsmålet: Betyr rekkefølgen noe? Ja = permutasjon. Nei = kombinasjon.

For sammensatte problemer: bruk "totalt minus uønskede", del opp i tilfeller, eller reduser problemet ved betingelser.