Kombinatorikk i spill

I artiklene om kombinatorikk lærer vi systematiske metoder for å beregne kombinasjonsmuligheter. Her skal vi bruke disse metodene, og litt til, for å beregne kombinasjonsmuligheter og sannsynligheter i noen spill og konkurranser.

Pokerhender

Pokerhånd med tress i damer

Det finnes forskjellige typer poker, her ser vi på varianten five-card draw, der en spiller får utdelt en hånd på 5 kort. Det vil si 5 kort trukket tilfeldig fra en stokk på 52 kort.

En pokerhånd kan vi betrakte som et uordnet utvalg uten tilbakelegging. Uordnet fordi det ikke spiller noen rolle hvilken rekkefølge kortene blir delt ut i, vi sorterer dem etterpå. Uten tilbakelegging fordi samme kort ikke kan deles ut mer enn én gang.

Kombinasjonene som gir en bestemt pokerhånd, er i noen tilfeller relativt enkle å finne, for eksempel royal straight flush, fordi denne hånden består av de fem høyeste kortene i samme farge. Det eneste som kan variere er fargen, så det finnes derfor bare 4 slike hender.

I andre pokerhender kan antall kombinasjoner være mer komplisert å beregne, for eksempel at det finnes 54 912 muligheter for tress. Noe som kompliserer i dette tilfellet, er at vi ikke bare kan se på hvilke muligheter vi har for tre like kort, men også må stille krav til de to andre kortene, slik at vi ikke får en hånd med fire like eller hus i stedet.

For å beregne sannsynligheter i poker dividerer vi antall mulige kombinasjoner i en bestemt type hånd på antall mulige kombinasjoner i en pokerhånd totalt.

I eksempel 2 i artikkelen om ordnede og uordnede utvalg beregner vi antall mulige kombinasjoner i en pokerhånd ved å beregne antall uordnede utvalg med 5 av 52 kort:

${\large \binom{52}{5}} = {\large \frac{52!}{5!(52 – 5)!}} = 2 \, 598\, 960$

Sannsynligheten for å få utdelt royal straight flush, for eksempel, blir da:

${\large \frac{4}{2 \, 598 \, 960}} \approx 1{,}539 \cdot 10^{-6}$, altså om lag 0,000154 %.

Antall kombinasjoner i andre pokerhender kan være mer kompliserte å finne.

En oversikt over sannsynligheter og tall på kortkombinasjoner i poker finnes på Wikipedia: pokersannsynlighet. Ta det som en utfordring å finne ut hvordan de er beregnet.

Tress

Her er en utregning for tress:

En kortstokk har 13 valører og 4 farger. Skal vi få tress, må vi ha 3 kort med samme valør, og det finnes altså 13 muligheter for dette. Vi kan få 3 toere, 3 treere, 3 firere, og så videre. Vi har altså ${\large \binom{13}{1}} = 13$ muligheter for valør. Det finnes også forskjellige muligheter for kombinasjon av farger. Vi kan kombinere spar/hjerter/ruter, spar/kløver/ruter, og så videre. Totalt ${\large \binom{4}{3}} = 4$ kombinasjonsmuligheter.

Det betyr at det finnes ${\large \binom{13}{1}} \cdot {\large \binom{4}{3}} = 13 \cdot 4 = 52$ kombinasjonsmuligheter for 3 kort med samme valør.

Siden en pokerhånd består av 5 kort, inneholder den 2 kort i tillegg til de 3 med samme valør. Disse 2 kan trekkes blant 49 gjenværende kort, noe som gir ${\large \binom{49}{2}} = 1176$ kombinasjonsmuligheter for de siste 2 kortene.

Men vi kan ikke tillate alle disse kombinasjonene. For hvis ett av kortene har samme valør som de tre like, har vi en pokerhånd med fire like, ikke tress. Det er imidlertid bare 1 av de 49 kortene som kan gi dette resultatet, vi kan fritt velge blant de 48 andre, noe som gir ${\large \binom{48}{2}} = 1128$ kombinasjonsmuligheter for de siste 2 kortene.

Vi kan heller ikke tillate at de 2 gjenværende kortene deler valør, for da har vi tre like pluss et par, noe som er hus i poker, og ikke tress. Så disse kombinasjonene må trekkes fra. For å regne ut hvor mange kombinasjoner det er, bruker vi samme prinsipp som vi innledningsvis brukte for å finne antall mulige kombinasjoner av 3 like kort. Men vi må huske at det nå bare er 12 tilgjengelige valører, så vi får ${\large \binom{12}{1}} = 12$ muligheter for valg av valør. Og vi får ${\large \binom{4}{2}} = 6$ kombinasjonsmuligheter for farger. Totalt 12 · 6 = 72 kombinasjoner som gir par. Vi sitter altså igjen med 1128 − 72 = 1056 lovlige kombinasjonsmuligheter for de siste 2 kortene.

Da gjenstår det bare å multiplisere antall kombinasjonsmuligheter for tre like kort med kombinasjonsmulighetene for de to siste kortene: 52 · 1056 = 54 912. Det finnes 54 912 forskjellige pokerhender med tress.

Sannsynligheten for å få utdelt tress er da

${\large \frac{54 \, 912}{2 \, 598 \, 960}} \approx 2{,}113 \cdot 10^{-2}$, altså om lag 2,113 %.

Når det gjelder kombinasjonsmuligheter for de siste 2 kortene, kan vi alternativt tenke slik: Vi kaller kortene A og B og trekker kort A først. Vi har da 49 kort å velge blant, hvorav 1 er «ulovlig», med samme valør som de 3 like. Altså 49 − 1 = 48 lovlige valg for A.
For B er det så 48 kort å velge blant, hvorav 1 er «ulovlig», med samme valør som de 3 like, og 3 er «ulovlige» med samme valør som A. Altså 48 − 1 − 3 = 44 lovlige valg for B.
Siden det ikke spiller noen rolle hvilket kort som er A og hvilket som er B, må vi dividere på antall måter å sortere A og B på, nemlig 2!. Og det totale antallet tillatte kombinasjoner blir ${\large \frac{48 \cdot 44}{2!}} = 1056$, som er det samme som vi fant tidligere.

Som et tredje alternativ for de 2 siste kortene kan vi tenke oss at vi for disse velger 2 ulike valører blant de 12 tilgjengelige, noe som gir ${\large \binom{12}{2}} = 66$ kombinasjonsmuligheter. Hvert av kortene kan velges fritt blant 4 farger, noe som totalt gir ${\large \binom{4}{1}} \cdot {\large \binom{4}{1}} = 16$ kombinasjonsmuligheter. Totalt gir det ${\large \binom{12}{2}} \cdot {\large \binom{4}{1}^2} = 66 \cdot 16 = 1056$ kombinasjonsmuligheter, som før.

Slår vi dette uttrykket sammen med uttrykket for antall kombinasjoner av 3 like kort, får vi et samlet uttrykk for antall mulige pokerhender med tress:
${\large \binom{13}{1}} \cdot {\large \binom{4}{3}} \cdot {\large \binom{12}{2}} \cdot {\large \binom{4}{1}^2} = 54 \,912$.

Lottorekker

Eksempler på lottotall med tilleggstall

Ei vinnerrekke i Lotto består av 7 tall mellom 1 og 34 trukket tilfeldig. Ei Lotto-rekke kan vi betrakte som et uordnet utvalg uten tilbakelegging. Uordnet fordi det ikke spiller noen rolle hvilken rekkefølge tallene blir trukket i, vi sorterer dem etterpå. Uten tilbakelegging fordi samme tall ikke kan trekkes mer enn én gang.

