Add Maths>Permutations and Combinations
Introduction
This topic is concerned with the number of different ways a group of n items can be grouped into r spaces. It is a topic that is greatly influenced by probability and requires thinking and a large amount of application. Permutations are concerned with the order the objects are in but Combinations are not.
Background knowledge
|
Factorials
A factorial, written as: n! (n factorial), is the multiplication of n by all the numbers before it till 1 (for positive integers/natural numbers). For example, 5! = 5*4*3*2*1 = 120.
As 4! is 4*3*2*1, 5! = 5*4! (and in the same way 5! = 5*4*3! etc.).
Example 1,
How many arrangements of 3 books are possible in a bookshelf?
3! = 3*2*1*0! = 6
But why?
As 4! is 4*3*2*1, 5! = 5*4! (and in the same way 5! = 5*4*3! etc.).
- Therefore n! = n*(n-1)!
- It is also important to know 0! = 1 (which means 5! also equals 5*4*3*2*1*0! which sustains the above rule.)
Example 1,
How many arrangements of 3 books are possible in a bookshelf?
3! = 3*2*1*0! = 6
But why?
- Imagine there are 3 slots in a shelf
- The first slot can have any one of 3 books
- For each book, the next slot can have anyone of the remaining 2
- And for the last slot, there is only 1 book remaining in each of the 2 scenarios
- Each time each is used, it means the event has a number of events associated with it as well so they are multiplied:
- 3*2*1 = 3! = 6
Example 2
On a football pitch, 11 players on each team stand in a line. The captain always stands at the front but the other players can be in any order. How many possible arrangements are there for each team?
Example 3
In the same game, the goalkeeper stands immediately behind the captain. How many arrangements are there now?
If the goalkeeper and captain are interchangeable, how many possible arrangements are there?
Below is a useful thing you can do with factorials that helps with permutations and combinations.
On a football pitch, 11 players on each team stand in a line. The captain always stands at the front but the other players can be in any order. How many possible arrangements are there for each team?
- The captain will always be at the start so there is only 1 possibility for the first slot
- The other 10 players can be in 10! arrangements (which equals 3,628,800)
- 1 * 3,628,800 = 3,628,800
Example 3
In the same game, the goalkeeper stands immediately behind the captain. How many arrangements are there now?
- The captain will always be at the start so there is only 1 possibility for the first slot
- The goalkeeper will always be second so there is only 1 possibility for the second slot
- The other 9 players can be in 9! arrangements (362,880)
- 1*1*362,880 = 362,880
If the goalkeeper and captain are interchangeable, how many possible arrangements are there?
- The captain and the goalkeeper (2 people) can be in 2! (=2) arrangements between them
- The arrangements of the captain and the goalkeeper must be at the front and so separate from the rest
- The other 9 players can be in 9! (362,880) arrangements
- 2*362880 = 725,760
Below is a useful thing you can do with factorials that helps with permutations and combinations.
Permutations
A permutation is an arrangement of objects which have been put in a specific order. For example, here are all the permutations of A, B and C...
|
n = The number of objects that can be arranged
r = The number of objects that are arranged (number of slots) nPr = The number of permutations of n objects in r slots |
Note: The Factorial questions in the above section where you are asked for arrangements, were asking for permutations.
Example
In a race of 5 athletes, how many arrangements of the first three places are there?
5P3 = 60
But why?
Example
In a race of 5 athletes, how many arrangements of the first three places are there?
5P3 = 60
But why?
- Again, imagine there are three slots that we care about for this question (first, second and third position)
- For the first slot, there are 5 athletes who can possibly come first
- For each 5 that comes first, there are 4 others that can come second
- For each of those 4, there are 3 others who can come third
- Each time each is used, it means the event has a number of events associated with it as well so they are multiplied:
- 5*4*3 = 60
- The formula comes from the thought process of removing the parts you don't care about (4th and 5th) from the total number of permutations
Combinations
A combination is a selection of objects and the order doesn't matter. For example, here are all the combinations of A, B and C involving all 3 letters...
- ABC (which is the same as CAB or BCA or ACB etc.)
Example
There are 5 candidates to join a maths team but only 3 can be in a team, how many different selections of the team are there?
5C3 = 10
But why?
There are 5 candidates to join a maths team but only 3 can be in a team, how many different selections of the team are there?
5C3 = 10
But why?
- Imagine there are three slots we care about.
- For the first, there are 5 possible candidates then for each there are 4 in the second slot and for each 3 in the third.
- This results in 5*4*3 = 60 (the number of permutations)
- However, permutations include repeated combinations as permutations consider the order as well
- For each combination, there are 3! permutations because the first selected student (A) can be in any one of 3 positions, the second (B) can be in any of the remaining 2 and the third (C) will be in the remaining 1 (this is written out below): 3*2*1 = 3! = 6
- As there are 3! permutations for each combination, the number of permutations needs to be divided by 3! to get the number of combinations
- Hence, nCr = nPr/r! which is equivalent to the equation for nCr
Answering Questions
The main difficulty of this topic is applying the knowledge to the questions so here are some tips.
- Break down the question into parts you can understand so you know what is going on
- Deduce whether they're asking for permutations, combinations or both by looking for keywords
- Think through the scenario and decide how to treat each feature (eg. do two objects get arranged as if they are 1)