Kombinatorikk

Kombinatorikk handlar om å finna antall kombinasjonar. I dette kapittelet ser me litt på korleis me kan gjera det gjennom programmering - både heilt grunnleggande med løkker og med funksjonar andre har laga.

Ordna utval med tilbakelegging.

Me trekk eit utval på \(r\) element frå ein populasjon med \(n\) element.

Moglege kombinasjonar er då $\( n\cdot n \cdot n \cdot \ldots \cdot n = n^r \)$

Ordna utval: rekkefølgen er viktig
Med tilbakelegging: kvart element i populasjonen kan trekkast fleire gongar.

n = 5         # populasjon
r = 3         # utval

komb = n**r   # kombinasjonar

print(f"Kombinasjonar: {komb}")

Kombinasjonar: 125

Ordna utval utan tilbakelegging.

Trekk eit utval på \(r\) element på ein populasjon på \(n\).

Moglege kombinasjonar er då $\( _n P _r = n\cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-r+1)\)$

Ordna utval: rekkefølgen er viktig
Utan tilbakelegging: når eit element er trekt kan det ikkje trekkast igjen

n = 5         # populasjon
r = 3         # utval

komb = 1      # startverdi (1 pga multiplikasjon)

for i in range(r):
    komb *= (n-i)
    
print(f"Kombinasjonar: {komb}")

Kombinasjonar: 60

Fakultet

Når \(n = r\) når me ser på ordna utval utan tilbakelegging gjer me eit utval som er like stort som populasjonen. I praksis vil det då bli kor mange forskjellige måtar me kan ordna populasjonen.

Trekk eit utval på \(n\) element på ein populasjon på \(n\).

Moglege kombinasjonar er då $\( _n P _n = n\cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2\cdot 1\)$

Dermed får me $\( _n P _n = n! = 1 \cdot 2 \cdot \ldots \cdot (n-2)\cdot (n-1) \cdot n \)$

\(n!\) les me som n fakultet og er produktet av alle dei naturlege tala frå og med \(1\) til og med \(n\)

n = 20

komb = 1
for i in range(n):
    komb *= (n-i)
    
print(f"Elementa kan ordnast på {komb} måtar")

Elementa kan ordnast på 2432902008176640000 måtar

Uordna utval

Binomialkoeffesient, \(_n C_r\), er måten me kan trekka eit utval på \(r\) frå ein populasjon på \(n\) når rekkefølgen ikkje er viktig. $\( \left({n}\atop{r}\right) = \frac{_n P_r}{r!} = \frac{n!}{r!\cdot (n-r)!}\)$

Me kan rekna denne ut i Python med å bruka SciPy-biblioteket:

import scipy.special as sc

n = 5
r = 3

# nCr - uordna utval
uordna = sc.comb(n, r, exact = True)

print(f"nCr = {uordna}")

nCr = 10

SciPy til ordna utval og fakultet

Me kan bruka scipy.special til å rekna ut fakultet og permutasjonar òg:

import scipy.special as sc

n = 5
r = 3

# n! - fakultet
fakultet = sc.factorial(n, exact = True)
print(f"n! = {fakultet}")

# nPr - permutasjonar - ordna utval
ordna = sc.perm(n, r, exact = True) # nøyaktig, ikkje tilnærma...
print(f"nPr = {ordna}")

n! = 120
nPr = 60