Kombinatorikk

Kombinatorikk er læren om å telle kombinasjoner. Det kan høres merkelig ut, da man allerede i barnehagen lærer å telle, men kombinasjoner kan fort bli uoversiktelige.

Tenk for eksempel at du har lekser i 8 fag, men kun har tid til å gjøre lekser i 3 av dem. hvor mange måter kan du utvelge de 3 fagene som du skal gjøre lekser i?

La oss regne litt på dette eksempelet.

Når vi velger det første faget, er det 8 alternativer. Når vi skal velge fag nummer to er det 7 alternativer. Ved valg av nummber tre, har vi bare 6 alternativer igjen.

Vi bruker mulitplikasjonsprinsippet:

$$8\cdot7\cdot6=336\:\text{alternativer}$$

Dette ble et ganske stort tall, men vi er ennå ikke ferdige. Hvis vi sier at hvert fag er representert at en bokstav, og vi har valgt fagene a, b og c, så er det flere forskjellige måter vi kan ha trukket de forskjellige fagene på: (a,b,c)(a,c,b)(b,a,c),(b,c,a),(c,a,b) og (c,b,a). Vi bryr oss ikke om hvilken rekkefølge vi velger de tre fagene, så alle kombinasjonene ovenfor er de samme for oss.

For å se på hvor mange måter vi kan bytte om på de tre fagene, må vi tenke at det første faget vi velger er det 3 alternativer, i andre faget er det 2 alternativer og til slutt bare ett alternativ. Altså kan de tre fagene kombineres på
$$3\cdot2\cdot1=6\:\text{måter}$$

Hver kombinasjon av de 3 fagene går altså igjen 6 ganger blant de 336 mulighetene vi fant frem til ovenfor. Vi må altså dividere med 6 for å nå frem til det riktige svaret.

$$\frac{8\cdot7\cdot6}{3\cdot2\cdot1}=56$$

Det er altså 56 forskjellige kombinasjoner av tre-fags-pakker du kan gjøre lekser i.

La oss se litt nærmere på uttrykket ovenfor.

$$\frac{8\cdot7\cdot6}{3\cdot2\cdot1}$$

Vi forlenger brøker med 5\(\cdot\)4\(\cdot\)3\(\cdot\)2\(\cdot\)1.

$$\frac{8\cdot7\cdot6}{3\cdot2\cdot1}=\frac{8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\:\cdot5\cdot4\cdot3\cdot2\cdot1}$$

Dette kan vi omskrive ved hjelp av fakultetsfunksjonen(sett inn link)

$$\frac{8\cdot7\cdot6}{3\cdot2\cdot1}=\frac{8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\:\cdot5\cdot4\cdot3\cdot2\cdot1}=\frac{8!}{3!\cdot5!}=\frac{8!}{3!\cdot(8-3)!}$$

Vi har altså funnet en formel til hvordan man kan velge ut 3 elementer ut av en mengde på 8, hvis man kun kan velge den samme tingen én gang, og hvis rekkefølgen er likegyldig.

Denne formelen kan generaliseres til:
"hvis man ønsker å velge ut r elementer av en mengde, som består av n elementer":

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

Hvis man for eksempel vil finne ut av hvor mange pokerhender som eksisterer, altså hvor mange måter man kan dele ut 5 kort på fra en bunke på 52, der rekkefølgen er likegyldig (vi bryr oss jo ikke om vi får spar ess som første eller siste kort), bruker man formelen:

$$K_{52,5}=\frac{52!}{5!\cdot(52-5)!}=\frac{52!}{5!\cdot47!}=2.598.960$$

Det er altså over 2,5 millioner forskjellige pokerhender.

Hvis rekkefølgen betyr noe

Det er imidlertidig ikke alle tilfeller hvor rekkefølgen er likegyldig. Det kunne for eksempel være at du blir bedt om å velge dine topp 10 yndlings-CD'er ut fra en liste på 25 CD'er. Da er det i hvert fall ikke likegyldig hvilken du velger som nummer 1 og hvilken du velger som nummer 10.

Så da kan vi spørre, hvor mange måter vi kan lage en slik liste på?

Her kan du på førsteplassen velge din favoritt blant de 25 CD'ene. På andreplass kan du velge blandt de 23 som er igjen. Og så videre inntil du til slutt har 16 valgmuligheter til din 10. plass.

Kombinasjonene er derfor:

$$25\cdot24\cdot23\cdot22\cdot21\cdot20\cdot19\cdot18\cdot17\cdot16=11.861.676.288.000$$

Altså nesten 12 billioner måter man kan sette sammen en topp-10-liste på.

Vi ganger og dividere brøken med 15\(\cdot\)14\(\cdot\)13\(\cdot\)...\(\cdot\)3\(\cdot\)2\(\cdot\)1.

$$\frac{25\cdot24\cdot23\cdot22\cdot21\cdot20\cdot19\cdot18\cdot17\cdot16\cdot15\cdot14\cdot13\cdot...\cdot3\cdot2\cdot1}{15\cdot14\cdot13\cdot...\cdot3\cdot2\cdot1}$$

Vi skriver om brøken ved hjelp av fakultetsfunksjonen

$$\frac{25\cdot24\cdot23\cdot22\cdot21\cdot20\cdot19\cdot18\cdot17\cdot16\cdot15\cdot14\cdot13\cdot...\cdot3\cdot2\cdot1}{15\cdot14\cdot13\cdot...\cdot3\cdot2\cdot1}=$$

$$=\frac{25!}{15!}=\frac{25!}{(25-10)!}$$

Vi kan generalisere. Hvis vi velger ut r elementer fra en mengde på n mulige, hvor vi kun kan velge hvert element én gang, og hvor rekkefølgen betyr noe, kan det gjøres på følgende antall måter:

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

Et annet eksempel:

Vi spiller Mastermind, hvor man skal velge en kode bestående av 4 farger ut av de 8 fargene som er med i spillet. Hver farge kan kun velges én gang, og rekkefølgen av fargene teller. Vi spekulerer på hvor mange kombinasjoner man kan komme frem til. Svaret er:
$$P_{8,4}=\frac{8!}{(8-4)!}=\frac{8!}{4!}=1680\text{ forskellige koder}$$

Har du et spørsmål, du vil stille om Kombinatorikk? Send oss en mail!
Har du en kommentar til innholdet på denne siden? Send oss en mail!