Permutation and Combination
As part of a refresher on simple probabilities, I will try to explain the differences between Permutation and Combination and when to use them.
The simple explanation is order matters for permutation but does not for combination.
Permutation — Order matters
Combination — Order doesn't matter
For example, think of picking toppings for a pizza. Mushrooms, onions, and sausage compared to onions, sausage, and mushroom are the same. This is a combination, the order doesn’t matter since all the chosen toppings are going to be put on the pizza.
An example of a permutation would be picking a passcode. 1234 and 2413 are different codes and can’t be interchanged. Strangely enough, a combination lock uses a permutation code where order does matter.
An easy way to remember which one is which is by thinking “Permutation ….. Position”.
Permutation with repetition
This is the easiest to calculate
When we have a number of choices to make for each position we have n number of choices each time. Therefore the number of possible choices is simply
n x n … (r times) = n^r
Say you have to pick a 4 digit passcode. The number of possible choices in each position is 10(0–9). So the number of possible 4 digit passcode is..
10^4 = 10000
Permutation without repetition
In this case, the number of choices is reduced each time. An example of this would be how many different ways can five different books be arranged on a shelf. The answer is
5 x 4 x 3 x 2 x 1 = 5! = 120 different ways
If we only want to choose three books out of five to arrange on the shelf it would be
5 x 4 x 3 = 60 different ways to arrange the books
The formula for this is n!/(n-r)!
Where n = the number of choices and r = the number of positions.
For combinations, there are also two types where repetition is not allowed and one where repetition is allowed.
Combinations without Repetition
This is similar to how lotteries work where the order of numbers doesn’t matter, if the numbers are the same, you have a winning ticket.
The formula for combinations without repetition is
An example would be choosing 3 numbers from 0 to 9.
The permutation for this would
10!/(10–3)! = 720
This formula counts 123 and 231 as two different entries. We have to get rid of all the combinations where the chosen number are the same.
We do this by dividing the permutation by the number of possible ways the chosen number can be arranged.
n!/(r!(n-r)!) = 10!/(3!(10–3)!) = 720/3! = 120
Permutation with repetition
An example of permutation with repetition would be picking three scoops of ice creams from five different flavors.
The formula for this is
(r + n − 1)!/r!(n − 1)!
So for example it would be
(3+5–1)!/3!(5–1)! = 7!/3!*4! = 5040/144 = 35
There are 35 combinations of ice cream scoops you could pick.