kombinatorikk

Kombinatorikk er en gren av matematikken som studerer tellelige objekter og deres mønstre. Den behandler spørsmål som hvor mange måter et sett kan organiseres eller trekkes ut under visse regler, og hvordan objekter kan kobles sammen i strukturer. De mest grunnleggende temaene er telling, permutasjoner og kombinasjoner, men feltet omfatter også partisjonering, grafteori, designteori og kodingsteori. Viktige verktøy inkluderer binomialkoeffisienter, rekursjon, genererende funksjoner og ulike tellemetoder som inklusjon-eksklusjon og bijeksjoner.

Kombinatorikkens historie strekker seg fra gamle telleproblemer til moderne teori. Eulers arbeid på 1700-tallet bidro betydelig til grafteori og telleproblemer, og senere har Cayley og andre utviklet grafteori videre. På 1900-tallet fikk genererende funksjoner og Polya-enumerasjon betydelig innflytelse, sammen med partisjonsteori og tilknyttede områder. I dag er kombinatorikk en sentral disiplin med nær kontakt til informatikk, statistikk og anvendte fagfelt.

Anvendelser inkluderer databehandling og kryptografi, optimering og søkealgoritmer, design av eksperimenter, og utvikling av feilkorrigerende koder for kommunikasjon og lagring. Subfelter som grafteori, kombinatorisk design, partisjonsteori og kodingsteori dekker et bredt spekter av problemer. En enkel illustrasjon er telling: antall måter å velge k elementer fra et sett på n elementer er binomialkoeffisienten n velger k; antall måter å ordne n elementer er n!, og antallet derangementer er en spesifikk annen telleoppgave.