Hvis vi trekker k elementer fra en mengde på n elementer, angir vi antall kombinasjonsmuligheter som ${\large \binom{n}{k}}$, noe vi kan beregne som ${\large \frac{n!}{k!(n-k)!} }$. I Lotto er det for eksempel ${\large \binom{34}{7}} = {\large \frac{34!}{7!(34-7)!} } = {\small 5 \, 379 \, 616}$ kombinasjonsmuligheter for 7 kuler som trekkes blant 34.
Vi ser at vi i denne formelen må beregne tre fakulteter, n!, k! og (n − k)!
En funksjon for å beregne fakulteter står i artikkelen om å lagre funksjoner i moduler:
def fakultet(n):
"""Beregner n!"""
fakt = 1
for m in range(2, n + 1):
fakt *= m
return fakt
Vi har altså mekanismen vi trenger for å skrive en funksjon som beregner ${\large \binom{n}{k}}$. Vi skal først gjøre det på gal måte. Vi bruker tre kopier av koden, tilpasset til n, k og n−k. Resultatene av beregningene lagrer vi underveis i tre variabler vi kaller k_fakt, n_fakt og n_minus_k_fakt, som vi så til slutt bruker til å beregne n_fakt / (k_fakt * n_minus_k_fakt):
def kombinasjon(n, k):
"""Beregner antall kombinasjoner av k blant n på en dum måte"""
# Beregn k!
k_fakt = 1
for m in range(2, k + 1):
k_fakt *= m
# Beregn n!
n_fakt = 1
for m in range(2, n + 1):
n_fakt *= m
# Beregn (n - k)!
n_minus_k_fakt = 1
for m in range(2, n - k + 1):
n_minus_k_fakt *= m
# Returner antall kombinasjonsmuligheter
# Divisjonen gir et flyttall, så vi konverterer til heltall
return int(n_fakt / (k_fakt * n_minus_k_fakt))
Men dette er svært dårlig design. Samme kode bør bare ligge én plass, og her gjentar vi koden fra fakultet() tre ganger. Det vi i stedet bør gjøre, er å importere funksjonen fakultet() og kalle den opp fra kombinasjon():
from kombinatorikk import fakultet
def kombinasjon(n, k):
"""Beregner antall kombinasjoner av k blant n"""
return int(fakultet(n) / (fakultet(k) * fakultet(n - k)))
Vi kan altså kalle opp en funksjon fra en annen. Vi bruker her funksjonen fakultet() uten å bry oss med hvordan den virker. Vi ber bare fakultet() beregne henholdsvis n!, k! og (n − k)!, og bruker resultatene til å beregne ${\large \binom{n}{k}}$.
Vi kan ha hele kjeder med funksjoner som kaller hverandre. Hvis vi i hovedprogrammet skriver
print(kombinasjon(34, 7))
kaller print() opp kombinasjon(), og kombinasjon() kaller opp fakultet() tre ganger. Det er teoretisk ingen grense for hvor lange kjeder av funksjonskall vi kan ha.
Hvis du ikke har gjort det, gjør oppgave 1 i artikkelen om å lagre funksjoner i moduler, slik at du har ei fil som heter kombinatorikk som inneholder funksjonen fakultet().
Åpne så fila kombinatorikk.
Legg inn koden til funksjonen kombinasjon() under fakultet(). Du kan kopiere koden som er vist over, men det er ikke nødvendig å importere fakultet(), siden den ligger i samme fil.
Lagre fila.
Åpne deretter ei ny fil, importer kombinasjon() fra kombinatorikk, og bruk kombinasjon() til å beregne antall kombinasjonsmuligheter når 7 elementer velges fra en mengde på 34.
Skriv ut resultatet. Riktig svar er 5 379 616.
Obs: Den nye fila skal ikke inneholde koden til kombinasjon(), bare hente den gjennom import.
Hvis vi flipper en mynt, kan den lande med «kron»-siden opp eller «mynt»-siden opp. Sannsynligheten for hvert av de to tilfellene er 0,5. Sannsynligheten for å få k «kron» når vi flipper n ganger er da gitt ved $P(k) = {\large \binom{n}{k}} \cdot (0{,}5)^n$.
Skriv en funksjon som beregner sannsynligheten for få k «kron» i n flipp. Verdier til k og n skal kunne gis inn som argumenter til funksjonen.
Riktig svar for 5 «kron» i 7 flipp er 0,1640625.
Hint: Du vil måtte bruke funksjonen kombinasjon() som du laget i oppgave 1.
I en binomisk fordeling har vi to mulige utfall i et forsøk. Enten inntreffer en hendelse, eller så inntreffer den ikke. I oppgave 2 var denne hendelsen «kron» på en mynt, med sannsynlighet lik 0,5. Men vi kan også ha hendelser der sannsynligheten ikke er 0,5. Flipper vi for eksempel en tegnestift, kan det være at sannsynligheten for at den havner med spissen opp er 0,7.
I en binomisk fordeling er sannsynligheten for at en hendelse med sannsynlighet p skal inntreffe k ganger i n forsøk gitt ved
$P(k) = {\large \binom{n}{k}} \cdot p^k \cdot {(1-p)}^{(n-k)}$
Utvid funksjonen fra oppgave 2 slik at den ikke er låst til sannsynlighet 0,5, men bruker formelen over. Verdien til p skal kunne gis inn som argument til funksjonen sammen med k og n.
Kall funksjonen binomisk(). Lagre den i fila kombinatorikk, under fakultet() og kombinasjon(), som ligger der fra før.
Åpne deretter ei ny fil, importer binomisk() fra kombinatorikk, og bruk binomisk() til å beregne sannsynligheten for at en hendelse med sannsynlighet 0,2 skal inntreffe 4 ganger i 8 forsøk.
Skriv ut resultatet. Riktig svar avrundet til 5 desimaler er 0,04588.
Obs: Den nye fila skal ikke inneholde koden til binomisk(), bare hente den gjennom import.
Kilder
-
- Matthes A. (2019). Python Crash Course. no starch press