Permutations and Combinations

Lesson

A permutation is each of the possible ways that a group of objects could be selected and arranged. 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.

The idea of counting how many possible different combinations there are is part of a mathematical topic called Counting Techniques. 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 colours and wanted to see how many different combinations of 5 colours there are - we need a more efficient method of counting.

You'll notice also that in my 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.

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.

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.

$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.

If there are $5$5 swimmers in a race, in how many different orders can they finish (assuming there are no ties)?

How many different ways can the letters of the word 'SHELF' be arranged?

Use permutations and combinations