De to grunnreglene

All telling bygger på to prinsipper. Produktregelen gjelder når en oppgave løses i en sekvens av uavhengige steg: hvis steg 1 kan gjøres på \(n_1\) måter, steg 2 på \(n_2\) måter osv., er totalen \(n_1 \cdot n_2 \cdots n_k\). Dette tilsvarer kardinaliteten av et kartesisk produkt. Sumregelen gjelder når oppgaven kan utføres på én av flere disjunkte måter: da legges antallene sammen. Huskeregel: «og/så» peker mot multiplikasjon, et disjunkt «eller» mot addisjon.

Produktregel: sekvensielle uavhengige valg \(\Rightarrow\) \(n_1 \cdot n_2 \cdots n_k\).

Sumregel: disjunkte alternativer \((A \cap B = \emptyset) \Rightarrow |A \cup B| = |A| + |B|\).

De fire utvalgstypene

Når du velger \(k\) elementer fra \(n\), still alltid to spørsmål: (1) teller rekkefølgen? (2) er gjentakelse tillatt? Svarene gir fire kombinasjoner med hver sin formel.

Ordnet, uten tilbakelegging (permutasjon): \(P(n,k) = \dfrac{n!}{(n-k)!}\)

Ordnet, med tilbakelegging (strenger): \(n^k\)

Uordnet, uten tilbakelegging (kombinasjon): \(\binom{n}{k} = \dfrac{n!}{k!(n-k)!}\)

Uordnet, med tilbakelegging (stars and bars): \(\binom{n+k-1}{k}\)

Sammenhengen \(P(n,k) = k! \cdot \binom{n}{k}\) viser at en permutasjon er en kombinasjon (velg hvilke) etterfulgt av en ordning (\(k!\) rekkefølger).

Binomialkoeffisienter og identiteter

\(\binom{n}{k}\) teller antall \(k\)-elements delmengder av en \(n\)-mengde. Sentrale identiteter: symmetri \(\binom{n}{k}=\binom{n}{n-k}\), Pascals regel \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\), og \(\sum_{k=0}^{n}\binom{n}{k}=2^n\) (antall delmengder). Binomialteoremet: \((x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k\).

Strengtelling og funksjoner

Antall strenger av lengde \(k\) over et \(n\)-symbols alfabet er \(n^k\). Det samme tallet teller antall funksjoner fra en \(k\)-mengde til en \(n\)-mengde. Injektive funksjoner tilsvarer ordnet utvalg uten tilbakelegging, \(P(n,k)\).

Inklusjon-eksklusjon og komplementtelling

Når mengder overlapper: \(|A\cup B|=|A|+|B|-|A\cap B|\), og for tre mengder legges trippelsnittet tilbake. Komplementtelling \(|A|=|U|-|\overline{A}|\) er gull verdt ved «minst én»-oppgaver, der komplementet «ingen» ofte er ett enkelt tilfelle.

Eksempel 1: Hvor mange bitstrenger av lengde 8 inneholder minst én null?

Totalt antall strenger: \(2^8 = 256\)

Strenger uten noen null (bare enere): kun \(11111111\), altså \(1\)

Komplementtelling: \(256 - 1 = 255\)

Eksempel 2: Hvor mange heltall i \(\{1,\dots,100\}\) er delelige med 2 eller 5?

Delelige med 2: \(\lfloor 100/2\rfloor = 50\)

Delelige med 5: \(\lfloor 100/5\rfloor = 20\)

Delelige med 10 (snittet): \(\lfloor 100/10\rfloor = 10\)

Inklusjon-eksklusjon: \(50 + 20 - 10 = 60\)

Eksempel 3: Hvor mange ikke-negative heltallsløsninger har \(x_1+x_2+x_3=10\)?

Modell: 10 stjerner og \(3-1=2\) skillevegger

Stars and bars: \(\binom{n+k-1}{k}=\binom{3+10-1}{10}=\binom{12}{10}\)

\(\binom{12}{10}=\binom{12}{2}=\dfrac{12\cdot 11}{2}=66\)

Studieguide: Kombinatorikk

Studieguide: Kombinatorikk