• Artiklens indhold er godkendt af redaktionen

kombinatorik

Oprindelig forfatter MELa Seneste forfatter Redaktionen

kombinatorik, 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, 56824.301.jpg. 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, 56824.401.jpg

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 2n. På den anden side kan antallet beregnes ved at summere antallet af delmængder med 0,1,...,n elementer. Derfor gælder formlen 56824.402.jpg
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 xk 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 56824.403.jpg som med x = 1 giver formlen ovenfor. I dette eksempel kaldes (1+x)n den frembringende funktion for binomialkoefficienten. Også andre kombinatoriske størrelser har frembringende funktioner.

Annonce

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.

Referér til denne tekst ved at skrive:
Mogens Esrom Larsen: kombinatorik i Den Store Danske, Gyldendal. Hentet 4. april 2020 fra http://denstoredanske.dk/index.php?sideId=108358

    • Artiklens indhold er godkendt af redaktionen

    • Kommentar til redaktionen Vedr. kombinatorik Marker den cirkel
      Send kommentar


  • Copyright

    Denne artikel må du ...

  • Kilde

    Denne artikel stammer fra:
    Leksikon

  • Historik