Permutationer

I det här avsnittet introducerar vi begreppet permutation och i vilka situationer dessa förekommer, och lär oss hur vi kan beräkna antalet permutationer. Kunskap om hur vi beräknar antalet permutationer kommer vi även att använda oss av i nästa avsnitt, då vi beräknar antalet kombinationer.

Permutationer

Tänk dig att det står tre olika böcker på ett hyllplan i en bokhylla. På hur många olika sätt kan du ordna dessa böcker bredvid varandra på hyllplanet?

Vi kan tänka så här: en av böckerna kommer att stå längst till vänster, en i mitten och en längst till höger. Om vi börjar med att välja vilken av de tre böckerna som ska stå längst till vänster, har vi alltså tre böcker att välja på. När vi sedan har valt den bok som ska stå längst till vänster återstår två böcker;  en av dessa två böcker ska stå i mitten. Sedan vi valt vilken bok som ska stå till vänster och vilken som ska stå i mitten återstår bara en bok, så den boken får då stå längst till höger på hyllplanet.

Det här innebär att vi först ska välja ett element av tre, sedan ett element av två och slutligen ett element av ett. Därför finns det sex olika möjliga sätt att ordna böckerna bredvid varandra, vilket vi kommer fram till med hjälp av multiplikationsprincipen:

$$3\cdot 2\cdot 1=6$$

Om vi betecknar böckerna a, b och c, har vi alltså följande sätt att ordna böckerna från vänster till höger på hyllplanet: abc, acb, bac, bca, cab, cba.

Dessa olika sätt att ordna böckerna kallar vi permutationer av tre element ur mängden {a, b, c}.

n-fakultet

När vi räknar med antalet permutationer stöter vi ofta på beräkningar av typen

$$3 \cdot 2 \cdot 1$$

För att underlätta våra beräkningar används skrivsättet 3! när vi menar

$$3 \cdot 2 \cdot 1$$

Detta utläses "3-fakultet". På motsvarande sätt är till exempel 5! samma sak som

$$5\cdot 4 \cdot 3 \cdot 2 \cdot 1$$

vilket utläses "5-fakultet".

Allmänt gäller för naturliga tal n att n! (vilket utläses "n-fakultet") är definierat som

$$\begin{cases} n!=n\cdot (n-1)\cdot (n-2)\cdot \,...\, \cdot 3\cdot 2\cdot 1 & \text{ om } n\geq 1 \\ 0!=1 & \text{ om } n=0 \end{cases}$$

Detta innebär att t.ex. 5! tolkas på följande sätt:

$$5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$$

Vi kan se n-fakultet som en talföljd med elementen

$$1,\,2,\,6,\,24,\,120,\,...$$

för n ≥ 1.

Därigenom inser vi även att vi kan beräkna värdet på det n:te elementet i denna talföljd med hjälp av en rekursiv formel. Om vi t.ex. känner till värdet på 4! kan vi lätt beräkna värdet på 5!, om vi känner till värdet på 3! beräknar vi lätt värdet på 4!, och så vidare ner till 0! (värdet på 0! är ju per definition lika med 1):

$$5!=5\cdot 4!=$$

$$=5\cdot 4\cdot 3!=$$

$$=5\cdot 4\cdot 3\cdot 2!=$$

$$=5\cdot 4\cdot 3\cdot 2\cdot 1!=$$

$$=5\cdot 4\cdot 3\cdot 2\cdot 1\cdot 0!=$$

$$=5\cdot 4\cdot 3\cdot 2\cdot 1\cdot 1=$$

$$=120$$

Antal permutationer

I vårt tidigare exempel med böckerna på hyllplanet undersökte vi på hur många sätt vi kan ordna om samtliga dessa böcker.

Ett mer allmänt fall av detta är att vi har n böcker och vill välja ut k av dessa böcker, och undersöka på hur många olika sätt vi kan göra detta, om vi tar hänsyn till den ordning som de utvalda böckerna hamnar i.

Till exempel kan vi ha 5 böcker i hyllan och ska välja ut 2 av dessa böcker. Då kan vi välja den första boken på 5 olika sätt. Därefter finns det 4 böcker kvar att välja mellan. Alltså kan vi göra dessa båda val på så här många sätt (antal permutationer när 2 element av 5 element väljs):

$$5\cdot 4=20$$

