spesialkombinasjoner

Spesialkombinasjoner er et begrep som brukes i kombinatorikk og sannsynlighet for å beskrive spesielle eller begrensede former for utvalg av objekter fra en mengde. I motsetning til enkle k-kombinasjoner underlegges disse utvalgene ekstra betingelser, for eksempel restriksjoner på avstand mellom valgte elementer eller mulighet for gjentakelse av elementer.

Eksempler på spesialkombinasjoner inkluderer kombinasjoner uten gjentakelser men med restriksjoner. For eksempel kan man hente k elementer fra en rad av n elementer slik at ingen to valgte er naboer. Antallet løsninger er da gitt av binomialkoeffisienten C(n-k+1, k). En annen type er kombinasjoner med gjentakelser, der hvert element kan gjentas og det totale antallet k deles mellom n forskjellige typer elementer; antallet løsninger er C(n+k-1, k). Det finnes også sirkulære eller runde spesialkombinasjoner (kombinasjoner i en sirkel) og kombinasjoner med forbudte elementer eller posisjoner.

Beregningsmetoder for spesialkombinasjoner inkluderer inkludering–eksklusjon-prinsippet, genererende funksjoner og rekursive oppsett. Disse verktøyene gir måter å telle eller enumerate løsninger under ulike restriksjoner, ofte ved å dele problemet opp i enklere delproblemer eller ved å bruke algebraiske representasjoner.

Anvendelser av spesialkombinasjoner finner man i spillteori, kort- og lotterispill, eksperimentdesign, koding og informasjonsteori, samt i problemløsning hvor man må oppfylle flere samtidig gitte betingelser. Begrepet henger tett sammen med relaterte emner som binomialkoeffisienter, kombinasjonsteori, multiset-kombinasjoner og genererende funksjoner, og gir en ramme for å analysere og telle komplekse utvalgsproblemer.

Se også: binomialkoeffisienter, kombinasjoner, kombinasjon i tillegg til konsepter som genererende funksjoner og inkludering–eksklusjon-prinsippet.