Kombinationer

I det här avsnittet ska vi introducera begreppet kombination, lära oss hur kombinationer förhåller sig till permutationer och hur vi kan beräkna antalet kombinationer.

Kombinationer

När vi i det förra avsnittet studerade permutationer utgick vi från en mängd bestående av n stycken element och valde sedan ut k av dessa element, och tog hänsyn till ordningen som de utvalda elementen hamnade i. Detta antal permutationer betecknade vi P(n, k) och beräknade på följande sätt:

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

där 0 ≤ k ≤ n.

Har vi till exempel en mängd {a, b, c, d} och ska välja tre av dessa fyra element, då kan vi med hjälp av formeln ovan beräkna att antalet permutationer är 24. Av dessa 24 permutationer kommer bland annat följande val av element alla att innehålla samma tre element, men utgöra separata permutationer av dessa tre element: abc, acb, bac, bca, cab, cba.

Om vi däremot bara är intresserade av vilka element som väljs ut, inte i vilken ordning valen av element görs, då har vi att göra med en annan situation.

Jämför vi med vårt exempel ovan, där vi valde tre av de fyra elementen i mängden {a, b, c, d}, då kommer vi att inse att bland annat de sex permutationerna abc, acb, bac, bca, cab och cba ju består av samma tre element. Därför ska dessa permutationer bara räknas en gång när vi enbart är intresserade av vilka element som väljs ut, inte i vilken ordning valen gjorts.

Ett val av k element från en mängd bestående av n element, när vi inte tar hänsyn till ordningen som elementen står i, kallar vi en kombination.

Antalet kombinationer med k element från en mängd bestående av n element betecknar vi C(n, k) eller \(\binom{n}{k}\), där \(\binom{n}{k}\) uttalas "n över k", och beräknas på följande sätt:

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

där 0 ≤ k ≤ n.

Enligt denna formel beräknar vi alltså antalet kombinationer C(n, k) genom att vi först beräknar antalet permutationer P(n, k) och sedan dividerar detta antal med k! för att bli av med de permutationer som annars räknas flera gånger.

Vi har fem olika böcker i en bokhylla och tänker ta med oss två av dessa böcker när vi ska ut och resa.

På hur många olika sätt kan vi välja två av de fem böckerna, om vi bara bryr oss om vilka böcker vi får med oss, inte i vilken ordning vi valde böckerna?

Eftersom vi inte bryr oss om i vilken ordning vi väljer böckerna, är det antalet kombinationer som vi är intresserade av att beräkna. Vi har fem element (olika böcker) att välja mellan och ska välja ut två av dessa element (böcker).

Därför räknar vi så här:

$$C(5,\,2)=\binom{5}{2}=\frac{5!}{(5-2)!\cdot 2!}=$$

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

$$=\frac{5\cdot 4\cdot 3!}{3!\cdot 2}=$$

$$=\frac{5\cdot 4}{2}=10$$

Vad vi har kommit fram till är alltså att vi kan välja vilka de två böckerna är på tio olika sätt.

Användbar symmetri

När vi beräknar antalet kombinationer kan vi lätt hamna i situationer med stora tal inblandade. I sådana situationer kan vi ibland använda oss av en symmetriegenskap som kan förenkla våra beräkningar.

Om vi till exempel har fem böcker i en bokhylla och ska välja ut två av dessa böcker utan att ta hänsyn till i vilken ordning valen görs, då motsvarar detta att välja ut vilka tre böcker som ska stå kvar i bokhyllan (det vill säga, vilka som inte ska väljas ut).

Detta innebär att följande likhet gäller:

$$\binom{5}{2}=\binom{5}{3}$$

Allmänt gäller följande räkneregel, som säger oss att antalet kombinationer då vi väljer k element av n element är lika många som om vi väljer (n-k) element av n element:

$$\binom{n}{k}=\binom{n}{n-k}$$

Denna räkneregel kan vi härleda på följande sätt med hjälp av den allmänna formeln för antalet kombinationer:

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

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

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

$$=\frac{P(n,\,k)}{k!}=\binom{n}{k}$$

Utifrån vårt exempel med valet av två av fem böcker i bokhyllan, kan vi alltså om vi vill med hjälp av denna räkneregel även räkna på följande sätt:

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

$$=\frac{5\cdot 4\cdot 3!}{2\cdot 3!}=\frac{5\cdot 4}{2}=10$$

Utöver denna räkneregel kan vi även ha användning av att känna till antalet kombinationer då vi väljer antingen noll eller samtliga element av n element.

Att välja noll element av n element kan bara göras på ett sätt (genom att inte välja något element):

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

Att välja samtliga n element av n element kan även det bara göras på ett sätt (genom att välja samtliga n element):

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