Vi spiller Lotto ved å sette opp 7 tall, som så blir sammenliknet med vinnerrekka. Det utbetales premie for 7, 6, 5 og 4 rette, samt for 6 rette + 1 tilleggstall, der tilleggstallet trekkes tilfeldig blant tallene som er tilbake når selve Lotto-rekka er trukket.

For å beregne vinnersannsynligheter i Lotto dividerer vi antall mulige vinnerrekker med antall mulige lottorekker totalt. Som vi beregner i eksempel 1 i artikkelen om ordnede og uordnede utvalg, er antall rekker totalt ${\large \frac{34!}{7!(34 – 7)!}} = 5 \, 379 \, 616$

Vi skal nå se på noen kombinasjonsmuligheter og sannsynligheter.

7 rette

Det finnes bare ei enkelt rekke med 7 rette, så sannsynligheten for å få dette er ${\large \frac{1}{5 \, 379 \, 616}} \approx 1{,}8589 \cdot 10^{-7}$.

Det er om lag 0,00001859 % sannsynlig å få 7 rette.

6 rette + tilleggstall

6 rette + 1 tilleggstall kan vi få ved å erstatte hvilket som helst av tallene i vinnerrekka med tilleggstallet, altså totalt 7 kombinasjonsmuligheter. Så sannsynligheten for dette blir ${\large \frac{7}{5 \, 379 \, 616}} \approx 1{,}3012 \cdot 10^{-6}$.

Det er om lag 0,00013012 % sannsynlig å få 6 rette + tilleggstall.

6 rette

Når 7 lottotall er trukket, gjenstår det 27 tall, og vi kan få 6 rette ved å erstatte hvilket som helst av tallene i vinnerrekka med et hvilket som helst av disse, altså 7 · 27 = 189 kombinasjonsmuligheter. Imidlertid vil 7 av disse inneholde tilleggstallet og gi gevinsten «6 + tilleggstall», så vi trekker dem fra, og står igjen med 182 kombinasjonsmuligheter. Sannsynligheten for dette blir ${\large \frac{182}{5 \, 379 \, 616}} \approx 3{,}3831 \cdot 10^{-5}$.

Det er om lag 0,0033831 % sannsynlig å få 6 rette.

5 rette

5 rette kan vi få ved å erstatte hvilken som helst av kombinasjon av 2 av de 7 tallene i vinnerrekka med en hvilken som helst kombinasjon av 2 av de 27 tallene som ikke er i vinnerrekka. Antall kombinasjonsmuligheter blir derfor ${\large \binom{7}{2}} \cdot {\large \binom{27}{2}} = 21 \cdot 351 = 7371$. Sannsynligheten for dette blir ${\large \frac{7371}{5 \, 379 \, 616}} \approx 1{,}3702 \cdot 10^{-3}$.

Det er om lag 0,13702 % sannsynlig å få 5 rette.

4 rette

Samme argument som for 5 rette gir at antall kombinasjonsmuligheter blir ${\large \binom{7}{3}} \cdot {\large \binom{27}{3}} = 35 \cdot 2925 = 102 \, 375$. Sannsynligheten for dette blir ${\large \frac{102 \, 375}{5 \, 379 \, 616}} \approx 1{,}9030 \cdot 10^{-2}$.

Det er om lag 1,903 % sannsynlig å få 4 rette.

0 rette

0 rette kan vi få ved en hvilken som helst kombinasjon av de 27 tallene som ikke er i vinnerrekka, så antall kombinasjonsmuligheter blir ${\large \binom{27}{7}} = 888 \, 030$. Sannsynligheten for dette blir ${\large \frac{888 \, 030}{5 \, 379 \, 616}} \approx 1{,}651 \cdot 10^{-1}$.

Det er om lag 16,507 % sannsynlig å få 0 rette på ei Lotto-rekke.

Sannsynligheten i lottorekker diskuteres også i lys av hypergeometriske fordelinger i eksempel 7 i statistikk-artikkelen om diskrete sannsynlighetsfordelinger.

Fischer-sjakk

I vanlig sjakk stiller spillerne opp de såkalte offiserene i rekkefølgen tårn, springer (hest), løper, dronning, konge, løper, springer, tårn:

Startoppstilling for offiserene i sjakk

Gjennom århundrer har imidlertid de første fasene i sjakkpartier blitt grundig analysert, og det er utviklet mye kunnskap om hvilke trekk som er bra og hvilke som er mindre bra. En sjakkspiller med god kunnskap om slik åpningsteori vil ha en klar fordel mot en spiller med mindre kunnskap.

Slik er det imidlertid ikke i Fischer-sjakk, oppfunnet av stormester Bobby Fischer, der offiserene stilles opp i tilfeldig rekkefølge.

Fischer-sjakk kalles også 960-sjakk fordi det finnes 960 forskjellige måter å stille offiserene opp på. Nå skal vi se hvordan vi kommer fram til dette tallet.

Tenker vi oss offiserene nummerert fra 1 til 8, vil det finnes 8! = 40 320 måter å organisere dem på. Men siden det ikke vil ha noen betydning om de to løperne bytter plass, eller om de to springerne bytter plass, blir det bare fjerdeparten så mange unike oppstillingsmuligheter, altså 10 080.

Det finnes imidlertid to spesialkrav til oppstillingen. Løperne må stå på forskjellig farge, som i vanlig sjakk, altså en løper på svart og en løper på hvitt felt. Dessuten må kongen stå mellom tårnene, slik at det er mulig å utføre rokade til begge sider, som i vanlig sjakk.

Utfordringen ved å innarbeide disse spesialkravene i beregningene ligger i å finne rett måte å angripe problemet på. Starter vi med et tårn, for eksempel, blir det hele komplisert fordi mulige plasseringer av kongen vil avhenge av hvor vi har plassert tårnet, og mulige plasseringer av det andre tårnet vil avhenge av hvor vi har plassert kongen.

I stedet starter vi med å plassere løperne. Første løper kan plasseres på ett av 8 felt, deretter kan andre løper plasseres på ett av de 4 feltene av motsatt farge, totalt 8 · 4 = 32 muligheter. Men siden det ikke vil ha noen betydning om løperne bytter plass, blir det bare halvparten så mange unike oppstillingsmuligheter, altså 16.

Når løperne er på plass, finnes det 6 · 5 = 30 muligheter for springerne, men, som for løperne, spiller det ingen rolle om de bytter plass, så det blir 15 unike oppstillingsmuligheter.

Så finnes det 4 muligheter for å plassere dronningen, deretter gjenstår det bare 3 ledige felt. Siden kongen skal stå mellom tårnene, kan de disse 3 brikkene da bare plasseres på 1 måte.

Totalt blir det altså 16 · 15 · 4 · 1 = 960 unike oppstillingsmuligheter. Blant disse inngår også oppstillingen i vanlig sjakk, så det finnes totalt 959 alternative oppstillinger.

Rett person i rett hus

Fem pepperkakehus

I TV-serien Hvem bor her er poenget å avgjøre hvem av 5 personer som bor i hvilket av 5 hus. Konseptet går egentlig ut på å knytte personlighetstyper til interiør, men la oss si at vi bare gjetter tilfeldig. Hva er da sannsynligheten for å plassere henholdsvis 0, 1, 2, 3, 4 og 5 personer i rett hus?

Totalt kan 5 personer plasseres i husene på 5! = 120 forskjellige måter.

For å beregne hvor mange av disse plasseringene som er uten noen person i rett hus, trenger vi et begrep som heter subfakultet (min oversettelse av subfactorial). Subfakultetet til n angir antall mulige permutasjoner av n elementer der ingen av elementene er på sin opprinnelige plass.

Subfakultetet til n skrives som !n, vi setter altså et utropstegnet foran tallet vi vil beregne subfakultetet til, ikke bak, som ved vanlig fakultet.

