Combinations and Permutations ask you to count the number of ways we can choose a group or order a group. Most GMAT test takers tend to overly focus on combinations and permutations. The truth is these questions only occur if you are scoring in the 700 range.
Permutations
Example:
If we toss two dice, how many different possible outcomes are there?
Solution:
There are typically two ways to solve this type of problem. The long way and the short way.
First way: Write out all the outcomes
| 11 | 12 | 13 | 14 | 15 | 16 |
| 21 | 22 | 23 | 24 | 25 | 26 |
| 31 | 32 | 33 | 34 | 35 | 36 |
| 41 | 42 | 43 | 44 | 45 | 46 |
| 51 | 52 | 53 | 54 | 55 | 56 |
| 61 | 62 | 63 | 64 | 65 | 66 |
Sometimes it is not possible to write out all outcomes.
The short way is to use the fundamental counting principle, which says if I have a set of items and another set of items, the number of choices is
number of possible outcome = n x k
Example:
We have the numbers 0 through 9 written on slips of paper in a hat. We pick a number slip at random and are asked to look at it. Then we put the slip back in the hat. If we are asked to do this three times, how many possible outcomes are there.
Solution:
Here are some cases of the three numbers we can pull out.
5 5 5
1 2 7
3 3 3
We can use a schematic way to represent the problem.
We have to fill 3 places with the number on the slips of paper.
__ __ __
In the first slot we can have 10 numbers 0 … 9. We have 10 options.
10 __ __
In the second slot, we also have 10 options because after we take a number out we put it back in.
10 10 __
Again in the third slot we have 10 options.
10 10 10
So by the fundamental counting principle we have
10 x 10 x 10 = 1000 outcomes
These questions are called permutations with returns. In these questions order is important.
1 2 3
is different from
3 2 1
Example:
How many 3 digit numbers are there?
Solution:
We can solve this using the formula we learned earlier in our discussion of consecutive numbers.
last number - first number + 1
999 -100 + 1 = 900
Now lets use permutations to solve this question.
We have 3 slots.
__ __ __
In the first slot we can put the numbers 1 .. 9. It doesn’t make sense to put zero here. So we have 9 numbers. In the second slot and third slot we can put the numbers 0 … 9. That’s 10 numbers.
9 10 10
So we have: 9 x 10 x 10 = 900
Example:
How many 3 digit numbers are there that are divisible by 5?
Solution:
Again we have 3 slots.
__ __ __
In the first slot we can put the numbers 1 .. 9. It doesn’t make sense to put zero here. So we have 9 numbers. In the second slot we can put the numbers 0 … 9. In the third slot, we know for a number to be divisible by it must end in a 5 or a 0. That’s two possibilities.
9 10 2
So we have: 9 x 10 x 2 = 180
Example:
If there are 5 boys and they must sit down on 5 seats, hwy many ways can they sit down?
Solution:
We have 5 seats so we have 5 slots.
__ __ __ __ __
In the first seat any of the 5 children can sit down. So we have 5 options.
5 __ __ __ __
Once a child sits down we can’t move him so there are only 4 children that can sit in the second seat. Once he sits down only 3 children can sit in the third seat. Once he sits down only 2 children can sit in the fourth seat. Once he sits down 1 boy can sit in the last seat.
5 4 3 2 1
So we have: 5 x 4 x 3 x 2 x 1 = 120
We call this 5 factorial or 5!.
7! = 7 x 6 x 5 x 4 x 3 x 2 x 1
Example:
| 6! | 6 x 5 x 4 x 3 x 2 x 1 | 6 x 5 x 4 | ||
| 2! | = | 2 x 1 | = |
Example:
If there are 8 children and only 5 seats, how many different ways can the children sit down?
Solution:
Not everybody will be able to get a seat. Again we draw the situation.
__ __ __ __ __
8 children can sit in the first seat. 7 children in the second seat . . . and so forth.
8 7 6 5 4
So we have: 8 x 7 x 6 x 5 x 4 children
This is exactly the same as:
| 8! | 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 | 8 x 7 x 6 x 5 x 4 | |
| 3! = | 3 x 2 x 1 | = |
If you think about it, this make sense. 8! counts all the ways, even the ways that the children that don’t have a seat can be ordered. We eliminate this order by dividing by 3!.
In general we have:
| n! |
| (n - k)! |
Example:
If there are 7 children and 10 seats, how many different ways can the children sit down?
Solution:
If we tried to solve this problem the same way it might be difficult.
We can look at this problem in reverse.
We draw 7 slots.
__ __ __ __ __ __ __
The first child has 10 options. The second child has 9 options and so forth.
10 9 8 7 6 5 4
So we have: 10 x 9 x 8 x 7 x 6 x 5 x 4 children
Example:
We have 5 people and 5 seats, but 2 are a couple and must sit together. How many ways can this be done?
Solution:
We draw 5 slots.
__ __ __ __ __
If two people must sit together we treat them as a group.
Say we have 5 people
A B C D E
Assume A and B are a couple. We don’t call them A and B we call them a couple.
Couple C D E
How many ways can we arrange this group of 4?
4!
Then we look in the group Couple.
How many ways can we arrange the 2 people in the couple?
2!
So we have: 4!2! = 48 ways
Example:
We have 5 people and 5 seats, but 3 are best friends and must sit together. How many ways can this be done?
Solution:
A B C D E
Group D E
Possible arrangements:3!
Now look at the group.How many ways can we arrange the people in the group?
3!
So the answer is:3!3! = 36
Combinations
Thus far when we are counting the order has mattered. We use combinations when order does not matter.
Example:
We have 8 baseball players, and we have to choose a 5 player team. How many different teams can we choose?
Solution:
Order does not matter. Here we are picking, choosing, or selecting.
When order mattered we had.
8 7 6 5 4
or
| 8! |
| 3! |
We have to eliminate the duplicate orders that consist of the same team. To get rid of the duplicates we divide by 5!.
So the answer is:
| choose 5|8 | 8! | |
| = | 3!5! | |
In general if we want to choose a group k out of n the formula is:
| n! |
| (n - k)!k! |
We divide by k! to get rid of the orders that are duplicates.
Example:
In how many arrangements can a teacher seat 3 girls and 3 boys in a row of 6 if the boys are to have the first, third, or fifth seats?
a)6
b)9
c)12
d)36
e)720
Solution:
We first draw the seats as a scheme:
__ __ __ __ __ __
It’s easy to look at each group separately. Let’s look at the girls first.
We are told the the boys must be in seat 1 , 3 , and 5. This means the girls have to be in seats 2 , 4, and 6
B _ B _ B _
In the first open seat 3 girls can sit down. In the second seat 2 girls can sit down. In the third 1 can sit down.
B 3 B 2 B 1
So the girls can sit down in 3! ways.
Now let’s look at the boys.
_ G _ G _ G
In the first open seat 3 boys can sit down. In the second seat 2 boys can sit down. In the third 1 can sit down.
3 G 2 G 1 G
So the boys can sit down in 3! ways.
Together we have:
3!3! = 36
The correct answer is D.
(46)
(28)
(2)