Kombinatorik er en matematisk disciplin, der omhandler kunsten at tælle endelige mængder. Ordet stammer fra Leibniz 1666, og teknikken spillede en afgørende rolle for udviklingen af sandsynlighedsregningen, fordi en sandsynlighed for en gunstig hændelse blandt endeligt mange mulige og lige sandsynlige hændelser kan beregnes som forholdet mellem antallet af gunstige og antallet af mulige. Derfor er det de samme, som udviklede sandsynlighedsregningen, Fermat, Pascal, Bernoulli og Euler, som til dette formål udviklede kombinatorikken betydeligt.

Det elementære problem er at bestemme antallet af kombinationer af \(k\) elementer fra en mængde med \(n\) elementer, dvs. antallet af udpluk på \(k\) elementer uden hensyn til rækkefølgen. Løsningen er binomialkoefficienten, \({n \choose k}\). Et tilsvarende problem er at bestemme antallet af \(k\)-permutationer eller \(k\)-arrangementer, der består af sæt af \(k\) elementer i en bestemt rækkefølge. Løsningen er \(k\)-faktoriellen af \(n\), \[|n|_k = {n \choose k} \cdot k! = n \cdot (n-1) \cdot ... \cdot (n-k+1).\]

To lidt mere specielle problemer er at bestemme antallet af måder, en mængde kan deles i \(k\) ikke-tomme og ikke-overlappende delmængder, samt at bestemme antallet af de permutationer af \(n\) elementer, som består af netop \(k\) ikke-overlappende cykler (en cykel er en permutation af formen 1→2→3→∙∙∙→i→ 1). Disse to problemer løses af Stirlingtallene af hhv. anden og første art. Endnu et specielt problem er at tælle de permutationer af tallene \(1,...,n\), der har et større tal umiddelbart efter et mindre netop \(k\) gange. Dette løses af tal opkaldt efter Euler (ikke at forveksle med Eulertal).

Et kombinatorisk argument for en formel består i, at en given mængde tælles på to måder. Da det var samme mængde, må de to summer være ens. Et eksempel er antallet af delmængder af en given mængde med \(n\) elementer. Da hvert element enten er med i en given delmængde eller ej, er deres antal \(2^n\). På den anden side kan antallet beregnes ved at summere antallet af delmængder med \(0,1,...,n\) elementer. Derfor gælder formlen \[2^n = {n \choose 0} + {n \choose 1} + \dots + {n \choose n}.\]

Et algebraisk argument for en mere generel formel består i at beregne \((1+x)^n\). Det vil være et polynomium af grad \(n\), og koefficienten til leddet \(x^k\) bliver antallet af måder, vi kan udtage de \(k\) faktorer, som skal bidrage med et \(x\). De resterende \(n-k\) bidrager med faktoren 1. Derfor har vi formlen \[(1+x)^n = {n \choose 0} + {n \choose 1}x + \dots + {n \choose n}x^n\] som med \(x = 1\) giver formlen ovenfor. I dette eksempel kaldes \((1+x)\) den frembringende funktion for binomialkoefficienten. Også andre kombinatoriske størrelser har frembringende funktioner.

Ligninger med kombinatoriske størrelser kaldes kombinatoriske identiteter; et typisk eksempel er Chu-Vandermondes formel. Kombinatoriske identiteter har påkaldt sig særlig interesse efter 1990, da det lykkedes den amerikanske matematiker D. Zeilberger (f. 1950) at lave computerprogrammer til verifikation af sådanne identiteter. Metoden fungerer i de fleste simple tilfælde, hvor identiteten kan skrives på hypergeometrisk form, men man kender mange identiteter, såvel hypergeometriske som andre, som ikke kan verificeres med denne automatiske metode.

Kommentarer

Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.

Du skal være logget ind for at kommentere.

eller registrer dig