Det finnes flere måter å beregne !n på. For eksempel ved hjelp av rekka 

$!n = n! {\displaystyle \sum_{m=0}^n} {\large \frac{(-1)^m}{m!}}$, der n ≥ 0.

som gir

$!0 = 0! \cdot {\large \frac{(-1)^0}{0!}} = 1 \cdot \frac{1}{1} = 1$
Det samme som 0!

$!1 = 1! \cdot \Big({\large \frac{(-1)^0}{0!} + \frac{(-1)^1}{1!}} \Big)= 1 \cdot \big( 1 -1 \big) = 0$
Det er lett å skjønne at dette må være riktig, siden det for 1 enkelt verdi ikke finnes alternative plasser.

$!2 = 2! \cdot \Big({\large \frac{(-1)^0}{0!}} + {\large \frac{(-1)^1}{1!}} + {\large \frac{(-1)^2}{2!}} \Big)= 2 \cdot \big( 1 – 1 + {\large \frac{1}{2}} \big) = 1$
Det er også lett å skjønne at dette må være riktig, for 2 verdier kan bare bytte plass med hverandre.

Videre får vi !3 = 2, !4 = 9, !5 = 44.

Det finnes altså !5 = 44 måter å plassere 5 personer i 5 hus på uten at noen er på rett plass.

Vil vi ha nøyaktig 1 person i rett hus, finnes det 5 muligheter for dette, og de resterende 4 kan da plasseres i feil hus på !4 = 9 måter. Totalt 5 · 9 = 45 kombinasjonsmuligheter.

Generelt vil n av 5 på rett plass kunne kombineres på ${\large \binom{5}{n}}$ måter, og de resterende på !(5-n) måter.

For n = 0 … 5 får vi

n ${\large \binom{5}{n}}$ !(5-n) Kombinasjoner
0 1 44 1 · 44 = 44
1 5 9 5 · 9 = 45
2 10 2 10 · 2 = 20
3 10 1 10 · 1 = 10
4 5 0 5 · 0 = 0
5 1 1 1 · 1 = 1

For å finne de tilhørende sannsynlighetene hvis vi gjetter tilfeldig, dividerer vi antall kombinasjoner med 120, som er antall kombinasjoner totalt:

  • Ingen i rett hus: ca. 36,67 % sannsynlighet.
  • 1 i rett hus: 37,5 % sannsynlighet.
  • 2 i rett hus: ca. 16,67 % sannsynlighet.
  • 3 i rett hus: ca. 8,33 % sannsynlighet.
  • 4 i rett hus: 0 % sannsynlighet.
  • Alle i rett hus: ca. 0,83 % sannsynlighet.

Kilder

Vekst av kombinasjonsmuligheter

Lysets hastighet er enorm. En lysstråle som forlater jorden i dag, vil om ett år ha nådd om lag 9,5 billioner kilometer ut i rommet. Men om to år vil den bare ha nådd dobbelt så langt, om ti år ti ganger så langt, og om n år n ganger så langt. Selv om hastigheten er stor, øker avstanden lyset tilbakelegger bare proporsjonalt, altså lineært, med antall år.

Når vi studerer kombinasjoner, øker imidlertid antall kombinasjonsmuligheter eksponentielt med antall elementer tilgjengelig. Hvis vi doblet antall kamper i ei tipperekke fra 12 til 24, ville ikke antall kombinasjonsmuligheter bli doblet, men øke fra 312 til 324, det vil si fra litt over fem hundre tusen til nesten tre hundre milliarder.

Eksempel 1:

I sjakk finnes det 20 forskjellige måter hvit kan åpne på (16 flytt med bønder og 4 med springere), og 20 måter svart kan svare på. Det gir totalt 400 kombinasjonsmuligheter allerede i første trekk. Nøyaktig hvor mange måter en kan flytte på i senere trekk vil avhenge av hvilke trekk som tidligere er gjort, men antall kombinasjoner øker uansett eksponentielt med antall trekk. Selv det kraftigste sjakkprogram klarer derfor ikke å vurdere kombinasjonene av alle mulige trekk i et parti fra åpning til slutt.

Eksempel 2:

Det sies at en ape med en skrivemaskin før eller siden vil skrive Shakespeares samlede verker. Tanken bak dette er at det finnes et endelig antall skrifttegn, og derved et endelig antall kombinasjoner av skrifttegn. Problemet er bare at antall kombinasjonsmuligheter vokser eksponentielt med antall tegn.

La oss for enkelhets skyld si at skrivemaskinen har 30 tegn tilgjengelig, de 26 latinske bokstavene a-z pluss 4 skilletegn. Så setter vi oss fore å skrive ned alle mulige tekster med et gitt antall tegn, og vi bruker 0,2 sekunder per tegn.

For en tekst med ett tegn vil det finnes 30 muligheter, som totalt tar 30 · 0,2 = 6 sekunder å skrive.

For en tekst med to tegn vil det finnes 30 · 30 = 900 muligheter, som totalt tar 900 · (0,2 + 0,2) = 360 sekunder å skrive, altså 6 minutter.

For en tekst med seks tegn vil det finnes 306 = 729 000 000 muligheter, som totalt tar 729 000 000 · (6 · 0,2) = 874 800 000 sekunder å skrive. Dette er om lag 27,7 år.

For en tekst med tolv tegn vil det finnes 3012 ≈ 5,3 · 1017 muligheter, som totalt tar 5,3 · 1017 · (12 · 0,2) ≈ 1,3 · 1018 sekunder å skrive. Dette er om lag 40 milliarder år, noe som er 8 ganger mer enn det som regnes som den gjenstående levetiden til solen.

Så vi skjønner at det vil ta sin tid før Shakespeares samlede verker blir ferdige med denne metoden.

Eksempel 3:

Grunnen til at det ofte kreves at passord skal inneholde små og store bokstaver, tall og spesialtegn, samt være av en viss lengde, er å gjøre antall mulige passord så mange at det blir vanskelig for en angriper å gjette seg fram til passordet. Antall mulige passord øker nemlig eksponentielt med både lengden og antall mulige tegn. La oss si at en datamaskin kan gjette en milliard kombinasjoner i sekundet. Regner vi med 29 bokstaver, 10 tall og 30 spesialtegn, viser tabellen under hvor lang tid datamaskinen vil bruke på å prøve alle mulige kombinasjoner, avrundet til hele enheter.

  8 tegn 9 tegn 10 tegn 11 tegn 12 tegn
Bare små bokstaver 8 minutter 4 timer 5 dager 141 dager 11 år
Store og små bokstaver 1 dag 86 dager 14 år 792 år 45 955 år
Bokstaver og tall 5 dager 1 år 67 år 4558 år 309 956 år
Bokstaver, tall og spesialtegn 98 dager 26 år 2591 år 253 910 år 24 883 204 år

Vi ser at vi ved å øke lengden fra 8 til 12 tegn og å inkludere alle tegntyper, går fra ca. 8 minutter til nesten 25 millioner år.

Uordnede utvalg med tilbakelegging

I artikkelen om ordnede og uordnede utvalg beregner vi antall uordnede utvalg ved å dividere antall ordnede utvalg med antall måter utvalget kan organiseres på. Hvis vi for eksempel trekker 2 ganger fra en mengde med 3 elementer, finnes det 3 · 2 = 6 ordnede utvalg som kan organiseres på 2! = 2 måter, noe som gir ${\large \frac{6}{2}} = 3$ uordnede utvalg. Heter elementene A, B og C, kan vi få de 6 ordnede utvalgene A-B, A-C, B-A, B-C, C-A og C-B. Dette utgjør 3 uordnede utvalg fordi, når rekkefølgen på elementene ikke spiller noen rolle, er A-B samme utvalg som B-A, A-C er samme utvalg som C-A, og B-C er samme utvalg som C-B.

De 3 uordnede utvalgene blir altså mengdene {A, B}, {A, C} og {B, C}.

Dette forutsetter imidlertid at vi trekker uten tilbakelegging. Trekker vi med tilbakelegging, blir situasjonen mer sammensatt fordi vi kan trekke samme element flere ganger.

Hvis vi for eksempel trekker 2 ganger fra en mengde med 3 elementer, finnes det 32 = 9 mulige ordnede utvalg. Heter elementene A, B og C, kan vi få de 9 ordnede utvalgene A-A, A-B, A-C, B-A, B-B, B-C, C-A, C-B og C-C. Her ser vi at mens utvalgene med to forskjellige elementer kan organiseres på 2 måter, kan utvalgene med to like elementer, altså A-A, B-B og C-C, bare organiseres på 1 måte.

Totalt får vi altså 6 mulige uordnede utvalg, som består av mengdene {A, A}, {A, B}, {A, C}, {B, B}, {B, C} og {C, C}.

Mange lærebøker tar overhodet ikke for seg beregning av antall uordnede utvalg med tilbakelegging, og vi skal heller ikke gå i detaljer, men vi skal i hvert fall presentere en formel. Hvis vi trekker k ganger fra en mengde på n elementer med tilbakelegging, vil antallet uordnede utvalg bli ${\large \binom{n + k – 1}{k}}$.

$\fbox{Antall uordnede utvalg med $k$ elementer av totalt $n$ ved trekning med tilbakelegging: ${\large \binom{n + k – 1}{k}}$}$

Eksempel 1:

Vi trekker k = 2 ganger fra en mengde med n = 3 elementer, med tilbakelegging. Vi får da

${\large \binom{n + k – 1}{k}} = {\large \binom{3 + 2 – 1}{2}} = {\large \binom{4}{2}} = {\large \frac{4!}{2!(4 – 2)!}} = {\large \frac{24}{2 \cdot 2}} = 6$

mulige uordnede utvalg, slik vi så over, der vi trakk 2 ganger fra mengden {A, B, C}.

Begrepet tilbakelegging skal vi imidlertid ikke alltid ta bokstavelig. Ofte er bare situasjonen at vi kan velge fra en mengde som ikke endrer seg.

Eksempel 2:

Vi skal kjøpe 4 frukter, og kan velge mellom eple, pære og appelsin. Hvor mange forskjellige kombinasjoner er da mulige?

Dette er et uordnet utvalg på k = 4 fra en mengde på totalt n = 3. Så vi får:

${\large \binom{n + k – 1}{k}} = {\large \binom{3 + 4 – 1}{4}} = {\large \binom{6}{4}} = {\large \frac{6!}{4!(6 – 4)!}} = {\large \frac{720}{24 \cdot 2}} = 15$

Vi kan kontroller utregningen ved å sette opp alle mulighetene. Vi kaller eple E, pære P, og appelsin A:

        1. EEEE. 4 epler.
        2. EEEP. 3 epler og 1 pære.
        3. EEEA. 3 epler og 1 appelsin.
        4. EEPP. 2 epler og 2 pærer.
        5. EEPA. 2 epler, 1 pære og 1 appelsin.
        6. EEAA. 2 epler og 2 appelsiner.
        7. EPPP. 1 eple og 3 pærer.
        8. EPPA. 1 eple, 2 pærer og 1 appelsin.
        9. EPAA. 1 eple. 1 pære og 2 appelsiner.
        10. EAAA. 1 eple og 3 appelsiner.
        11. PPPP. 4 pærer.
        12. PPPA. 3 pærer og 1 appelsin.
        13. PPAA. 2 pærer og 2 appelsiner.
        14. PAAA. 1 pære og 3 appelsiner.
        15. AAAA. 4 appelsiner.

Oppgave 1:

En iskremkiosk har is med 10 forskjellige smaker, og du kjøper en kjeks med 3 iskremkuler. Hvor mange smakskombinasjoner kan du få hvis du kan velge flere kuler av samme type? Hvor mange smakskombinasjoner kan du få hvis du bare velger forskjellige typer?

Se løsningsforslag

Ordnede utvalg med tilbakelegging

I artikkelen om ordnede og uordnede utvalg og artikkelen om utvalg fra blandede mengder beregner vi kombinasjonsmuligheter når vi trekker fra en mengde. Uten at vi presiserer det, trekker vi der uten tilbakelegging. Det vil si at når et element først er trukket ut, kan vi ikke trekke det på nytt. Nå skal vi se på «trekking med tilbakelegging», det vil si at vi legger uttrukne elementeter tilbake i den opprinnelige mengden, slik at de kan trekkes på nytt.

Som vi ser i artikkelen om permutasjoner, har vi, når vi trekker fra en mengde med n elementer, n valgmuligheter i første trekning, n−1 i andre, deretter n−2 og så videre. Vi har ikke tilbakelegging, så for hver trekning blir det ett element mindre å velge blant.

Trekker vi derimot flere ganger med tilbakelegging fra en mengde på n elementer, har vi hver gang n elementer å velge blant. Trekker vi 2 ganger, får vi n2 mulige ordnede utvalg, trekker vi 3 ganger, får vi n3 mulige ordnede utvalg, og trekker vi k ganger, får vi nk mulige ordnede utvalg.

$\fbox{Antall ordnede utvalg med $k$ elementer av totalt $n$ ved tilbakelegging: $n^k$}$

Når vi trekker uten tilbakelegging, kan vi jo ikke trekke flere elementer enn de vi har, så k ≤ n. Noen slik begrensning eksisterer ikke med tilbakelegging, vi kan trekke så mange ganger vi vil.

Eksempel 1:

I eksempel 1 i artikkelen om ordnede og uordnede utvalg beregner vi at det finnes 27 113 264 460 mulige ordnede utvalg når vi trekker 7 av 34 lottokuler uten tilbakelegging. Trekker vi med tilbakelegging, finnes det 347 = 52 523 350 144 mulige ordnede utvalg, ca. 94 % flere.

Dersom vi trekker få ganger blant mange elementer, blir forskjellen på antall utvalg med og uten tilbakelegging liten.

Eksempel 2:

Vi har 100 nummererte kuler, og trekker 2.

Uten tilbakelegging gir det 100 · 99 = 9900 mulige ordnede utvalg. Med tilbakelegging gir det 1002 = 10 000 mulige ordnede utvalg, ca. 1 % flere.

Begrepet tilbakelegging skal vi imidlertid ikke alltid ta bokstavelig. Ofte er bare situasjonen at vi kan velge fra en mengde som ikke endrer seg.

Eksempel 3:

Ei rekke på en tippekupong består 12 kamper, der vi for hver kamp har valgmulighetene ‘H’, ‘U’ og ‘B’. Dette endrer seg aldri, vi vil for alle kamper kunne velge fra mengden som består av ‘H’, ‘U’ og ‘B’. Vi kan derfor tenke på tipping som å gjøre et utvalg med tilbakelegging. Utvalget er ordnet fordi rekkefølgen på kampene har betydning.

En tippekupong vil følgelig kunne fylles ut på 312 = 531 441 måter, siden vi velger 12 ganger fra en mengde på 3 elementer.

Sannsynligheten for å få 12 rette hvis vi setter opp ei rekke tilfeldig, er

Hvis vi fyller ut tilfeldig, gir «gunstige på mulige» at sannsynligheten for å få 12 rette er ${\large \frac{1}{531 \, 441}} \approx 1{,}882\cdot 10^{−6}$, om lag 0,00019 %.

Ikke mye, men 10 ganger mer enn sannsynligheten for å vinne hovedgevinsten i Lotto.

