Kombinatorikk i spill

I artikkelen om kombinatorikk lærte 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

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.

Som vi så i eksempel 9 i artikkelen om kombinatorikk, finner 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}$, litt mer enn 0,00015 %

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

En utregning for tress er vist i eksempel 1:

Eksempel 1:

Pokerhånd med tress i damer

Vi skal finne antall kortkombinasjoner i tress, samt sannsynligheten for å få utdelt 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.

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.

Men 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 \cdot 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 3 like kort med kombinasjonsmulighetene for de 2 siste kortene: $52 \cdot 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}$, litt mer enn 2,1 %.

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 beregnet i eksempel 14 i artikkelen om kombinatorikk, 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{,}859 \cdot 10^{-7}$.

Det er om lag 0,0000186 % 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{,}301 \cdot 10^{-6}$.

Det er om lag 0,0001301 % 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{,}383 \cdot 10^{-5}$.

Det er om lag 0,003383 % 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{,}370 \cdot 10^{-3}$.

Det er  om lag 0,1370 % 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{,}903 \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,51 % sannsynlig å få 0 rette på ei Lotto-rekke.

Sannsynligheten i lottorekker diskuteres også i lys av hypergeometriske fordelinger i eksempel 7 i 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 offiserer 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.

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