kombinasjonsproblem

Kombinasjonsproblem, eller problemer i kombinatorikk, omhandler telling, utvalg og ordning av objekter under gitte regler. Slike spørsmål oppstår ofte i sannsynlighet, statistikk, datavitenskap og design av eksperimenter, og løses ofte ved å telle mulige konfigurasjoner uten å gjøre eksplisitte beregninger av hver.

Kjerneproblemtyper inkluderer telling av objekter der rekkefølgen ikke spiller rolle (kombinasjoner), og ordning av objekter (permutasjoner), samt valg med eller uten gjentakelse. Når rekkefølgen ikke gjelder, brukes kombinasjoner uten repetisjon: antall måter å velge k objekter fra n er C(n,k) = n!/(k!(n−k)!). Når rekkefølgen teller, er antallet ordnede utvalg k fra n gitt av P(n,k) = n!/(n−k)!. Ved repetisjon tillatt, fås kombinasjoner med gjentakelse: C(n+k−1,k). Permutasjoner med gjentakelse justeres tilsvarende.

De grunnleggende verktøyene inkluderer additiv og multiplikativ telleregel, samt prinsipper som inklusjons–eksklusjons. Bruk av binomialkoeffisienter og faktoriell tallteknikker er vanlig, og rekursive forhold, genererende funksjoner og dynamisk programmering brukes for mer komplekse telleoppgaver eller betingede utvalg.

Eksempel: antall måter å velge tre kort fra en 52-korts kortstokk er C(52,3). Antall ordninger av tre bokstaver fra et alfabet med fem bokstaver er 5^3. Anvendelser av kombinatorikk finnes i sannsynlighet, koding, design og ressursplanlegging.