Kombinatorikk

I artikkelen om begreper i sannsynlighet introduserte 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 sjansen 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 omlag en måned å komme gjennom alle.

I stedet skal vi i denne artikkelen lære å bruke systematiske metoder som lar oss regne på kombinasjoner. For eksempel finne ut at det finnes 54 912 pokerhender med tress, så sannsynligheten for å få dette utdelt er ${\large \frac{54 \, 912}{2 \, 598 \, 960}}$, ca. 2 %.

Gjennom artikkelen 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:

RegnearkÅpne et regneark med eksempler på kombinatorikk-funksjoner
 

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. 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 \cdot 2 \cdot 1 = 6$ sekvenser. Med fire elementer får vi $4 \cdot 3 \cdot 2 \cdot 1 = 24$ sekvenser. Generelt, med $n$ elementer, får vi $n \cdot (n – 1) \cdot (n – 2) \cdot \; \dots \; \cdot 1$ sekvenser.

Produktet $n \cdot (n – 1) \cdot (n – 2) \cdot \; \dots \; \cdot 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 2:

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

Eksempel 3:

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! \approx 2,4 \cdot 10^{18}$ muligheter. Et enormt tall. Hvis elevene byttet plass hvert 5. sekund, 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! \approx 1{,}4 \cdot 10^{80}$ 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

Det finnes altså altså n! måter å organisere n elementer på, for eksempel 5! = 120. Men hva om vi ikke vil ha med alle elementene, og spør om hvor mange måter vi kan organisere k av totalt n elementer på? 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, og kommet til element n – k + 1.

Slike sammensetninger kaller vi k-permutasjoner av n.

Eksempel 4:

Fra en mengde på 10 elementer kan vi kombinere 4 elementer på $10 \cdot 9 \cdot 8 \cdot 7 = 5040$ måter.

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 4. I GeoGebra skriver vi nPr(n, k) i inntastingsfeltet eller CAS. Vi skriver for eksempel nPr(10, 4) for å gjøre beregningen i eksempel 4.

Har vi ikke en slik funksjon tilgjengelig, vil det være arbeidskrevende å utføre multiplikasjonene én for én. Vi skal derfor regne om uttrykket ved hjelp av et lite regnetriks og multipliserer med en brøk med $(n – k)!$, det vil si $(n – k) \cdot (n – k – 1) \cdot (n – k – 2) \cdot \; \dots \; \cdot 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)!}$

Nå har vi kommet fram til en formel for antall k-permutasjoner av n, som bare involverer fakulteter,

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

Har vi en kalkulator med fakultet-funksjon, kan vi derved lett utføre beregningen.

Eksempel 5:

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. Kontroller svaret med Excel eller GeoGebra.

​Se løsningsforslag

​Eksempel 6:

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 7:

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.

Ordnede og uordnede utvalg

Så langt har vi studert kombinasjonsmuligheter 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 vesentlig. 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 8:

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-1-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 8. 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 8.

Eksempel 9:

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 som vi refererte til innledningsvis.

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

Oppgave 3:

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

Delmengder

I artikkelen om begreper i sannsynlighet ble vi kjent med begrepet mengder, og hvordan vi kunne illustrere mengder ved hjelp av Venn-diagrammer. Vi lærte også om delmengder, der en mengde er en del av en annen, noe vi i Venn-diagrammer illustrerer med en sirkel inni en annen sirkel.

Slike delmengder er egentlig kombinasjoner av elementer i mengden, slik vi nettopp har sett på. For eksempel er hver mulig vinnerrekke i Lotto en delmengde med 7 tall i en hovedmengde på totalt 34.

Nå skal vi finne ut hvor mange delmengder det går an å lage i en mengde. 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, 3 med to tall i hver, og 1 med alle tallene. Totalt blir dette 3 + 3 + 1 = 7 delmengder. Tenker vi oss at mengden med 0 elementer, $\emptyset$, også er en delmengde, blir det totalt 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, 1 med to elementer og 1 med 0 elementer. En mengde med ett element vil kunne inneholde 2 delmengder, nemlig 1 med ett element og 1 med ingen elementer. En mengde med 0 elementer vil bare kunne inneholde 1 delmengde, nemlig mengden med 0 elementer.

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 delmengde med $n$ elementer kan inneholde $2^n$ delmengder}$

Oppgave 4:

En mengde, $A$, inneholder elementene $a$, $b$ og $c$: $A = \{a, b, c \}$. List opp de mulige delmengdene som kan lages. Stemmer dette antallet med det som er angitt i boksen over?

Se løsningsforslag

At en mengde, $B$, er en delmengde av $A$, skriver vi slik: $B \subseteq A$.

At en mengde, $B$, ikke er en delmengde av $A$, skriver vi slik: $B \nsubseteq A$.

Vi har sett at en delmengde kan bestå av alle elementene i en mengde, en mengde er altså en delmengde av seg selv. Men bare delmengder som ikke er lik mengden selv kalles ekte delmengder.

At en mengde, $B$, er en ekte delmengde av $A$, skriver vi slik: $B \subset A$.

At en mengde, $B$, ikke er en ekte delmengde av $A$, skriver vi slik: $B \not \subset A$.

Eksempel 10:

$\{2, 3 \} \subseteq \{2, 3, 4 \}$

$\{2, 3 \} \subset \{2, 3, 4 \}$

$\{2, 3, 4 \} \subseteq \{2, 3, 4 \}$

$\{2, 3, 4 \} \not\subset \{2, 3, 4 \}$

$\emptyset \subseteq \{2, 3, 4 \}$

$\emptyset \subset \{2, 3, 4 \}$

$\{1 \} \nsubseteq \{2, 3, 4 \}$

$\{2, 3, 4, 5 \} \nsubseteq \{2, 3, 4 \}$

Eksempel 11:

Vi skal sjekke hvor mange delmengder med henholdsvis 1, 2 og 3 elementer som kan lages i en mengde med totalt 3 elementer. Som nevnt er en delmengde det samme som et uordnet utvalg, så vi bruker formelen for antall uordnede utvalg:

0 elementer: ${\large \binom{3}{0}} = {\large \frac{3!}{0!(3 – 0)!}} = 1$.

1 element: ${\large \binom{3}{1}} = {\large \frac{3!}{1!(3 – 1)!}} = 3$.

2 elementer: ${\large \binom{3}{2}} = {\large \frac{3!}{2!(3 – 2)!}} = 3$.

3 elementer: ${\large \binom{3}{3}} = {\large \frac{3!}{3!(3 – 3)!}} = 1$.

Dette stemmer med det vi har funnet tidligere. Og totalt blir det 1 + 3 + 3 + 1 = 8, som er 23, som det skal være.

Utvalg fra blandede mengder

Så langt har vi sett 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, blir det mer komplisert. Vi illustrerer med et noen eksempler:

Eksempel 12:

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 \cdot 28 = 1540$ måter.

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

Oppgave 5:

Ta utgangspunkt i gruppa i eksempel 12, 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

RegnearkÅpne et regneark der du kan regne ut antall mulige elevutvalg

 

Eksempel 13:

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 12, 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 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 6:

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

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 elementer i kombinasjonen, og mulige er antall kombinasjoner totalt.

Eksempel 14:

Vi skal beregne sannsynligheten for å vinne hovedgevinsten i Lotto en gitt uke.

I eksempel 8 regnet vi ut at det finnes ${\large \frac{34!}{7!(34 – 7)!}} = 5 \, 379 \, 616$ mulige vinnerrekker i Lotto. En gitt uke trekkes 1 av disse ut, så gunstige på mulige gir at sannsynligheten blir

 ${\large \frac{1}{5 \, 379 \, 616}} \approx 1{,}86 \cdot 10^{-7}$.

Sannsynligheten for å vinne er litt mindre enn 0,00002 %.

Eksempel 15:

Vi skal beregne sannsynligheten for å få en bridgehånd med nøyaktig åtte ruter som i eksempel 13.

Vi beregnet i eksempel 13 at det finnes totalt 740 999 259 slike hender. 

Totalt finnes det ${\large \binom{52}{13}} = 635 \, 013 \, 559 \, 600$ mulige bridgehender. Så sannsynligheten blir

${\large\frac{740 \, 999 \, 259}{ 635 \, 013 \, 559 \, 600}} \approx 0,0012$.

Sannsynligheten for å få en hånd med nøyaktig 8 ruter er omlag 0,12 %.

Oppgave 7:

Beregn sannsynlighetene for å få de korthendene nevnt i oppgave 6.

Se løsningsforslag

Trekning med og uten tilbakelegg

Når vi så langt har valgt elementer fra en mengde, har vi gjort det "uten tilbakelegg", det vil si at når ett element først er trukket ut, kan vi ikke trekke det på nytt. Men vi kan også trekke "med tilbakelegg", det vil si at vi tenker oss at vi legger det uttrukne elementet tilbake i den opprinnelige mengden, slik at vi kan trekke det en gang til.

Som vi så i avsnittet om permutasjoner, hadde vi, når vi trakk fra en mengde med n elementer, n valgmuligheter i første trekning, n – 1 i neste, deretter n – 2 og så videre. Vi hadde ikke tilbakelegg, så for hver trekning ble det ett element mindre å velge blant.

Trekker vi derimot flere ganger med tilbakelegg fra en mengde på n elementer, har vi jo hver gang n elementer å velge blant. Trekker vi 2 ganger, får vi derfor n2 mulige ordnede utvalg, trekker vi 3 ganger, får vi n3 mulige ordnede utvalg, og så videre.

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

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

Eksempel 16:

En tippekupong består 12 kamper, der vi for hver kamp har mulighetene 'H', 'U' og 'B', og vi skal finne ut hvor mange kombinasjonsmuligheter det finnes på en slik kupong. Det vi spør etter da, er egentlig antall ordnede utvalg når vi trekker 12 ganger fra en mengde på 3 med tilbakelegg. Utvalget er ordnet fordi rekkefølgen på kampene er vesentlig, at kamp 1 er 'H' og kamp 2 er 'B' er for eksempel ikke det samme som at kamp 1 er 'B' og kamp 2 er 'H'. Utvalget er med tilbakelegg fordi 'H', 'U' og 'B' er like tilgjengelige i hver kamp.

Antall mulige kuponger blir derfor

312 = 531 441.

Sannsynligheten for å få 12 rette hvis vi setter opp en kupong tilfeldig, er

${\large \frac{1}{531 \, 441}} \approx 1{,88}\cdot 10^{-6}$, omlag 0,0002 %.

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

I motsetning til i Lotto kan vi imidlertid i tipping forbedre sjansene ved å ikke velge tilfeldig. Statistikken viser at det i gjennomsnitt er flere hjemmeseiere, 'H' enn borteseiere, 'B', og flere borteseiere enn uavgjort, 'U'. Den mest sannsynlige kupongen, hvis vi ikke tar hensyn til hvilke lag som spiller, har derfor 12 hjemmeseiere. Så vil vi også kunne forbedre sjansene ved å ta hensyn til hvilke lag som spiller og satse på at de beste lagene vinner.

Dette er forskjellen 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, sannsynlighetene varierer med hvilke kamper som spilles. Å velge tilfeldig er derfor en fin strategi i Lotto, men ikke i tipping.

Oppgave 8:

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

Se løsningsforslag

Uordnede utvalg med tilbakelegg

