Permutations and Combinations
In how many ways can the people Anna, Babs, Colin and Dave be arranged?
We'll start with having Anna first:
ABCD | ABDC | ACBD | ACDB | ADBC | ADCB |
As there are 6 arrangements with Anna first, there must also be 6 arrangements with Babs first. Similarly, there will be 6 arrangements for Colin and Dave first.
Hence there are 24 arrangements altogether. These 24 different arrangements are called permutations.
Another way of thinking about this is to say we can choose
- the first person in 4 ways (as there are 4 people to choose from)
- the second person in 3 ways (as there are now only 3 people to choose from)
- the third person in 2 ways (as there are now only 2 people to choose from)
- the last person in 1 way (as there is now only 1 person to choose from)
So the number of arrangements = 4 × 3 × 2 × 1 = 24 ways
Another way of showing this is: 4 × 3 × 2 × 1 = 4! (called 4 factorial )
In general, the number of ways of arranging n distinct (different) objects is:
n! (n factorial)
n! = n × (n × 1) × (n × 2) × ... × 2 × 1
For Example:
The number of ways of arranging 7 people standing in a line is:
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
Your calculator will have a button that will calculate factorials for you. Try it for the following factorials:
What happens if not all the objects are distinct?
The number of ways of arranging n objects of which r are the same is
In addition to this, the number of ways of arranging n objects of p of one type are alike, q of a second type are alike, r of a third type are alike, etc.
This is given by:
For Example:
In how many ways can the letters of the word statistics be arranged?
There are 10 letters in 'statistics' and: | S occurs 3 times |
T occurs 3 times | |
I occurs twice |
Hence the number of ways:
...Still a very large number of ways.
Suppose there were 8 swimmers in a 50m butterfly race.
In how many different ways can the first 3 places be filled?
As before:
- We can choose the first swimmer in 8 ways (as there are 8 swimmers to choose from)
- The second swimmer in 7 ways (as there are now only 7 swimmers to choose from)
- The third swimmer in 6 ways (as there are now only 6 swimmers to choose from)
So the number of permutations = 8 × 7 × 6 = 336
Rewriting this result using the factorial method will give us a handy formula for all questions of this type:
Note: 8 − 3 = 5, which is the number of swimmers subtracted by the number of places to be filled.
Hopefully from this we can see the following general rule:
The number of permutations of r objects from n is written as ^{n}p_{r}
We write:
Handy hint: |
---|
Nearly all permutation questions involve putting things in order from a line where the order matters. For example ABC is a different permutation to ACB. |
Suppose that we wish to choose r objects from n, but the order in which the objects are arranged does not matter. Such a choice is called a combination.
ABC would be the same combination as ACB as they include all the same letters.
The number of combinations of r objects from n, distinct objects can be written in 2 ways:
Example:
Again lets take 8 Olympic swimmers. However, this time we want to select a team of 3.
In how many ways can this be done?
We can clearly see that this time, the order in which the swimmers are picked does not matter.
For example, picking swimmers 1, 4 and 7 will give us exactly the same team (and combination) as picking swimmers 4, 7 and 1. This means we have a combinations problem.
We are choosing 3 from 8 therefore:
Note: That the denominator adds to give you the numerator. This is no coincidence and will always happen. Use this to check your workings.
Handy hint: |
---|
Nearly all combination questions involve 'picking' or 'choosing' a number of objects from a larger amount of objects. |
A few handy results for you: