Kombinasjoner

Vi bruker kombinasjoner når vi velger et bestemt antall objekter fra en mengde og rekkefølgen vi velger dem i, ikke har noe å si. Et typisk eksempel er lotto 6 av 49 — i urnen har vi 49 tall, og vi trekker 6 av dem, og det er likegyldig i hvilken rekkefølge vi trekker dem.

Utledning av formelen

Lykkehjul

La oss ha en mengde M, for eksempel M = {a, b, c, d, e}. Da er en k-kombinasjon en delmengde K ⊆ M som inneholder nøyaktig k elementer. Siden K er en mengde, har rekkefølgen selvsagt ingen betydning. En kombinasjon av tre elementer fra mengden M kunne altså være {a, b, d} eller {b, c, d}.

Forskjellen fra ordnet utvalg er at der hadde rekkefølgen noe å si, så (a, b, e) og (e, b, a) er ulike ordnede utvalg, men de er samme kombinasjon, for både (a, b, e) og (e, b, a) inneholder de samme elementene; at de står i en annen rekkefølge, bryr vi oss ikke om når det gjelder kombinasjoner.

Vi kan imidlertid bruke ordnet utvalg for å få en formel for antall ulike kombinasjoner. Vi vet at antall ordnede utvalg av k elementer fra en mengde med n elementer er nøyaktig

$_{n} P_{k} = \frac{n!}{(n - k)!} .$

Hvis vi regnet ut antall ordnede utvalg av tre elementer fra mengden M = {a, b, c, d, e} ovenfor, ville vi få {}₅P₃ = 60 ulike utvalg. Men der ville vi for hvert trippel også ha alle dets permutasjoner. Vi ville altså ha trippelet abc, men også acb, bac, bca, cab og cba. Dette er seks ulike ordnede utvalg, men det er én kombinasjon, for alle har de samme elementene.

Hvis vi har et trippel, hvor mange ulike permutasjoner av det finnes det? Nøyaktig 3!. Med andre ord finnes det nøyaktig 3! ganger så mange ordnede utvalg av tre elementer som kombinasjoner av tre elementer. I stedet for å regne med én kombinasjon regner vi med 3! ganger flere ordnede utvalg, ett for hver permutasjon av det aktuelle trippelet. Så hvis vi deler antall ordnede utvalg på 3!, får vi antall kombinasjoner.

Den forrige framgangsmåten kan vi generalisere og si at hvis vi leter etter antall ulike k-kombinasjoner fra en mengde med n elementer, er dette antallet, som vi kaller $(\binom{n}{k})$ , lik

$(\binom{n}{k}) = \frac{_{n} P_{k}}{k!},$

altså antall ordnede utvalg delt på k!, som er antall permutasjoner av hvert k-tuppel. Formelen kan vi skrive om ved å skrive ut formelen for antall ordnede utvalg:

$(\binom{n}{k}) = \frac{_{n} P_{k}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Eksempel: Antall kombinasjoner av to elementer fra mengden {a, b, c} er

$(\binom{3}{2}) = \frac{3!}{1! \cdot 2!} = 3$

og disse kombinasjonene er: {a, b}, {a, c} og {b, c}. For kombinasjoner av tre elementer fra den opprinnelige mengden M = {a, b, c, d, e} ville vi fått antallet

$(\binom{5}{3}) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

og disse kombinasjonene er: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Binomialkoeffisient

Tallet som vi brukte ovenfor, kalles binomialkoeffisient. Binomialkoeffisienten har denne formen

$(\binom{n}{k})$

Det er et slags brøkuttrykk uten brøkstrek (som du likevel av vane kommer til å skrive), men med parenteser (de er ikke valgfrie, de må være der). Binomialkoeffisienten leser vi «n over k». Verdien til binomialkoeffisienten er den samme som antall k-kombinasjoner fra n elementer.

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Så hvis vi har en mengde med 5 elementer og velger grupper på fire elementer fra den, blir det totale antallet

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Grunnleggende sammenhenger

For binomialkoeffisienten og n ∈ ℕ gjelder:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Videre gjelder for n, k ∈ ℕ₀ og k ≤ n

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

Og for n, k ∈ ℕ₀ og k < n gjelder

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Kalkulator

Den følgende kalkulatoren regner ut binomialkoeffisienten n over k.

Løste eksempler

Vi begynner med det nevnte lottospillet 6 av 49. Der trekker vi fra en urne med 49 kuler til sammen 6 kuler. Hvor mange ulike muligheter kan trekkes ut?

Først — har rekkefølgen vi trekker tallene i, noe å si? Nei, vi tipper bare tallene, ikke rekkefølgen. Vi skal bruke kombinasjoner. Vi har til sammen 49 kuler og trekker 6 kuler, og får binomialkoeffisienten

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13 983 816$

Det finnes til sammen 13 983 816 muligheter som kan trekkes ut. Dette gir oss forresten sannsynligheten for å vinne med én rekke 1/13 983 816, som er 0,00000715112 %.
Jakob, en kjent sjarmør, er akkurat på bygdedans, der det er til sammen 13 pene jenter han kunne tenke seg å være sammen med. Jakob vet at han klarer å gjøre 4 ulike jenter fornøyde i løpet av en kveld. Fra hvor mange ulike firergrupper kan Jakob velge?

Dette er igjen et enkelt eksempel på kombinasjoner, rekkefølgen har ikke noe å si, Jakob blir like god med den første jenta som med den siste. Vi får altså en mengde med 13 jenter, og fra den velger vi alltid 4 jenter. Det gir binomialkoeffisienten

$(\binom{13}{4}) = 715.$
Du har en gruppe på femti personer — halvparten menn og halvparten kvinner. Hvor mange ulike tripler av personer finnes det hvis de ikke får bestå av bare ett kjønn (altså: i trippelet kan det ikke være tre menn eller tre kvinner)?

Dette er en litt mer sammensatt kombinasjon. Hvis vi utelukker tripler med bare ett kjønn, står vi igjen med bare to muligheter for hvordan trippelet kan være sammensatt — to menn og én kvinne eller én mann og to kvinner, og antall kombinasjoner i den første gruppen (to menn og én kvinne) er det samme som antall kombinasjoner i den andre gruppen. Det holder altså å regne ut antall kombinasjoner i den første gruppen og multiplisere det med to. Nå er det igjen lett som en plett. Vi finner antall ulike par av menn, som er tjuefem over to, og multipliserer det med antall kombinasjoner av én kvinne (det er tjuefem, se grunnleggende sammenhenger ovenfor, nærmere bestemt andre linje). Dette resultatet multipliserer vi til slutt med to, og vi har det endelige resultatet.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
I en eske er det 15 produkter, og 4 av dem er defekte. På hvor mange måter kan vi velge 6 produkter slik at
- ingen er defekt? Nå velger vi 6 produkter fra 15 − 4 = 11 produkter som ikke er defekte. Vi får altså binomialkoeffisienten
  
  $(\binom{11}{6}) = 462.$
- nøyaktig ett produkt er defekt? Vi velger da en mengde som inneholder 5 feilfrie produkter og 1 defekt. Vi har til sammen 11 feilfrie produkter og 4 defekte. Vi bruker multiplikasjonsprinsippet og får resultatet:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- høyst ett er defekt? Til løsningen bruker vi de forrige resultatene. Vi vet at vi har til sammen 462 muligheter for å velge nøyaktig 6 feilfrie produkter, og vi har 1848 muligheter for å velge fem feilfrie og ett defekt produkt. Vi bruker altså addisjonsprinsippet, legger sammen resultatene og får det vi vil ha, nemlig høyst ett defekt produkt (= enten ingen defekte produkter eller nøyaktig ett). Resultatet er: 462 + 1848 = 2310.

Kapitler: Kombinatorikk, Ordnet utvalg, Permutasjoner, Kombinasjoner, Ordnet utvalg med tilbakelegging, Kombinasjoner med gjentakelse, Hvor mange ulike PIN-koder finnes det?

« Forrige: Permutasjoner

Neste: Ordnet utvalg med tilbakelegging »