I motsetning til i Lotto kan vi imidlertid i Tipping forbedre vinnersjansene ved å ikke velge tilfeldig, men ta hensyn til kvaliteten på lagene som spiller, og velge ut fra dette.

Dette er en forskjell på Lotto og Tipping. I Lotto har vi ingen mulighet til å forutse resultatet, alle mulige kombinasjoner er like sannsynlige. Slik er det ikke i Tipping, der sannsynlighetene varierer med hvilke lag som spiller. Så selv om å velge tilfeldig er en fin strategi i Lotto, er det ikke det i Tipping.

Oppgave 1:

En kodelås består av tre kodehjul, hvert med sifre fra 0 til 9. Beregn hvor mange mulige koder som kan stilles inn på låsen.

Se løsningsforslag

Kilder

    • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
    • Hagen, Per C. (2000). Innføring i sannsynlighetsregning og statistikk. Cappelen akademisk
    • Birkeland, P.A., Breiteig, B., Venheim, R. (2012). Matematikk for lærere 2. Universitetsforlaget

Kombinasjoner og sannsynligheter

Når vi har en uniform modell, det vil si at alle elementer i en mengde har samme sannsynlighet for å bli trukket ut, kan vi beregne sannsynligheten for en kombinasjon av elementer ved å bruke «gunstige på mulige», der gunstige er antall gunstige kombinasjoner, og mulige er antall mulige kombinasjoner totalt.

Eksempel 1:

I Lotto trekkes ei vinnerrekke på 7 tall av 34 mulige. Så skal vi beregne sannsynligheten for å tippe vinnnerrekka.

Det finnes ${\large \frac{34!}{7!(34 − 7)!}} = 5 \, 379 \, 616$ kombinasjoner totalt med 7 av 34 tall. Av disse er bare 1 gunstig, nemlig vinnerrekka. Så sannsynligheten for å tippe riktig blir ${\large \frac{1}{5 \, 379 \, 616}} \approx 1{,}859 \cdot 10^{−7}$.

Sannsynligheten er om lag 0,0000186 %.

Eksempel 2:

Vi skal beregne sannsynligheten for å få utdelt en bridgehånd med nøyaktig åtte ruter.

Det finnnes ${\large \binom{13}{8}} \cdot {\large \binom{39}{5}}$ bridgehender med nøyaktig åtte ruter, slik vi beregner i eksempel 3 i artikkelen om utvalg fra blandede mengder.

En bridgehånd består av 13 av 52 kort, så det finnes totalt ${\large \binom{52}{13}}$ mulige bridgehender.

Sannsynligheten for å få en bridgehånd med nøyaktig åtte ruter blir derfor

${\large \frac{{\Large \binom{13}{8}} \cdot {\Large \binom{39}{5}}}{{\Large \binom{52}{13}}}} = {\large\frac{1287 \, \cdot \, 575\,757}{ 635 \, 013 \, 559 \, 600}} = {\large\frac{740 \, 999 \, 259}{ 635 \, 013 \, 559 \, 600}} \approx 1{,}1669 \cdot 10^{-3}$.

Sannsynligheten er om lag 0,117 %.

Oppgave 1:

En pokerhånd består av 5 kort delt ut fra en stokk med 52 kort. Beregn sannsynligheten for å få utdelt en pokerhånd med nøyaktig 3 ess.

Se løsningsforslag

Eksempel 3:

Vi skal beregne sannsynligheten for å få utdelt en pokerhånd som inneholder spar ess.

Denne hånden vil inneholde 1 kort som velges blant 1 spar ess, og 4 kort som velges blant 51 kort som ikke er spar ess, noe som gir ${\large \binom{1}{1}} \cdot {\large\binom{51}{4}}$ kombinasjonsmuligheter.

Totalt finnes det ${\large \binom{52}{5}}$ mulige pokerhender.

Sannsynligheten for å få en pokerhånd som inneholder spar ess blir derfor ${\large \frac{{\Large \binom{1}{1}} \cdot {\Large \binom{51}{4}}}{{\Large \binom{52}{5}}}} = {\large\frac{1 \, \cdot \, 249 \, 900}{ 2 \, 598 \, 960}} \approx 9{,}6154 \cdot 10^{-2}$.

Sannsynligheten er om lag 9,615 %.

Men hvis vi i stedet for å regne ut desimalverdien av brøken faktoriserer teller og nevner, får vi

$\frac{\displaystyle 2 \cdot 2 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdot 17}{\displaystyle 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \cdot 7 \cdot 7 \cdot 13 \cdot 17}$

Her er mange faktorer som kan forkortes, og forkorter vi brøken så langt det går, står vi igjen med ${\large \frac{5}{52}}$.

Dette virker kanskje litt pussig, men modellerer vi situasjonen på en annen måte, skjønner vi hvor dette tallet kommer fra. Trekker vi et kort fra en kortstokk, er sannsynligheten for at det er spar ess ${\large \frac{1}{52}}$. Trekker vi fem kort, er sannsynligheten for at spar ess er blant dem ${\large \frac{5}{52}}$.

Her regner vi «gunstige på mulige» direkte.

Det vil ofte være flere måter å modellere en situasjon på, slik som i eksempel 3.

Oppgave 2:

I en boks ligger 10 kuler som er merket fra A til J. Vi trekker et utvalg på tre kuler tilfeldig. Bruk kombinasjonsformelen til å beregne sannsynligheten for at utvalget inneholder kule A. Undersøk om du kan modellere situasjonen på en annen måte og få samme svar.

Se løsningsforslag

Kilder

    • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
    • Hagen, Per C. (2000). Innføring i sannsynlighetsregning og statistikk. Cappelen akademisk
    • Birkeland, P.A., Breiteig, B., Venheim, R. (2012). Matematikk for lærere 2. Universitetsforlaget

Utvalg fra blandede mengder

I artikkelen om permutasjoner og artikkelen om ordnede og uordnede utvalg ser vi på hvor mange kombinasjoner vi kan danne av enhetlige mengder, det vil si mengder som bare inneholder én type ting, for eksempel lottokuler eller personer. Inneholder mengdene forskjellige typer ting, må vi utvide logikken litt. Vi illustrerer med noen eksempler:

Eksempel 1:

Fra en idrettsgruppe som består av 11 gutter og 8 jenter skal det velges 4 representanter, og vi vil finne ut hvor mange måter representantene kan kombineres på når vi krever at det skal velges 2 jenter og 2 gutter.

Her er vi egentlig ute etter to delmengder, én der 2 gutter velges blant 11, og én der 2 jenter velges blant 8.

2 gutter kan velges blant 11 på ${\large \binom{11}{2}} = {\large \frac{11!}{2!(11 − 2)!}} = 55$ måter.

2 jenter kan velges blant 8 på ${\large \binom{8}{2}} = {\large \frac{8!}{2!(8 − 2)!}} = 28$ måter.

Alle disse variantene kan kombineres med hverandre, så 2 jenter og 2 gutter kan velges på 55 · 28 = 1540 måter.

Vi beregner altså antall elementer i hver av delmengdene og multipliserer dem etterpå.

Vi dropper ofte å føre mellomregningene, og skriver bare utregningen i eksempel 1 som ${\large \binom{11}{2}} \cdot {\large \binom{8}{2}} = 55 \cdot 28 = 1540$.

Eksempel 2:

Fra idrettsgruppa i eksempel 1, som består av 11 gutter og 8 jenter, skal det velges 2 representanter, og vi vil finne ut hvor mange kombinasjoner av representanter det finnes med henholdsvis:

      • 2 gutter og ingen jenter.
         
      • Ingen gutter og 2 jenter.
         
      • 1 av hvert kjønn.

