1.2 Kombinatorikk: telle riktig

$$n_1 \cdot n_2 \cdots n_k.$$

Intuisjon: for hvert av de $n_1$ valgene i trinn 1 finnes $n_2$ valg i trinn 2, altså $n_1 n_2$ kombinasjoner for de to første trinnene, og så videre. Dette prinsippet ligger under alle de andre formlene i kapitlet.

$$n^k.$$

Det følger av multiplikasjonsprinsippet: $n$ muligheter i hvert av de $k$ trinnene. Eksempel: en firesifret PIN-kode har $10^4 = 10\,000$ muligheter.

$$n! = n \cdot (n-1) \cdots 2 \cdot 1, \qquad 0! = 1.$$

$n!$ teller antall måter å ordne $n$ ulike objekter i rekkefølge (en permutasjon). Fem bøker kan settes i hylla på $5! = 120$ måter. Konvensjonen $0! = 1$ trengs for at formlene under skal stemme.

$$\frac{n!}{(n-k)!} = n \cdot (n-1) \cdots (n-k+1).$$

Intuisjon: $n$ valg til første plass, $n-1$ til andre (ett er brukt opp), og så videre — $k$ synkende faktorer. Eksempel: gull, sølv og bronse blant 8 løpere kan fordeles på $8 \cdot 7 \cdot 6 = 336$ måter.

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}.$$

Intuisjon: start med de $n!/(n-k)!$ ordnede utvalgene. Hvert uordnet utvalg av $k$ objekter er telt $k!$ ganger (én gang for hver rekkefølge), så vi deler på $k!$. Eksempel: å velge 3 av 10 ansatte til et utvalg — $\binom{10}{3} = 120$.

$$\binom{n}{n_1, n_2, \ldots, n_r} = \frac{n!}{n_1!\,n_2! \cdots n_r!}.$$

Binomialkoeffisienten er spesialtilfellet med to grupper ($k$ valgte og $n-k$ ikke-valgte). Multinomialkoeffisienten teller også antall ulike anagram av et ord: del bokstavene i grupper etter hvilken bokstav de er.

$$P(X = x) = \frac{\binom{a}{x}\binom{b}{k-x}}{\binom{a+b}{k}}.$$

Intuisjon: teller = velg $x$ av de $a$ og $k-x$ av de $b$; nevner = alle måter å velge $k$ av $a+b$. Dette er telleoppsettet bak urne- og kvalitetskontrolloppgaver, og broen til den hypergeometriske fordelingen i kap. 2.2.

En ordning av objekter i rekkefølge. Antall permutasjoner av $n$ ulike objekter er $n!$. Skal bare $k$ av $n$ ordnes, er det $n!/(n-k)!$. Nøkkelordet er rekkefølge: hvis en omstokking gir et nytt utfall, teller du permutasjoner.

En kombinasjon er et uordnet utvalg — bare hvilke elementer, ikke rekkefølgen ($\binom{n}{k}$). En permutasjon er et ordnet utvalg — rekkefølgen teller ($n!/(n-k)!$). Sammenhengen: $\displaystyle \frac{n!}{(n-k)!} = \binom{n}{k}\cdot k!$, siden hvert uordnet utvalg svarer til $k!$ ordnede.

$$\binom{n}{k} = \binom{n}{n-k}.$$

Nyttig regnetriks: $\binom{20}{18} = \binom{20}{2} = 190$ er mye lettere å regne enn venstresiden direkte.

En mengde med $n$ elementer har $2^n$ delmengder (hvert element er enten med eller ikke). Sammenhengen med binomialkoeffisientene: $\sum_{k=0}^{n}\binom{n}{k} = 2^n$ — summerer du antall delmengder av hver størrelse, får du alle delmengdene.

$$P(\text{minst 1}) = 1 - P(\text{ingen}).$$

Standardgrepet i «minst én defekt / minst ett ess»-oppgaver.

$$\frac{n!}{n_1!\,n_2! \cdots n_r!}.$$

Intuisjon: hadde alle $n$ bokstavene vært ulike, ville det vært $n!$ omstokkinger; men bytter du om to like bokstaver, får du samme ord, så vi deler bort $n_i!$ for hver bokstavtype. Eksempel: STATISTIKK gir $10!/(2!\,3!\,2!\,2!) = 75\,600$ ord.

Bygg hånden i trinn og gang (multiplikasjonsprinsippet): velg valørene først, deretter fargene innen hver valør. En vanlig kortstokk har 13 valører (2–A) og 4 farger. Hold styr på om valørene er ombyttbare: i et «hus» er tresettets valør og parets valør ikke ombyttbare, så de velges hver for seg.