Permutationer

En permutation är ett specialfall av ordnat urval, där vi har en mängd med n element och vill veta antalet olika ordnade n-tiplar.

Formeln

Vi repeterar ordnat urval. Vi tar siffrorna {1, 2, 3, 4, 5}. Hur många tresiffriga tal kan vi bilda av dem om ingen siffra får upprepas? Det är ett typiskt exempel på ordnat urval, som kan lösas med den kända formeln

$$\frac{n!}{(n-k)!}=\frac{5!}{(5-3)!}=60.$$

Hur många femsiffriga tal skulle vi kunna bilda?

$$\frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120.$$

Vi kan notera att om vi har en mängd med fem element och söker antalet olika femtiplar, så är resultatet lika med 5!. Det kan vi generalisera och säga att om vi har en mängd med n element, så finns det totalt n! olika n-tiplar. Därmed kommer vi till begreppet permutation.

Vad är en permutation

Om vi har en mängd M med storleken n, så är en permutation en godtycklig n-tipel av element ur mängden M, där inget element får upprepas. Exempel: om vi har mängden M = {a, b, c, d}, så är till exempel (a, b, d, c) eller (d, b, a, c) permutationer. Antalet olika permutationer är lika med antalet ordnade urval av n element ur n, alltså

$$n!$$

Lösta exempel

1. Du har sex böcker och vill ställa dem på en hylla i någon ordning. Hur många olika ordningar finns det? Vi har sex böcker och permuterar alltid alla böckerna, så resultatet är 6! = 720.

2. Till dina 6 svenska böcker från förra exemplet har det tillkommit 4 böcker på engelska. På hur många olika sätt kan du ställa de här 10 böckerna på hyllan, om du vill ha alla svenska böcker för sig och alla engelska böcker för sig?

   Vilka möjligheter har vi att ställa böckerna? Vi kan först ställa de sex svenska böckerna och sedan de fyra engelska, eller tvärtom – först de fyra engelska och sedan de sex svenska. Det finns 6! sätt att ställa de svenska böckerna och 4! sätt att ställa de engelska böckerna. Vi använder multiplikationsprincipen och multiplicerar de här resultaten: 6! · 4! = 17 280. Eftersom det finns två möjligheter att ställa böckerna (först de svenska och sedan de engelska, och tvärtom), multiplicerar vi dessutom det här talet med två. Det totala resultatet är 17 280 · 2 = 34 560.