GMAT Quantitative: Permutations and Combinations
When dealing with permutations and combinations, you are essentially trying to find the number of different outcomes given a set of items and a number of restrictions. The difference between permutation and combination merely depends on whether the order matters. Let me illustrate with an example. Suppose you have three food items, apples, bananas and carrots. If you were asked to only pick two of them, how many possibilities are there? If you got 3, that’s the right answer. You have apples & bananas, apples & carrots and bananas and carrots. This is combination. If I told you however, that the order in which you eat the food matters, then you have more possibilities, because instead of just apples & bananas, you have to consider bananas & apples too. The latter is permutation.
What I did earlier, when I listed out the 3 choices is called, not surprisingly, listing. But there is a method to listing to ensure that you don’t leave any possibilities out. Everyone tends to have his or her own method, let me share mine. If I have four items – a, b, c and d – and I’m supposed to choose 2:
If you noticed, listing is a good method for figuring out combinations. The Tree Diagram is a graphical method that helps you with permutation. Using the previous example of 4 items, here’s the tree diagram that illustrates the number of ways of permuting items.
If you look at the last line of the tree diagram and count the number of boxes, you will see that there are 12 possible ways to permute 2 items out of 4. Each item can be combined with 3 other things. Another way of seeing this is that you have two spaces you need to fill ___ and ___. Looking at the first space, you have 4 possible items you could place there. Looking at the second space, you have 3 possible items you could place there, since you have already put 1 item in the first space. So there are 4 x 3 = 12 ordered possibilities.
Fundamental Counting Principle
The spaces-and-number-of-options-to-fill-that-space method of thinking is essentially the fundamental counting principle. The principle states that:
Let’s see if you understand the principle with a quick example.
How many different ways are there are arranging these letters: T A N G O.
Did you get 120?
Imagine five spaces ___ ___ ___ ___ ___
You have 5 possible letters to put in the first space, and when that’s done, you have 4 possible letters to put in the second space, 3 letters for the third space and so on.
So the answer is 5*4*3*2*1 or 120!
Once you’ve figured out whether to use permutation or combination, there is actually very little work to be done if you know the formulas for permutation and combination or if you know where the function is hidden on your calculator.
As mentioned before, permutation is used when the order matters and combination when you just want to choose, but not order, the items. Let’s dive straight into the formulas then go through a few examples.
The number of ways of permuting r objects out of n objects is given by
n P r =n!/(n-r)! where n! = n * (n-1) * (n-2) * … * (2) * (1)
The number of ways of combining r objects out of n objects is given by
n C r = n!/r!(n-r)!
Note that 0! is defined as 1.
How many ways are there of arranging 4 letters out of the following F R I E N D?
FRIEND has 6 different letters, and since the order of letters matter, you know you have to use the permutation formula. Applying the formula directly, the answer is given by
6 P 4 = 6!/(6-4)! – 6!/2! – 360
You can double-check this by using the fundamental counting principle that we covered in Part I. Drawing a tree diagram will also work, but it might get a little messy as the tree gets bigger and bigger.
If there are 3 entrees and 5 desserts, how many ways are there of choosing 1 entrée and 2 desserts? Note, that the question does not say anything about the order in which the entrees and desserts are eaten, so you know to use the combination principle. Because you are choosing entrees and desserts separately, you have to apply the combination formula twice.
First, to choose 1 entrée out of 3, we apply the formula 3 C 1 = 3!/1!(3-1)! – 3!/1!2! – 3
Next, to choose 2 desserts out of 5, we apply the formula 5 C 2 = 5!/2!(5-2)! – 5!/2!3! – 10
Then because for each entrée, there are 10 possible 2-dessert combinations and there are 3 ways of choosing 1 entrée, to get the total number of possibilities, we take 3*10 = 30.
What if the question throws you a curveball and asks you to permute something that has a repeated item. For example, how many ways are there of arranging the letters A G H A S T?
The ‘A’ is repeated twice so first you pretend that the letters are distinct and find the number of possibilities. Then divide that value by 2! because ‘A’ is repeated twice.
AGHAST has 6 letters, and if we permute all the letters, we get 6!
Because A is repeated, we divide 6! by 2! to get the answer 360
Supposing you are asked to permute only 4 out of 6 of the letters from AGHAST, then you would do 6 P 4 as per normal, and divide that answer by 2! since A is repeated. The answer should be 180.