gmat quantitative: permutations and combinations

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.

 

Listing

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:

  • Step 1

    Take the first item a and combine it with b. Then go down the list and combine it with c and d to get a total of three possibilities: ab, ac, ad.

  • Step 2

    Take the second item b and combine it with the rest of the list. Don’t combine it with a because you already did that in step 1. So you get: bc, bd

  • Step 3

    Keep doing the same thing for the next thing on the list, which is c. For c, there’s only one thing behind it on the list – d. So there’s only 1 possibility here: cd

  • Step 4

    Keep going until you get to the second last item. In this case, you already reached it in step 3. Tally up your choices: ab, ac, ad, bc, bd, cd

Tree Diagram

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:

If task A can be done in m ways and after Task A is complete, Task B can be done in n ways, then there are m*n ways of completing Task A then Task B.

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!

 

Formulas

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.

Permuting

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)

Combining

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.

Example 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.

Example 2

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.

Example 3

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.