8.02 Permutations

A permutation is each of the possible ways that a group of objects could be selected and arranged, when the order of the object is important.  For example, If I have a red dot, blue dot and green dot; then I could choose any two of them and end up with the following options.  

We can say there are $6$6 permutations. For small sets like the one above, it's quite simple to write down all the choices and add them up.  But for larger sets, like imagine we had $8$8 colours and wanted to see how many different combinations of $5$5 colours there are - we need a more efficient method of counting.  

You'll notice also that in the example above with coloured spots, that the answer of red and green spot was different to the answer of a green and red spot.  We say that for a permutation, that the order is important.  That is, that we call the red and green different to a green and a red.   

Diagramatic calculations

Using a diagram can help us work out the number of permutations a set of objects have. 

For example, consider the set of objects of the letters $A,B,C,D$A,B,C,D and $E$E.  and we want to see how many different sets of $3$3 letters we can have. 

A diagramatic calculation starts with drawing boxes (or circles, or triangles, or any other shape you can write a number inside of), where the number of the boxes is equal to the number of objects we are selecting.  In this case we are selecting $3$3 letters each time, so we have $3$3 boxes.

Inside the first box, we write down how many possible choices we have for this box.  We have $5$5 letters to choose from, so we have $5$5 options.  Either $A,B,C,D$A,B,C,D or $E$E.

Inside the second box, we write down how many possible choices we have for this box.  Because we had $5$5 to start with, but will have selected one already, there are $4$4 options left for this next box. 

Finally, inside the third box.  How many possible letters would we have left to pick from.  Only $3$3. 

To calculate how many possible options we have we multiply these together.

So there are $60$60 possible permutations for selecting $3$3 objects from the $5$5.  

 

Formula for permutations

Consider the example of finding how many $3$3 digit numbers can be formed using the $9$9 digits $1,2,3,4,5,6,7,8,9$1,2,3,4,5,6,7,8,9, given that the digits cannot be used more than once? 

The answer is $504$504 numbers.

The explanation is quite simple.  We have $9$9 choices for the left most digit of the $3$3-digit number. When that choice is made, we then have $8$8 choices for the middle digit. The right most digit can be filled by one of the remaining $7$7 digits,  (just like in our diagramatic calculation above).

If you think about it, this means that there must be $9\times8\times7=504$9×8×7=504 possible $3$3-digit numbers.

Mathematically we say that there are $P\left(9,3\right)$P(9,3) size $3$3 arrangements of the $9$9 digits possible.

 

As another example, suppose we have $9$9 people lining up for a group photo. The number of arrangements of the $9$9 people in the $9$9 spots available is simply $P\left(9,9\right)$P(9,9) or $9!$9! and this evaluates to $362880$362880 possible line-ups!   

The formula for a permutation calculation is 

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

Where $n$n is the number of objects we have to choose from, and $r$r is the number of objects we are selecting. Remember that the ! in maths denotes a factorial. 

 

The notation

$P\left(n,r\right)$P(n,r)

The symbol $P\left(n,r\right)$P(n,r) with $r\le n$r≤n, is a short hand notation for the product $n\times\left(n-1\right)\times\left(n-2\right)\times...\times\left(n-r+1\right)$n×(n−1)×(n−2)×...×(n−r+1). It can be thought of as a product similar to $n!$n! , but only including $r$r of the decreasing factors.

For example, using the above formula, $P\left(8,3\right)$P(8,3) means $8\times7\times6=336$8×7×6=336 - an expression that counts only $3$3 of the decreasing factors. Again, $P\left(12,5\right)=12\times11\times10\times9\times8=95040$P(12,5)=12×11×10×9×8=95040 and $P\left(5,1\right)=5$P(5,1)=5. We can also write that $n!=P\left(n,n\right)$n!=P(n,n). 

By definition, $P\left(n,0\right)=1$P(n,0)=1, so $P\left(8,0\right)=1$P(8,0)=1, $P\left(12,0\right)=1$P(12,0)=1 etc.

The letter $P$P in the notation doesn't stand for partial, although in some sense we a partially evaluating $n!$n!. The letter $P$P stands for permutation which means an arrangement of things. 

Practice questions

QUESTION 1

QUESTION 2