Kombinationer
Lad der være givet en mængde med n forskellige elementer. Vi ønsker at bestemme antallet af måder, man kan udtage en delmængde bestående af r elementer. Et eksempel kunne være, at man gerne vil vide på hvor mange måder et 5-mands udvalg kan sammensættes ved at udvælge 5 elever fra en klasse med eksempelvis 25 elever.
Men lad os se på et lidt simplere eksempel. Vi har en 5-mængde, d.v.s. en mængde bestående af 5 elementer, som vi for eksempel kan kalde A, B, C, D og E. Vi vil nu undersøge, hvor mange forskellige 3-mængder, vi kan udtage af denne 5-mængde. En sådan 3-mængde kaldes også en kombination (evt. en 3-kombination), og vi er altså interesseret i at bestemme antallet af sådanne mulige kombinationer. Et eksempel på en kombination er mængden {A, B, C}, en anden mængden {A, C, D}. Læg mærke til, at vi kun interesserer os for hvilke elementer, der er med i 3-mængden, men er ligeglade med den rækkefølge de udvælges i.
Det ses (forholdsvis) let, at de mulige kombinationer i dette simple eksempel må være:
{A,B,C} {A,B,D} {A,B,E} {A,C,D} {A,C,E} {A,D,E} {B,C,D} {B,C,E} {B,D,E} {C,D,E}
Der er altså 10 mulige kombinationer.
Metoden med at opskrive alle kombinationerne er dog besværlig og i eksempler som det med 5-mands udvalget ovenfor, er det helt uoverkommeligt. Vi har derfor brug for en enklere metode, og en sådan findes da heldigvis også:
|
Antallet af r-mængder, som kan udtages af en n-mængde betegnes {$K(n,r)$} og kan beregnes v.h.a. formlen: {$$K(n,r) = \frac{n!}{r!(n-r)!} $$} {$K(n,r)$} skrives også {$\binom{n}{k}$} og kaldes en binomialkoefficient |
Bevis for fomlen for {$K(n,r)$}
Vi vil begynde med at udlede formlen for eksemplet {$K(5,3)$} og derefter generalisere resultatet.
Vi skal altså udtage tre elementer fra en 5-mængde. Der er derfor 5 muligheder for at vælge det første element, hvorefter der er 4 muligheder for at vælge det andet element og endelig 3 muligheder for at vælge det sidste element.
Til sidst er der for hver kombination af de to først udvalgte elementer 3 muligheder for at vælge det sidste element. Vi får altså, at der i alt er {$5\cdot4\cdot3 = 60$} mulige måder at udtrække de tre elementer på. Her skal vi dog være opmærksom på, at de forskellige rækkefølger, som en 3-mængde kan udtages i, alle bliver talt med. F.eks. kan de første tre elementer (A, B og C) jo udtages i rækkefølgerne ABC, ACB, BAC, BCA, CAB, CBA, som altså alle bliver talt med.
Vi skal udtage r elementer af en n-mængde.
Antallet af måder man kan udtage en 3-mængde af en 5-mængde kan altså beregnes sådan:
{$$K(5,3) = \frac{5!}{3!(5-3)!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1 \cdot 2 \cdot 1} = \frac{120}{12} = 10$$}
Og antallet af måder man kan udtage en 5-mængde ud af en 25-mængde bliver:
{$$K(25,5) = \frac{25!}{5!(25-5)!} = 53130$$}