Kombinasjoner

Kombinasjoner er et grunnleggende begrep i kombinatorikk og beskriver måter å velge et delsett fra en endelig mengde der rekkefølgen ikke spiller noen rolle. En kombinasjon av n forskjellige elementer tatt k av gangen har antallet uttrykt ved binomialkoeffisienten C(n, k) = n! / (k!(n−k)!).

Eksempel: Fra en mengde med fem elementer velges tre; C(5, 3) = 10.

Kjente egenskaper inkluderer symmetrien C(n, k) = C(n, n−k) og den grunnleggende formelen at summen av C(n, k) over k fra 0 til n er 2^n. Når k > n, er C(n, k) normalt definert som 0.

Kombinasjoner kan ha gjentakelse (multisett), der samme element kan velges flere ganger. Antallet måter å velge k elementer fra n typer med ubegrenset gjentakelse er C(n+k−1, k).

Anvendelser omfatter å velge kortstok, trekninger i lotteri, utforming av komiteer og beregning av sannsynligheter i hypergeometriske modeller. I sannsynlighet og statistikk brukes kombinasjoner blant annet til å telle utfall når utvalg skjer uten tilbakelegg.

I kontrast teller man når rekkefølgen er viktig; da snakker man om permutasjoner i stedet for kombinasjoner. Kombinasjoner gir thus en måte å telle uordnede utvalg effektivt og brukes som byggestein i mange matematiske og praktiske problemstillinger.