Vi har nå sett på kombinasjonsmuligheter i ordnede utvalg med og uten tilbakelegg, og i uordnede utvalg uten tilbakelegg. I den varianten vi ikke har sett på, uordnede utvalg med tilbakelegg er det imidlertid komplisert å beregne kombinasjonsmuligheter. Når det gjelder utvalg uten tilbakelegg, har vi sett at vi finner antall mulige uordnede utvalg ved å dividere antall ordnede utvalg på antall måter elementene i utvalget kan organiseres på. Velger vi for eksempel to av tallene 1, 2 og 3, kan vi danne 6 mulige ordnede utvalg. Siden to tall kan organiseres på to måter, blir det 6 : 2 = 3 mulige uordnede utvalg. Trekker vi med tilbakelegg, får vi imidlertid 32 = 9 mulige ordnede utvalg: 1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 3-2, 3-3. Og hvor mange måter elementene kan organiseres på, varierer med hva vi har trukket. To like elementer, som 1 og 1 kan bare organiseres på én måte, mens to ulike elementer, som 1 og 2 kan organiseres på to måter. Ved å telle, ser vi at det i dette eksempelet finnes 6 mulige uordnede utvalg, nemlig {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, og {3, 3}. De forskjellige utvalgene er heller ikke like sannsynlige, det er dobbelt så sannsynlig å få to ulike tall som å få to like.

Med økende antall valgmuligheter øker kompleksiteten.

Vekst av antall kombinasjoner

Lysets hastighet er enorm. En lysstråle som forlater Jorda i dag, vil om ett år ha nådd omlag 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 på en tippekupong 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 17:

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 18:

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 internasjonale bokstavene 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 tar 6 sekunder å skrive. For en tekst med to tegn vil det finnes 900 muligheter, som hver tar 0,4 sekunder å skrive, totalt 6 minutter. For en tekst med seks tegn vil det finnes 729 millioner muligheter, som hver tar 1,2 sekunder å skrive, totalt omlag 27,7 år. For en tekst med tolv tegn vil det finnes omlag $5{,}3\cdot10^{17}$ muligheter, som hver tar 2,4 sekunder å skrive, totalt over 40 milliarder år. Altså omlag 8 ganger lenger enn det som regnes som den gjenstående levetiden til Sola.

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

Pokersannsynligheter

Å regne på sannsynligheter i poker består i å finne antall mulige kombinasjoner som gir en bestemt hånd, for eksempel tress, og så dividere på antall mulige kombinasjoner i en pokerhånd totalt. Dette dreier seg om uordnede utvalg uten tilbakelegg. Uordnede fordi det ikke spiller noen rolle hvilken rekkefølge kortene blir delt ut i, vi sorterer dem etterpå. Uten tilbakelegg fordi samme kort ikke kan deles ut mer enn én gang.

Det finnes 2 598 960 pokerhender totalt, slik vi regnet ut i eksempel 9.

Kombinasjonene som gir en bestemt pokerhånd er i noen tilfeller relativt enkle å finne, slik som for 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. Sannsynligheten for å få royal straight flush utdelt er derfor

$\frac{\displaystyle 4}{\displaystyle 2 \, 598 \, 960} \approx 1{,}53 \cdot 10^{-6}$, litt mer enn 0,00015 %.

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

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. Eksempel 19 forklarer utregningen for tress.

Eksempel 19:

Vi skal finne sannsynligheten for å få tress utdelt i poker.

En kortstokk har fire farger og tretten valører. Skal vi få tress, må vi ha tre kort med samme valør, og det finnes altså 13 muligheter for dette. Vi kan få tre toere, tre treere, tre firere og så videre. For å bruke den etablerte terminologien med kombinasjoner, har vi 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 tre kort med samme valør.

En pokerhånd består av fem kort, så den inneholder altså to kort i tillegg til de tre med samme valør. Disse to kan trekkes blant 49 gjenværende kort, noe som gir ${\large \binom{49}{2}} = 1176$ kombinasjonsmuligheter.

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 ett 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 to kortene.

Heller ikke kan vi tillate at de to 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 tre like. 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 \cdot 6 = 72$ kombinasjoner som gir par. Vi sitter altså igjen med $1128 – 72 = 1056$ lovlige kombinasjonsmuligheter for de siste to kortene.

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

Sannsynligheten for å få utdelt tress er da

$\frac{\displaystyle 54 \, 912}{\displaystyle 2 \, 598 \, 960} \approx 2{,}1 \cdot 10^{-2}$, litt mer enn 2 %.

Når det gjelder kombinasjonsmuligheter for de siste to 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 ett er "ulovlig", med samme valør som de tre like. For B er det så 48 kort å velge blant, hvorav ett er "ulovlig", med samme valør som de tre like, og tre er "ulovlige" med samme valør som A. Altså 49 – 1 = 48 lovlige valg for A og 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 $\frac{\displaystyle 48 \cdot 44}{\displaystyle 2!} = 1056$, som er det samme som vi fant tidligere.

Som et tredje alternativ for de to siste kortene kan vi tenke oss at vi for disse velger to 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 tre 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$.

Kilder:

  • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
  • Ubøe, J. (2011). Statistikk for økonomifag. Gyldendal akademisk
  • 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
  • Wikipedia