Kombinationer

Kombinationer bruger vi, når vi vælger et bestemt antal objekter fra en mængde, og rækkefølgen, som vi vælger objekterne i, ikke har betydning. Et typisk eksempel er lotto 6 ud af 49 — i urnen har vi 49 tal, og vi trækker 6 af dem, og det er ligegyldigt, i hvilken rækkefølge vi trækker dem.

Udledning af formlen

Lykkehjul

Lad os have en mængde M, fx M = {a, b, c, d, e}. Så er en kombination af r elementer en delmængde K ⊆ M, som indeholder præcis r elementer. Fordi K er en mængde, har rækkefølgen selvfølgelig ingen betydning. En kombination af tre elementer fra mængden M kunne altså være {a, b, d} eller {b, c, d}.

Forskellen i forhold til ordnet udvælgelse er, at rækkefølgen havde betydning, så (a, b, e) og (e, b, a) er forskellige ordnede udvælgelser, men de er samme kombination, for både (a, b, e) og (e, b, a) indeholder de samme elementer; at de står i en anden rækkefølge, er ikke interessant for kombinationer.

Men vi kan bruge ordnet udvælgelse til at få en formel for antallet af alle forskellige kombinationer. Vi ved, at antallet af ordnede udvælgelser af r elementer fra en mængde med n elementer er netop

$P (n, r) = \frac{n!}{(n - r)!} .$

Hvis vi altså beregnede antallet af alle ordnede udvælgelser af tre elementer fra den forrige mængde M = {a, b, c, d, e}, ville vi få P(5, 3) = 60 forskellige udvælgelser. Men for hvert tripel ville vi også have alle dets permutationer. Dvs. vi ville have tripelet abc, men også tripler acb, bac, bca, cab og cba. Det er seks forskellige ordnede udvælgelser, men det er én kombination, for de har alle de samme elementer.

Hvis vi har et tripel, hvor mange forskellige permutationer af dette tripel findes der så? Netop 3!. Med andre ord findes der netop 3! gange så mange ordnede udvælgelser af tre elementer som kombinationer af tre elementer. I stedet for at regne med én kombination regner vi med 3! gange flere ordnede udvælgelser, med hver permutation af det givne tripel. Så hvis vi dividerer antallet af ordnede udvælgelser med 3!, får vi antallet af kombinationer.

Den foregående fremgangsmåde kan vi generalisere og sige, at hvis vi søger antallet af alle forskellige kombinationer af r elementer fra en mængde af størrelse n, så er dette antal, som vi betegner K(n, r), lig med,

$K (n, r) = \frac{P (n, r)}{r!},$

dvs. antallet af ordnede udvælgelser divideret med r!, hvilket er antallet af permutationer af hvert r-tupel. Formlen kan vi omskrive ved at skrive formlen for beregning af ordnede udvælgelser ud:

$K (n, r) = \frac{P (n, r)}{r!} = \frac{n!}{(n - r)!} \cdot \frac{1}{r!} = \frac{n!}{(n - r)! \cdot r!} .$

Eksempel: antallet af kombinationer af to elementer fra mængden {a, b, c} er

$K (3, 2) = \frac{3!}{1! \cdot 2!} = 3$

og det er disse kombinationer: {a, b}, {a, c} og {b, c}. For kombinationer af tre elementer fra den oprindelige mængde M = {a, b, c, d, e} ville vi få antallet

$K (5, 3) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

og det er disse kombinationer: {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}.

Binomialkoefficient

Ud over den foregående skrivemåde med K(n, r) bruger man også den såkaldte binomialkoefficient. Binomialkoefficienten har denne form

$(\binom{n}{r})$

det er en slags brøk uden brøkstreg (som du alligevel af gammel vane vil komme til at skrive), men med parenteser (de er ikke valgfrie, de skal være der). Binomialkoefficienten læser vi »n over r«. Binomialkoefficientens værdi er så den samme som K(n, r).

$(\binom{n}{r}) = \frac{n!}{(n - r)! \cdot r!}$

Så hvis vi har en mængde med 5 elementer og vælger grupper på fire elementer fra den, bliver deres samlede antal

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Grundlæggende sammenhænge

For binomialkoefficienten og n ∈ ℕ gælder:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Desuden gælder for n, r ∈ ℕ₀ og r ≤ n

$\begin{array}{rcl} (\binom{n}{n - r}) & = & (\binom{n}{r}) . \end{array}$

Og for n, r ∈ ℕ₀ og r < n gælder

$\begin{array}{rcl} (\binom{n}{r}) + (\binom{n}{r + 1}) & = & (\binom{n + 1}{r + 1}) . \end{array}$

Beregner

Følgende beregner finder binomialkoefficienten n over r.

Løste eksempler

Vi begynder med det allerede nævnte lotto. Her trækkes der i alt 6 kugler fra en urne, hvor der er 49 kugler. Hvor mange forskellige muligheder kan der udtrækkes?

Først og fremmest — har rækkefølgen af trækningen af tallene betydning? Nej, vi tipper kun tallene, ikke deres rækkefølge. Vi bruger kombinationer. Vi har i alt 49 kugler, vi trækker 6 kugler, og vi får binomialkoefficienten

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13.983 .816$

Der er i alt 13.983.816 muligheder for, hvad der kan udtrækkes. Hvilket i øvrigt giver os sandsynligheden for at vinde med én række 1/13.983.816, hvilket er 0,00000715112 %.
Oscar, kendt som en charmør, er lige nu til landsbyfest, hvor der er i alt 13 smukke piger, som han kunne være interesseret i. Oscar ved, at han kan gøre 4 forskellige piger glade i løbet af en aften. Hvor mange forskellige grupper på fire kan Oscar vælge mellem?

Det er igen et enkelt eksempel på kombinationer, rækkefølgen har ikke betydning, Oscar vil være lige så god ved den første pige som ved den sidste. Vi får således en mængde på 13 piger, hvoraf vi altid vælger 4 piger. Det fører til binomialkoefficienten

$(\binom{13}{4}) = 715.$
Du har en gruppe på halvtreds personer - halvdelen mænd og halvdelen kvinder. Hvor mange forskellige grupper på tre personer findes der, hvis de ikke må bestå af kun ét køn (dvs. i gruppen må der ikke være tre mænd eller tre kvinder).

Det er allerede en lidt sværere kombination. Hvis vi udelukker grupper af ét køn, er der kun to muligheder for, hvordan gruppen kan være sammensat - to mænd og én kvinde eller én mand og to kvinder, hvor antallet af kombinationer i den første gruppe (to mænd og én kvinde) er det samme som antallet af kombinationer i den anden gruppe. Det er altså nok at beregne antallet af kombinationer i den første gruppe og så gange det med to. Nu er det igen en leg. Vi bestemmer antallet af kombinationer af forskellige par af mænd, hvilket er femogtyve over to, og ganger det med antallet af kombinationer af én kvinde (det er femogtyve, se de grundlæggende sammenhænge ovenfor, konkret anden linje). Dette resultat ganger vi blot med to, og så har vi det endelige resultat.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
I en kasse er der 15 produkter, hvoraf 4 er defekte. På hvor mange måder kan man vælge 6 produkter, således
- at ingen er defekt? Nu vælger vi 6 produkter blandt de 15 − 4 = 11 produkter, som ikke er defekte. Vi får således binomialkoefficienten
  
  $(\binom{11}{6}) = 462.$
- at præcis ét produkt er defekt? Vi vælger således en mængde, som indeholder 5 fungerende produkter og 1 defekt. Vi har i alt 11 fungerende produkter og 4 defekte. Vi bruger multiplikationsprincippet og får resultatet:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- at højst ét er defekt? Til løsningen bruger vi de foregående resultater. Vi ved, at vi har i alt 462 muligheder for at vælge præcis 6 fungerende produkter, og vi har 1848 muligheder for at vælge fem fungerende og ét defekt produkt. Vi bruger således additionsprincippet, lægger disse resultater sammen, og så har vi det resultat, vi vil have, dvs. højst ét defekt produkt (= enten intet defekt produkt eller præcis ét). Resultatet er således: 462 + 1848 = 2310.

Kapitler: Kombinatorik, Ordnet udvælgelse, Permutationer, Kombinationer, Ordnet udvælgelse med tilbagelægning, Kombinationer med gentagelser, Hvor mange forskellige pinkoder findes der?

« Forrige: Permutationer

Næste: Ordnet udvælgelse med tilbagelægning »