combinatoriske

Kombinatorik er en gren af matematikken, der beskæftiger sig med tælling, konstruktion og analyse af objekter under givne regler. Den undersøger spørgsmål som hvor mange forskellige objekter der kan forekomme, hvordan objekter kan arrangeres uden gentagelser, og hvilke strukturer der kan eksistere inden for bestemte begrænsninger. Metoderne bygger ofte på logik, beviser og algoritmer.

De centrale områder omfatter optælling, herunder permutationer, kombinationer og binomialkoefficienter; grafteori med stier, cykler, farvning og matchings; partitions (opdeling af talmængder) og designteori, som beskæftiger sig med konstruktion af objekter med bestemte egenskaber. Den studerer også eksistens- og konstruktionproblemer i tilknytning til talteori og algebraiske strukturer.

Metoderne spænder fra rekursion og matematisk induktion til genererende funktioner, bijektioner og probabilistiske metoder. Genererende funktioner giver et kraftfuldt sprog til tælling og asymptotiske analyser, mens den probabilistiske metode ofte beviser universelle tilstande ved hjælp af tilfældige konstruktioner. Analytiske og algoritmiske teknikker anvendes til at finde effektive måder at tælle eller konstruere objekter på.

Anvendelserne omfatter informatik (algoritmer, kompleksitet og datahåndtering), kryptografi og informations-teori, design af eksperimenter i biologi og landbrug samt kombinatorisk optimering og kodningsteori.

Historisk opstod kombinatorik i flere tidlige tællingsproblemer og blev formaliseret gennem arbejder af Pascal og Fermat; senere bidrog Euler, og i det 20. århundrede blev Ramsey-teori og grafteori centrale områder. Feltet er siden vokset til en central disciplin inden for moderne matematik og teoretisk datalogi.