Vi får:

      • 2 gutter og ingen jenter: ${\large \binom{11}{2}} \cdot {\large \binom{8}{0}} = 55 \cdot 1 = 55$.
         
        Her ser vi at vi egentlig ikke trenger å ta med ${\large \binom{8}{0}}$ fordi dette uttrykket blir lik 1. Vi kan tenke på det som at «ingen jenter» bare kan bare velges på 1 måte. Vi trenger sant å si heller ikke tenke på at vi trekker fra en blandet mengde, fordi vi bare trekker gutter. Imidlertid kan det være lurt å stille opp hele regnestykket slik det er gjort, fordi det tydeliggjør metoden, og vi slipper å lage spesialtilfeller når vi skal velge 0.
         
      •  Ingen gutter og 2 jenter: ${\large \binom{11}{0}} \cdot {\large \binom{8}{2}} = 1 \cdot 28 = 28$.
         
        Her får vi også en faktor som er lik 1, av samme grunn som når vi bare trekker gutter.
         
      • 1 av hvert kjønn: ${\large \binom{11}{1}} \cdot {\large \binom{8}{1}} = 11 \cdot 8 = 88$.

Her kunne vi nøyd oss med å stille opp 11 · 8, fordi vi blant 11 gutter kan velge 11 forskjellige, og blant 8 jenter kan velge 8 forskjellige. Men vi stiller opp hele regnestykket slik det er gjort, fordi det tydeliggjør metoden, og vi slipper å lage spesialtilfeller når vi skal velge 1.

Oppgave 1:

Ta utgangspunkt i gruppa i eksempel 1 og 2, med 11 gutter og 8 jenter, og beregn hvor mange kombinasjoner det finnes med

  1. 3 gutter og 3 jenter
     
  2. 1 gutt og 3 jenter
     
  3.  Ingen gutter og 4 jenter

Se løsningsforslag

RegnearkLast ned regneark der du kan regne ut antall mulige elevutvalg

Eksempel 3:

En bridgehånd består av 13 kort. Vi vil finne ut hvor mange bridgehender som inneholder nøyaktig åtte ruter.

Det er ikke så tydelig som i eksempel 1 og 2, men også her skal vi velge to delmengder fra to mengder. Den ene mengden består av alle kort som er ruter, totalt 13 stykker. Den andre mengden består av alle kort som ikke er ruter, totalt 52 − 13 = 39 stykker. Fra mengden med ruter skal vi så velge 8 kort. Siden en bridgehånd består av totalt 13 kort, blir det da 13 − 8 = 5 kort som skal velges blant kortene som ikke er ruter.

Totalt gir det ${\large \binom{13}{8}} \cdot {\large \binom{39}{5}} = 1287 \cdot 575 \, 757= 740 \, 999 \, 259$ mulige hender med nøyaktig åtte ruter.

Oppgave 2:

Beregn hvor mange korthender med 5 kort det finnes som

  1. inneholder nøyaktig 2 spar.
     
  2. bare inneholder spar.
     
  3. inneholder spar konge.

Se løsningsforslag

Prinsippet kan utvides til et vilkårlig antall mengder.

Eksempel 4:

En bedrift har fire avdelinger, der det arbeider henholdsvis 7, 11, 4 og 13 personer. Så skal vi regne ut hvor mange utvalg på 8 personer det finnes med to representanter fra hver avdeling.

Dette blir ${\large \binom{7}{2}} \cdot {\large \binom{11}{2}} \cdot {\large \binom{4}{2}} \cdot {\large \binom{13}{2}} = 21 \cdot 55 \cdot 6 \cdot 78 = 540\,540$.

SkjermfilmSe filmen «Blandede mengder»

Kilder

    • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
    • Hagen, Per C. (2000). Innføring i sannsynlighetsregning og statistikk. Cappelen akademisk
    • Birkeland, P.A., Breiteig, B., Venheim, R. (2012). Matematikk for lærere 2. Universitetsforlaget

Utvalg og delmengder

Delmengder

I sannsynlighet-artikkelen om mengder blir vi kjent med begrepet mengder, og ser hvordan vi kan illustrere mengder ved hjelp av Venn-diagrammer. Vi lærer også om delmengder, der mengder inngår i mengder.

Nå skal vi finne ut hvor mange delmengder det går an å lage i en mengde. Venn-diagrammene under viser en mengde med tre elementer, nemlig tallene 1, 2 og 3, og hvordan disse tallene kan organiseres i delmengder.

Illustrasjon av mengde uten delmengder Illustrasjon av mengde med delmengder med ett element Illustrasjon av mengde med delmengder med to elementer Illustrasjon av mengde med delmengder med tre elementer

Vi ser at vi kan lage 3 delmengder med ett tall i hver, og 3 med to tall i hver. Vi krever ikke at delmengdene skal være ekte, så vi har også 1 delmengde som inneholder alle tallene. Siden mengden med 0 elementer, ∅, også er en delmengde, blir det totalt 3 + 3 + 1 + 1 = 8 mulige delmengder.

Det er lett å se for seg at en mengde med to elementer vil kunne inneholde 4 delmengder, nemlig 2 med ett element i hver, 1 med to elementer, og ∅. En mengde med ett element vil kunne inneholde 2 delmengder, nemlig 1 med ett element, og ∅. En mengde med 0 elementer vil bare kunne inneholde ∅.

I alle tilfeller blir antall delmengder lik 2n, der n er antall elementer. 20 = 1, 21 = 2, 22 = 4, 23 = 8. Grunnen til at det er slik, er at det for hvert element finnes to muligheter: Elementet kan være med i en delmengde eller ikke. Har vi en mengde med m delmengder og introduserer et nytt element, vil vi kunne lage m nye delmengder som inkluderer det nye elementet, og får doblet antall mulige delmengder.

$\fbox{En mengde med $n$ elementer kan inneholde $2^n$ delmengder}$

Oppgave 1:

En mengde, A, inneholder elementene a, b og c: A = {a, b, c}. List opp de mulige delmengdene som kan lages i denne mengden. Stemmer det totale antallet delmengder med formelen for antall delmengder?

Se løsningsforslag

Delmengder er egentlig uordnede utvalg av elementer i en mengde, slik vi studerer i artikkelen om ordnede og uordnede utvalg. For eksempel er hver mulig vinnerrekke i Lotto en delmengde med 7 tall i en mengde på totalt 34.

Eksempel 2:

Vi har en mengde med 4 elementer, og bruker kombinasjonsformelen til å beregne hvor mange uordnede utvalg som kan lages med henholdsvis 0, 1, 2, 3 og 4 elementer:

0 elementer: ${\large \binom{4}{0}} = {\large \frac{4!}{0!(4 – 0)!}} = {\large \frac{24}{1 \cdot 24}} = 1$

1 element: ${\large \binom{4}{1}} = {\large \frac{4!}{1!(4 – 1)!}} = {\large \frac{24}{1 \cdot 6}} = 4$

2 elementer: ${\large \binom{4}{2}} = {\large \frac{4!}{2!(4 – 2)!}} = {\large \frac{24}{2 \cdot 2}} = 6$

3 elementer: ${\large \binom{4}{3}} = {\large \frac{4!}{3!(4 – 3)!}} = {\large \frac{24}{6 \cdot 1}} = 4$

4 elementer: ${\large \binom{4}{4}} = {\large \frac{4!}{4!(4 – 4)!}} = {\large \frac{24}{24 \cdot 1}} = 1$

Totalt blir dette 1 + 4 + 6 + 4 + 1 = 16 mulige delmengder. Dette stemmer med formelen for antall mulige delmengder, som sier at en mengde med 4 elementer har 24 = 16 mulige delmengder.

Oppgave 2:

Vi har en mengde med 3 elementer. Bruk kombinasjonsformelen til å beregne hvor mange uordnede utvalg som kan lages med henholdsvis 0, 1, 2 og 3 elementer. Sjekk om det totale antallet stemmer med formelen for antall mulige delmengder.

