Kombinatorikk

Innledning

For å kunne beregne sannsynligheter trenger man en oversikt over mulige utfall og kombinasjoner. I den forbindelse kan det være greit med noen regler for å få klarhet når situasjoner virker uoversiktlige.

Multiplikasjonsregelen

Dersom situasjonen består av flere trinnvise valg mellom flere elementer blir antall kombinasjoner som følger.:

Antall elementer i første valgrunde multiplisert med antall elementer i andre runde osv.

m ∙ n ∙ …..

Eksempel:

Hvor mange antrekk kan du velge dersom du har valget mellom to gensere, fire bukser og tre par sko?

Svar:

2 (gensere) ∙ 4 (bukser) ∙ 3 (par sko) = 24 (antrekk)

Fakultet

På hvor mange måter kan 5 personer plassere seg i en 5 seters sofa? Første person kan velge mellom 5 seter, andre person mellom 4 osv. Det gir følgende antall kombinasjoner

5∙(5-1) ∙(5-2) ∙(5-3) ∙ (5-4) = 5!

n artikler kan arrangeres på :

n ∙(n-1) ∙(n-2) ∙………..1 = n!

n! leses ”n fakultet”.

0! defineres lik 1

Eksempel:

10! = 10∙9∙8∙7∙6∙5∙4∙3∙2∙1= 3628800

Som man observerer blir fakulteter raskt store størrelse.

Eksempel:

På hvor mange måter kan bokstavene a, b, c, d og e arrangeres?

Fem bokstaver kan arrangeres på 5! Måter, altså 5! = 120 måter.

Ordnet utvalg med tilbakelegging

Vi har 4 kuler i en urne. Kulene er nummererte fra 1 til 4. Dersom vi trekker en gang har vi fire muligheter. Når vi har trukket legger vi kulen tilbake igjen og trekker på nytt, slik at det blir 4 muligheter i andre trekning også.

Dersom man foretar r trekninger blant n elementer gir det

<math>n^r</math> muligheter.

Rekkefølgen spiller en rolle slik at {1,2,3,3} er forskjellig fra {1,3,2,3}

Eksempel

Denne modellen kan brukes på fotballtipping. Du har en urne med tre kuler; H, U og B. Du trekker 12 ganger (kamper) og legger kulen tilbake i urnen hver gang. Antall mulige måter å fylle ut en rekke på blir da

<math>3^{12} = 531.441</math> måter.

Ordnet utvalg uten tilbakelegging

Dersom man har 10 kuler og skal trekke ut tre uten tilbakelegging vil man ha følgende muligheter:

1. trekning: 10 muligheter

2. trekning: 9 muligheter

3. trekning: 8 muligheter

Det gir oss 10 ∙ 9 ∙ 8 = 720 mulige kombinasjoner. Vi snakker om ordnede utvalg slik at {1,2,3} er forskjellig fra {1,3,2}, dvs. rekkefølgen spiller en rolle.

Dersom man trekker r elementer fra mengden n uten tilbakelegging skrives det nPr og kalkulatoren bør ha en funksjon for det. P står for permutasjoner. nPr er gitt som:

Eksempel:

På Bingobakken skole som har 500 elever skal det velges elevråd, og de bestemmer seg for å avgjøre det hele ved loddtrekning.

Det skal først trekkes en leder.

Så skal det trekkes en kasserer.

Så skal det trekkes et rådsmedlem.

Til slutt skal det trekkes en vararepresentant.

Hvor mange mulige sammensetninger kan elevrådet ved Bingobakken ha?

Her har rekkefølgen av trekkingen betydning fordi den avgjør hvilken funksjon personen skal ha.

n = 500 og r = 4

Man får da:

<math>500P4 = \frac{500!}{(500-4)!} = \frac{500!}{(496)!} =500 \cdot 499 \cdot 498 \cdot 497 = 6,18 \cdot 10^{10} </math> mulige permutasjoner.

Uordnet utvalg uten tilbakelegging

Dersom man skal velge ut to personer til en komité spiller det ingen rolle om man blir valgt som nummer en eller nummer to, enten er man med i komiteen eller så er man det ikke. Situasjonen kalles uordnet utvalg uten tilbakelegging. I slie situasjoner er {Eva, Ivar} identisk med {Ivar, Eva}. Om man tar utgangspunkt i formelen for ordnede utvalg og dividerer på antall muligheter de uttrukne elementene kan kombineres på får man:

Som er formelen for uordnede utvalg uten tilbakelegging eller binominalkoeffisienten. Den skrives også Slik:

<math> nCr = {n \choose r} </math>

Eksempel:

På Lottobakken skole, som har 500 elever, skal det velges elevråd. De bestemmer seg for å avgjøre det hele ved loddtrekning. De har funnet ut at elevrådet skal bestå av fire likeverdige medlemmer. Da har trekkingsrekkefølgen ingen betydning. Hvor mange forskjellige elevråd kan de få på Lottobakken?

Dette blir et uordnet utvalg uten tilbakelegging

n = 500 og r = 4

Vi får: