Kombinationer

Kombinationer använder vi när vi väljer ett visst antal objekt ur en mängd av objekt och ordningen i vilken vi väljer objekten inte spelar roll. Ett typiskt exempel är lotto 6 av 49 – i urnan har vi 49 tal och vi drar 6 av dem, och det spelar ingen roll i vilken ordning vi drar dem.

Härledning av formeln

Lyckohjul

Vi tar en mängd M, till exempel M = {a, b, c, d, e}. Då är en kombination av k element en delmängd K ⊆ M som innehåller precis k element. Eftersom K är en mängd spelar ordningen naturligtvis ingen roll. En kombination av 3 element ur mängden M skulle alltså kunna vara {a, b, d} eller {b, c, d}.

Skillnaden mot ordnat urval är att ordningen spelade roll där, så (a, b, e) och (e, b, a) är olika ordnade urval, men de är samma kombination, eftersom både (a, b, e) och (e, b, a) innehåller samma element; att de står i en annan ordning intresserar oss inte när det gäller kombinationer.

Men vi kan använda ordnat urval för att få fram en formel för antalet olika kombinationer. Vi vet att antalet ordnade urval av k element ur en mängd med n element är precis

$\frac{n!}{(n - k)!} .$

Om vi alltså räknade ut antalet ordnade urval av 3 element ur den tidigare mängden M = {a, b, c, d, e}, skulle vi få 60 olika ordnade urval. Men för varje tripel skulle vi då ha med alla dess permutationer. Dvs. vi skulle ha tripeln abc, men också triplerna acb, bac, bca, cab och cba. Det här är sex olika ordnade urval, men det är en kombination, eftersom alla har samma element.

Om vi har en tripel, hur många olika permutationer av den finns det? Precis 3!. Med andra ord finns det precis 3! gånger fler ordnade urval av 3 element än kombinationer av 3 element. I stället för att räkna med en kombination räknar vi med 3! gånger fler ordnade urval, med varje permutation av den givna tripeln. Så om vi delar antalet ordnade urval med 3! får vi antalet kombinationer.

Det föregående resonemanget kan vi generalisera och säga att om vi söker antalet olika kombinationer av k element ur en mängd med storleken n, så är detta antal lika med antalet ordnade urval dividerat med k!, vilket är antalet permutationer av varje k-tipel. Formeln kan vi förenkla genom att skriva ut formeln för antalet ordnade urval:

$\frac{\frac{n!}{(n - k)!}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Exempel: antalet kombinationer av 2 element ur mängden {a, b, c} är

$\frac{3!}{1! \cdot 2!} = 3$

och det är de här kombinationerna: {a, b}, {a, c} och {b, c}. För kombinationer av 3 element ur den ursprungliga mängden M = {a, b, c, d, e} skulle vi få antalet

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

och det är de här kombinationerna: {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

I stället för den här formeln skriver man oftast den s.k. binomialkoefficienten. Binomialkoefficienten har den här formen

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

det är ett slags bråk utan bråkstreck (som du ändå kommer att skriva dit av ren vana), men med parenteser (de är inte valfria, de måste vara där). Binomialkoefficienten läser vi ”n över k”. Värdet av binomialkoefficienten är

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

Så om vi har en mängd med 5 element och väljer 4 element ur den, blir det totala antalet

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

Grundläggande samband

För binomialkoefficienten och n ∈ ℕ gäller:

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

Vidare gäller för n, k ∈ ℕ och k ≤ n

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

Och för n, k ∈ ℕ och k < n gäller

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

Miniräknare

Följande miniräknare beräknar binomialkoefficienten n över k.

Lösta exempel

Vi börjar med lotto 6 av 49 som vi nämnde ovan. Där dras totalt 6 kulor ur en urna med 49 kulor. Hur många olika dragningar är möjliga?

Först av allt – spelar ordningen på dragningen roll? Nej, vi tippar bara talen, inte deras ordning. Vi använder kombinationer. Vi har totalt 49 kulor, vi drar 6 kulor och får binomialkoefficienten

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

Det finns totalt 13 983 816 möjligheter som kan dras. Det ger oss i förbigående sannolikheten att vinna med en enda rad 1/13 983 816, vilket är 0,00000715112 %.
William, känd som en riktig charmör, är på en danskväll i bygdegården där det finns totalt 13 trevliga tjejer som han skulle vilja träffa. William vet att han hinner göra 4 olika tjejer glada under en kväll. Ur hur många olika fyrgrupper kan William välja?

Det här är återigen ett enkelt exempel på kombinationer, ordningen spelar ingen roll, William blir lika bra med den första tjejen som med den sista. Vi får alltså en mängd med 13 tjejer, ur vilken vi alltid väljer 4 tjejer. Det leder till binomialkoefficienten

$(\binom{13}{4}) = 715.$
Du har en grupp på femtio personer – hälften män och hälften kvinnor. Hur många olika grupper om tre personer finns det, om de inte får bestå av enbart ett kön (dvs. gruppen får inte bestå av tre män eller tre kvinnor).

Det här är en lite svårare kombination. Om vi utesluter grupper av ett enda kön återstår bara två möjligheter för hur gruppen kan vara sammansatt – två män och en kvinna eller en man och två kvinnor, där antalet kombinationer i den första gruppen (två män och en kvinna) blir lika stort som antalet kombinationer i den andra gruppen. Det räcker alltså att vi räknar ut antalet kombinationer i den första gruppen och sedan multiplicerar det med två. Nu är det återigen enkelt. Vi bestämmer antalet kombinationer av olika par av män, vilket är tjugofem över två, och multiplicerar det med antalet kombinationer av en kvinna (det är tjugofem, se grundläggande samband ovan, närmare bestämt andra raden). Det här resultatet multiplicerar vi bara med två och har slutresultatet.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
I en låda finns 15 produkter, varav 4 är defekta. På hur många sätt kan man välja 6 produkter så att
- ingen är defekt? Nu väljer vi 6 produkter ur 15 − 4 = 11 produkter som inte är defekta. Vi får alltså binomialkoefficienten
  
  $(\binom{11}{6}) = 462.$
- exakt en produkt är defekt? Vi väljer alltså en mängd som innehåller 5 fungerande produkter och 1 defekt. Fungerande produkter har vi totalt 11, defekta har vi 4. Vi använder multiplikationsprincipen och får resultatet:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- högst en produkt är defekt? För att lösa det använder vi de tidigare resultaten. Vi vet att vi har totalt 462 möjligheter att välja precis 6 fungerande produkter och 1848 möjligheter att välja fem fungerande och en defekt produkt. Vi använder alltså additionsprincipen, adderar de här resultaten och får det resultat som vi vill ha, dvs. högst en defekt produkt (= antingen ingen defekt produkt eller exakt en). Resultatet blir: 462 + 1848 = 2310.

Kapitel: Kombinatorik, Ordnat urval, Permutationer, Kombinationer, Ordnat urval med återläggning, Kombinationer med upprepning, Hur många olika PIN-koder finns det?

« Föregående: Permutationer

Nästa: Ordnat urval med återläggning »