Se løsningsforslag

SkjermfilmSe filmen «Delmengder»
 

Kilder

    • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
    • Hagen, Per C. (2000). Innføring i sannsynlighetsregning og statistikk. Cappelen akademisk
    • Birkeland, P.A., Breiteig, B., Venheim, R. (2012). Matematikk for lærere 2. Universitetsforlaget

Ordnede og uordnede utvalg

I artikkelen om permutasjoner studerer vi hvilke kombinasjonsmuligheter vi har når vi setter elementer sammen i en bestemt rekkefølge. For eksempel kan vi, når vi velger to av tallene 1, 2 og 3, danne kombinasjonene 1-2, 1-3, 2-1, 2-3, 3-1 og 3-2. Disse kombinasjonene kalles ordnede utvalg fordi rekkefølgen elementene står i, er viktig. Men ser vi bort fra rekkefølgen, vil henholdsvis 1-2 og 2-1, 1-3 og 3-1, og 2-3 og 3-2 representere samme utvalg. Disse kalles uordnede utvalg fordi rekkefølgen elementene står er uten betydning. De mulige uordnede utvalgene består av kombinasjonene {1, 2}, {1, 3}, og {2, 3}.

Vi har tidligere introdusert en formel for å beregne antall k-permutasjoner av totalt n elementer. Dette er egentlig det samme som antall ordnede utvalg:

$\fbox{Antall ordnede utvalg med $k$ elementer av totalt $n$: $\frac{\displaystyle n!}{\displaystyle (n − k)!}$}$

Siden k elementer kan organiseres på k! måter, betyr det at vi finner antall uordnede utvalg ved å dividere dette antallet på k!:

$\fbox{Antall uordnede utvalg med $k$ elementer av totalt $n$: $\frac{\displaystyle n!}{\displaystyle k!(n − k)!}$}$

Eksempel 1:

I pengespillet Lotto dannes en vinnerrekke ved at det trekkes 7 av totalt 34 tall.

Antall måter en sekvens på 7 tall av totalt 34 kan trekkes på, er det samme som antall ordnede utvalg med 7 av 34 elementer:

${\large \frac{34!}{(34 − 7)!}} = 27 \, 113 \, 264 \, 460$.

Men når trekningen er foretatt, ordnes tallene i stigende rekkefølge, så rekkefølgen tallene trekkes i, har ingen betydning. For eksempel gir både 12-28-17-7-6-2-31 og 7-17-2-6-12-31-28 vinnerrekka 2-6-7-12-17-28-31.

For å finne antall mulige vinnerrekker, må vi altså dividere med antall måter 7 tall kan organiseres på, nemlig 7!, og beregne antall mulige uordnede utvalg:

${\large \frac{34!}{7!(34 − 7)!}} = 5 \, 379 \, 616$.

Det finnes altså ca. 5,38 millioner mulige vinnerrekker.

Det finnes en egen skrivemåte for å uttrykke «antall uordnede utvalg med k av totalt n elementer», ${\large \binom{n}{k}}$, som leses «n over k». Altså

$\fbox{${\large \binom{n}{k}} = \frac{\displaystyle n!}{\displaystyle k!(n − k)!}$}$

Vi kaller også gjerne dette «antall kombinasjoner med k av n elementer».

Excel har en egen funksjon, kombinasjon, til å beregne antall kombinasjoner, der kombinasjon(n, k) gir antall kombinasjoner med k av n elementer. Vi skriver for eksempel =kombinasjon(34; 7) for å gjøre beregningen i eksempel 1. Tilsvarende funksjon I GeoGebra heter ncr(n, k) Vi skriver for eksempel ncr(34, 7) i inntastingsfeltet eller CAS for å gjøre beregningen i eksempel 1.

Eksempel 2:

Vi skal regne ut hvor mange forskjellige pokerhender det finnes. En pokerhånd består av 5 av totalt 52 kort, så det vi må beregne er hvor mange kombinasjoner, altså antall uordnede utvalg, det finnes med 5 av 52 elementer. Vi får

${\large \binom{52}{5}} = {\large \frac{52!}{5!(52 − 5)!}} = 2 \, 598\, 960$, som er det samme tallet vi brukte da vi i introduksjonen regnet på sannsynlighet for å få tress utdelt i poker.

Vi kan kontrollere svaret i Excel ved å skrive =kombinasjon(52; 5) og i GeoGebra ved å skrive ncr(52, 5).

Oppgave 1:

I en bedrift med 25 ansatte skal det velges 3 representanter til en delegasjon. Beregn hvor mange forskjellige delegasjoner som kan velges. Bruk formel, og kontroller svaret i Excel eller GeoGebra.

Se løsningsforslag

Kilder

    • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
    • Hagen, Per C. (2000). Innføring i sannsynlighetsregning og statistikk. Cappelen akademisk
    • Birkeland, P.A., Breiteig, B., Venheim, R. (2012). Matematikk for lærere 2. Universitetsforlaget

Permutasjoner

Spør vi oss hvor mange måter vi kan organisere tallene 1 og 2 på, er det lett å innse at svaret er to. Vi kan ha sekvensene 1-2 og 2-1. Men tar vi med tallet 3 også, blir det mer komplisert. Vi kan ha 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2 og 3-2-1. Totalt seks sekvenser. Tar vi også med tallet 4, kan vi ha 24 sekvenser. Slike sekvenser kalles permutasjoner.

Fakultet

Antallet forskjellige permutasjoner er lett å beregne. La oss si at vi har tre elementer. Da kan tre elementer velges til å stå først, blant de gjenstående kan to velges til å stå som nummer to, og så er det bare ett element igjen som kan stå sist. Totalt 3 · 2 · 1 = 6 sekvenser. Med fire elementer får vi 4 · 3 · 2 · 1 = 24 sekvenser. Generelt, med n elementer, får vi n · (n−1) · (n−2) · … · 1 sekvenser.

Produktet n · (n−1) · (n−2) · … · 1 har et eget navn, fakultet, og betegnes med et utropstegn:

$\fbox{Fakultet: $n! = n \cdot (n−1) \cdot (n−2) \cdot \; \dots \; \cdot 1$}$

Her er n et positivt heltall. Det er også definert at

$\fbox{$0! = 1$}$

Vi skal senere se hvorfor dette er nyttig.

Eksempel 1:

Vi skal beregne 5! og får 5 · 4 · 3 · 2 · 1 = 120.

Eksempel 2:

Vi har en klasse med 20 elever, og skal beregne hvor mange forskjellige måter de kan sette seg ved pultene på. Første elev kan velge blant 20 pulter, andre blant 19, og så videre, så totalt blir det 20! ≈ 2,4 · 1018 muligheter. Et enormt tall. Hvis elevene byttet plass hvert 5. sekund døgnet rundt, ville det ta nesten 400 milliarder år å komme gjennom alle variantene.

Vi skjønner at n! blir et stort tall, selv for lave n. 59! ≈ 1,4 · 1080 er for eksempel et tall større enn antall atomer i det observerbare universet.

Det er sjelden vi beregner fakultetet for hånd. Litt avanserte kalkulatorer og dataprogrammer har egne funksjoner for dette. I Excel bruker vi funksjonen fakultet, for eksempel skriver vi =fakultet(10) for å beregne 10!. I GeoGebra skriver vi bare et tall med et utropstegn etter i inntastingsfeltet eller CAS. For eksempel 10!.

På grunn av de store tallene er det begrenset hvor høye fakulteter dataprogrammer kan beregne. Excel og GeoGebra stopper på 170!. En del kalkulatorer stopper på 69!, fordi høyere fakulteter er større enn 10100, og kalkulatorene bare kan vise eksponenter med maksimalt to sifre.

