Topics‎ > ‎

Permutations and Combinations

To solve permutation/combination problems, the key thing to know is when it is a permutation vs. a combination.

Permutations : number of ways you can arrange k objects out of n objects where the order matters.
Combinations : number of ways to choose k objects from n objects where order does not matter.


Permutations

Problem: Let’s say we have 6 players in a game and they can win Gold, Silver and Bronze medals. List the number of possibilities for all the winners.

Well, since each of the medals is different, the order matters, i.e. if the three winners are A, B and C, we can have A->Gold, B->silver, C->bronze or B->Gold, A->Silver, C->Bronze, or C->Gold, B->Silver, A->Bronze and so on.






Let's say we first pick the Gold medal winner, then the silver medal winner and then the bronze medal winner.
As shown above, initially, any of the 6 players can get the gold medal. Once we pick the Gold medal winner, now we have a choice among 5 players for the Silver medal.
After the Silver medal winner is picked, we are left with just 4 players to choose from for Bronze medal.

Then total number of options we have:  6 X 5 X 4 = 120.

Or, we can use the formula:
   

Why is this the same as the calculation we did?

Let’s see, we know the factorial of 6 is: 6! = 6 X 5 X 4 X 3 X 2 X 1
But we only want 6 X 5 X 4. How can we “stop” the factorial at 4?
So basically, we just want to get rid of 3 X 2 X 1. What’s another name for this? 3!

So, if we do 6! / 3! we get: (6 X 5 X 4 X 3 X 2 X 1) / (3 X 2 X 1) 
Cancelling common terms, we get:
6 X 5 X 4

And why did we use the number 3 in the denominator? Because it was left over after we picked 3 medals from 6. So, a better way to write this would be: 6! / (6 - 3)!. Say if we had 7 players, the number of ways to pick the 3 medal winners would be 7! / (7 - 3)!. Or if we had 8 players, it would be 8! / (8 - 3)!.

So, generalizing this, we get the fancy permutations formula:
If you have n items and want to find the number of ways k items can be ordered, just use this formula:

Tip: It’s important to understand why we use this formula, but to do these calculations fast, it is helpful to know the factorials of the first 10 numbers, so we can just plug in these values in the formula.

It is also helpful to know that P(n, n) is just n! since 0! is 1. You should memorize the factorials of 1 to 10 to be able to do fast calculations.

nn!
01
11
22
36
424
5120
6720
75040



Combinations

In combinations order does not matter. Let’s say in the above problem, a coach needs to pick 3 people from the team to represent the school.

How many ways can they pick 3 players from 8?

Well, in this case, the order in which we pick people doesn’t matter, so a team of ABC is the same as BAC or CAB, etc.

So if we used the permutations formula to pick 3 players, we would have some repetitions, e.g. ABC, BAC, CAB, etc.
Exactly how many repetitions will we have?
That would be just the number of ways we can rearrange 3 people.
And what is that? Well, we have 3 choices for the first person, 2 for the second, and only 1 for the last. So we have 3 X 2 X 1 ways to re-arrange 3 people. In other words, number of ways you can rearrange 3 items is just 3!

Or, in general, if you have N people and you want to know how many arrangements there are for all of them, it’s just N factorial or N!

So, basically there are 3! or 6 variations for every choice we pick. If we want to figure out how many combinations we have, we just get all the permutations and divide that by all the number of repetitions we have for each choice. In our case, we get 120 permutations (from above), and we divide by the 6 redundancies for each permutation and get 120/6 = 20.

Another way to find the combinations is to create a tree as shown below. Each path is a different combination of letters and if you count all the paths, it adds up to 20.



However, in order to do these calculations quickly, it is helpful to know the formulas.

The general formula for combinations is:
which means “Find all the ways to pick k objects from n, and divide by the k! variants”. 
Writing this out, we get our combination formula, or the number of ways to combine k items from a set of n:

Exercises:

1. There are 6 points, A, B, C, D, E, F on the circumference of a circle.
  a) How many distict lines can be formed by joining any 2 points?
  b) how many triangles can be formed?
  c) how many distinct quadrilaterals can be formed?

2. A license plate has two letters and then four numbers in it.
How many plates can be made without duplicating the letters and numbers?
Comments