Allmänt gäller att när vi väljer ut k element från en mängd bestående av n element och vi tar hänsyn till ordningen elementen hamnar i, vilket vi skriver P(n, k), kan antalet sätt att göra detta beräknas på följande sätt:

$$P(n,\,k)=n\cdot (n-1)\cdot\,...\,\cdot (n-k+1)$$

där 0 ≤ k ≤ n.

Detta kan vi förenkla till följande formel, med vars hjälp vi enkelt kan beräkna antalet permutationer då k element av n element väljs:

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

där 0 ≤ k ≤ n.

När vi till exempel beräknar antalet sätt att välja 2 böcker av 5 böcker och tar hänsyn till ordningen dessa böcker hamnar i, räknar vi alltså så här:

$$P(5,\,2)=\frac{5!}{(5-2)!}=\frac{5!}{3!}=\frac{5\cdot 4\cdot 3!}{3!}=5\cdot 4=20$$

När vi beräknar antalet permutationer finns det några specialfall som är bra att känna till: 

$$P(n,\,n)=n!$$

$$P(n,\,1)=n$$

$$P(n,\,0)=1$$

Det första specialfallet, att P(n, n) = n!, motsvarar situationen i vårt första exempel i det här avsnittet, där vi undersökte på hur många sätt vi kan ordna om 3 böcker (alltså 3 av 3 böcker väljs), vilket visade sig vara 3!.

Vi kan härleda antalet permutationer i det första specialfallet genom att använda den allmänna formeln, där vi låter k = n gälla:

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

Det andra specialfallet, att P(n, 1) = n, innebär att vi väljer ett element av n element. Att detta kan ske på n olika sätt kan framstå som självklart, men vi kan härleda att detta gäller genom att använda den allmänna formeln, där vi låter k = 1 gälla:

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

Det tredje specialfallet, att P(n, 0) = 1, innebär helt enkelt att det finns ett enda sätt att inte välja något element av n element (och det är att inte välja något element). Även detta kan vi härleda med hjälp av den allmänna formeln, där k = 0 gäller:

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

Tolka och beräkna följande antal permutationer:

1. P(7, 3)
   P(7, 3) tolkar vi som antalet permutationer när vi väljer 3 element av 7 element.
   Vi beräknar antalet permutationer så här:
   $$P(7,\,3)=\frac{7!}{(7-3)!}=\frac{7!}{4!}=$$
   $$=\frac{7\cdot 6\cdot 5\cdot 4!}{4!}=7\cdot 6\cdot 5=210$$
   Antalet permutationer då vi väljer 3 element av 7 element är alltså 210.
2. P(7, 7)
   P(7, 7) tolkar vi som antalet permutationer när vi väljer 7 element av 7 element, det vill säga samtliga sju element.
   Detta motsvarar det första specialfallet som vi tog upp ovan, så vi vet att antalet permutationer blir
   $$P(7,\,7)=7!=7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=5\,040$$
   Antalet permutationer då vi väljer 7 element av 7 element är alltså 5040.
3. P(7, 1)
   P(7, 1) tolkar vi som antalet permutationer när vi väljer ett element av 7 element.
   Detta motsvarar det andra specialfallet ovan, så vi vet att antalet permutationer är lika många som antalet element, det vill säga 7:
   $$P(7,\,1)=7$$
   Vill vi ändå beräkna P(7, 1) med den allmänna formeln för antalet permutationer, får vi följande:
   $$P(7,\,1)=\frac{7!}{(7-1)!}=\frac{7!}{6!}=\frac{7\cdot 6!}{6!}=7$$
   Antalet permutationer då vi väljer ett element av 7 element är alltså 7.
4. P(7, 0)
   P(7, 0) tolkar vi som antalet permutationer när vi väljer noll element av 7 element. Detta motsvarar det tredje specialfallet ovan, så vi vet att antalet permutationer är ett, eftersom vi kan välja noll element på bara ett enda sätt:
   $$P(7,\,0)=1$$
   Vill vi ändå beräkna P(7, 0) med den allmänna formeln för antalet permutationer, få vi följande:
   $$P(7,\,0)=\frac{7!}{(7-0)!}=\frac{7!}{7!}=1$$
   Antalet permutationer då vi väljer noll element av 7 element är 1.

I nästa avsnitt introducerar vi det närliggande begreppet kombination och går igenom hur vi beräknar antalet kombinationer.