Oppgave 1:

En skoleklasse på 30 elever stiller opp på rekke. Hvor mange måter kan rekka organiseres på? Bruk kalkulator eller dataprogram til beregningen.

Se løsningsforslag

k-permutasjoner av n

Det finnes altså n! mulige sekvenser med n elementer, for eksempel 5! = 120. Men hva om vi ikke vil ha med alle elementene, og spør om hvor mange sekvenser vi kan lage av k av totalt n elementer? Det er ikke så vanskelig å resonnere seg fram til. Første element kan velges på n måter, andre element på n−1 måter, tredje element på n−2 måter, og så videre til vi har tatt med k elementer, altså n · (n−1) · (n−2) · … · (nk+1).

Slike sekvenser kaller vi k-permutasjoner av n.

Eksempel 3:

Vi vil lage sekvenser med 4 elementer fra en mengde på 10. Her er n = 10 og k = 4. Så antall sekvenser blir
n · (n−1) · (n−2) · … · (nk+1) = 10 · (10−1) · (10−2) · (10−3) = 10 · 9 · 8 · 7 = 5040.

Det finnes 5040 mulige sekvenser med 4 av 10 elementer på. Antall 4-permutasjoner av 10 er altså 5040.

Excel har en egen funksjon, permuter, til å beregne antall k-permutasjoner, der permuter(n; k) gir antall k-permutasjoner av n. Vi skriver for eksempel =permuter(10; 4) for å gjøre beregningen i eksempel 3. I GeoGebra skriver vi npr(n, k) i inntastingsfeltet eller CAS. Vi skriver for eksempel npr(10, 4) for å gjøre beregningen i eksempel 3.

Men har vi ikke Excel eller GeoGebra tilgjengelig, vil det være arbeidskrevende å utføre multiplikasjonene én for én. Vi skal derfor regne om uttrykket n · (n−1) · (n−2) · … · (nk+1) ved hjelp av et lite regnetriks, og multipliserer med en brøk med (nk)!, det vil si (nk) · (nk−1) · (nk−2) · … · 1 i teller og nevner:

$n \cdot (n − 1) \cdot (n − 2) \cdot \; \dots \; \cdot (n − k + 1) =$

$n \cdot (n − 1) \cdot (n − 2) \cdot \; \dots \; \cdot (n − k + 1) \cdot \frac{\displaystyle (n − k) \cdot (n − k − 1) \cdot (n − k − 2) \cdot \; \dots \; \cdot 1}{\displaystyle (n − k) \cdot (n − k − 1) \cdot (n − k − 2) \cdot \; \dots \; \cdot 1} =$

$\frac{\displaystyle n \cdot (n − 1) \cdot (n − 2) \cdot \; \dots \; \cdot 1}{\displaystyle (n − k) \cdot (n − k − 1) \cdot (n − k − 2) \cdot \; \dots \; \cdot 1} =$

$\frac{\displaystyle n!}{\displaystyle (n − k)!}$

Her har vi kommet fram til en form som bare involverer fakulteter, og derfor enkelt kan beregnes på en kalkulator med fakultetsfunksjon.

Vi har altså:

$\fbox{Antall $k$-permutasjoner av $n$: $\frac{\displaystyle n!}{\displaystyle (n − k)!}$}$

Eksempel 4:

Vi skal finne antall 2-permutasjoner av 3, det vil si hvor mange sekvenser av to elementer vi kan lage av totalt tre. Vi bruker formelen over, og får ${\large \frac{3!}{(3 − 2)!}} = {\large \frac{6}{1}} = 6$.
Med så få elementer kan vi kontrollere dette ved å telle permutasjonene. La oss si at de 3 elementene heter a, b og c. Da kan vi lage sekvensene a-b, a-c, b-a, b-c, c-a og c-b. Totalt 6 stykker, slik vi kom fram til ved hjelp av formelen.

Oppgave 2:

Beregn antall 4-permutasjoner av 10 ved å bruke formelen for antall k-permutasjoner av n. Gjør også utregningen i Excel og GeoGebra.

​Se løsningsforslag

​Eksempel 5:

Vi skal finne antall 5-permutasjoner av 5. Vi bruker formelen for antall k-permutasjoner av n, og får ${\large \frac{5!}{(5 − 5)!}} = {\large \frac{5!}{0!}} = {\large \frac{120}{1}} = 120$.

Her fikk vi 0! = 1 i nevneren. Hadde vi ikke hatt spesialdefinisjonen av 0!, ville vi ikke kunnet bruke formelen i dette tilfellet.

Men utregningen er tungvint, for en n-permutasjon av n betyr bare n!, så vi kunne nøyd oss med å regne ut 5! = 120.

​​Eksempel 6:

Vi skal finne antall 0-permutasjoner av n. Vi bruker formelen for antall k-permutasjoner av n, og får ${\large \frac{n!}{(n − 0)!}} = {\large \frac{n!}{n!}} = 1$.

Vi kan altså lage én sekvens med 0 elementer uavhengig av hvor mange elementer vi har til rådighet totalt.

SkjermfilmSe filmen «Permutasjoner»
 

Kilder

    • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
    • Hagen, Per C. (2000). Innføring i sannsynlighetsregning og statistikk. Cappelen akademisk
    • Birkeland, P.A., Breiteig, B., Venheim, R. (2012). Matematikk for lærere 2. Universitetsforlaget

Introduksjon til kombinatorikk

Som navnet antyder, går kombinatorikk ut på å studere muligheter for å kombinere ting.

I artikkelen om begreper i sannsynlighet introduserer vi begrepet «gunstige på mulige», som går ut på at vi finner sannsynligheten for en hendelse i et stokastisk forsøk ved å telle opp antall enkeltutfall som fører til hendelsen, og dividere med det totale antall utfall i forsøket. Vi forutsetter da at vi har en uniform sannsynlighetsmodell, det vil si at alle utfallene er like sannsynlige.

Eksempel 1:

Når vi trekker et kort tilfeldig fra en komplett kortstokk, er sannsynligheten for å få en spar en fjerdedel, fordi det blant 52 like sannsynlige enkeltutfall er 13 kort som er spar, og «gunstige på mulige» gir ${\large \frac{13}{52}} = {\large \frac{1}{4}}$.

I mange tilfeller lar det seg imidlertid i praksis ikke gjøre å telle opp antall enkeltutfall fordi de er så mange. Hvis vi for eksempel skal beregne sannsynligheten for å få utdelt tress i poker ved å inspisere alle mulige pokerhender, finnes det totalt 2 598 960 kombinasjoner å gå gjennom. Sjekket vi 1 kombinasjon i sekundet dag og natt, ville det ta om lag en måned å komme gjennom alle.

I stedet skal vi i artiklene om kombinatorikk lære å bruke systematiske metoder som lar oss regne på kombinasjoner. For eksempel finne ut at det blant 2 598 960 mulige pokerhender finnes 54 912 med tress, så sannsynligheten for å få dette utdelt er

${\large \frac{54 \, 912}{2 \, 598 \, 960}}$, ca. 2 %.

SkjermfilmSe filmen «Introduksjon til kombinatorikk»
 

I artiklene om kombinatorikk refereres det til hvordan forskjellige beregninger kan utføres ved hjelp av funksjoner i GeoGebra og Excel. Eksempler i Excel finnes regnearket under, som har én fane for hver funksjon:

RegnearkLast ned regneark med eksempler på kombinatorikk-funksjoner
 

Kilder

    • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
    • Hagen, Per C. (2000). Innføring i sannsynlighetsregning og statistikk. Cappelen akademisk
    • Birkeland, P.A., Breiteig, B., Venheim, R. (2012). Matematikk for lærere 2. Universitetsforlaget