Permutations and Combinations for CAT

Permutations and combinations are tools for counting things. They play a huge role in probability and other areas of discrete mathematics. And they are important for the Common Admissions Test (CAT)! In this review article, we’ll explore permutations and combinations and provide some practice using them.

Permutations and combinations are just one small part of the CAT Quantitative section. For more tips, check out How to Study for the CAT Quantitative Ability Section.

What are Permutations and Combinations?

Technically, a permutation is a way of rearranging items in a set, while a combination is a particular choice of some elements from a set. However, we see these concepts in problems, we usually mean the associated formulas and methods for counting items from a set.

Permutations

A permutation is an arrangement of some number of distinct items (no repetitions) in which the order matters.

Suppose that you and your two closest friends decide to line up for a selfie. In how many ways can this be done?

Bill Nye, Barack Obama, and Neil DeGrasse Tyson

President Barack Obama poses for a selfie with Bill Nye, left, and Neil DeGrasse Tyson in the Blue Room prior to the White House Student Film Festival, Feb. 28, 2014. (Official White House Photo by Pete Souza)

For the sake of brevity, let’s name the three people A, B, and C. First of all, one of the three, A, B, or C, can choose to be on the left. That leaves two choices for the middle spot. Finally, once the first two people have been placed, the final person must go on the right.

Therefore, there are (3 choices) × (2 choices) × (1 choice) = 6 total permutations.

This generalizes to any number of items. The number of permutations of n distinct items is exactly n! (“n factorial”), where

n factorial

Notice that 0! = 1. At first this may seem strange, but think about it like this: How many ways are there to arrange zero objects? Exactly one way!

Permutations of subsets

Suppose ten people enter a race. How many possible arrangements of first, second, and third place winners?

It sounds like a permutation, but this time we don’t have to arrange all ten runners — just the top three. Nevertheless, the process starts the same.

  • The first place winner must be one of the 10 runners (10 choices).
  • After deciding first place, there are 9 runners to choose from to establish second place (9 choices).
  • Once first and second are chosen, now there are 8 runners to pick from for third (8 choices).

Therefore, there are a total of 10 × 9 × 8 = 720 possible arrangements.

In general, the number of permutations of r items from a set of n distinct elements is denoted nPr. The formula is:

Formula for permutation numbers

Combinations

Combinations are much like permutations, except that the order does not matter. For example, we might ask how many combinations of three runners could be chosen out of the 10 entrants. Here we do not order the runners by first, second, or third places.

The key here is to start with a permutation number, and then divide by the number of ways to rearrange the smaller set of elements. In our example, we would have:

10P3 / 3! = 720 / 6 = 120.

Using the notation nPr for the number of combinations of r elements from a set of n distinct elements, we have the following equivalent formulas:

Formulas for nCr (combination numbers)

Permutation with Repetition

The methods developed above generalize to rearrangements of sets with repetition of any numbers of items. Suppose a set has n items, and r1 of them are of one type, r2 of another type, r3 of another type, and so on. How many ways are there to make an arrangement of this set?

The key is to first find the total number of permutations of the entire set (n!). Then (just as in a combination), divide off by the number of rearrangements of any items that are considered the same. Thus, the total number will be:

permutation_with_repetition formula

Practice Problems

Ok, now that you know the basics, let’s explore how the concepts of permutations and combinations might show up on the CAT!

Problem 1

How many distinct ways can the letters of the word MISSISSIPPI be rearranged?

Solution

This is a permutation with repetition. There are n = 11 letters total, with the following repetitions:

  • Four I’s: r1 = 4
  • Four S’s: r2 = 4
  • Two P’s: r3 = 2

(We could also include r4 = 1 for the single M, but it does not affect the value.)

As you work out the number, look for cancellations to make your life easier.

Example1_solution - permutations and combinations

Problem 2

In how many ways can 8 identical balls be placed into three bins? Each bin may contain any number of the balls, including none at all.

Solution

The “ball-and-bin” problems are fairly common on the CAT, showing up in a variety of ways. Fortunately, there’s a standard trick for this. Use a symbol (like |) to separate the 8 balls. For example, here’s one way to fill the bins:

* * | * * * * * | *    (2, 5, and 1, respectively, in each bin)

Now we answer the equivalent question: Of the 10 symbols (8 balls plus 2 dividers), which two will be chosen as the dividers? That’s a combination number:

10C2 = (10)(9)/(2) = 45.

Problem 3

How many 5-digit numbers whose only digits are 4’s and 3’s are multiples of 12?

Solution

This is an interesting combination (no pun intended!) of number theory and counting.

A whole number is a multiple of 12 if and only if it is a multiple of 3 and a multiple of 4. Multiples of 3 have digits that add to a multiple of 3. On the other hand, the last two digits of every multiple of 4 must be a multiple of 4.

So we need a string of five 4’s and 3’s that

  1. add up to a multiple of 3, and
  2. whose last two digits are a multiple of 4.

To get a sum of a multiple of three, there are only a few possibilities:

  1. All 3’s
  2. Two 3’s and three 4’s

But the first scenario does not permit a multiple of 4 in the last two digits. That leaves scenario 2. In fact, the only possibility is that the final two numbers are 44.

So now we just have to count 3-digit strings using the digits 3, 3, 4. This one is easy enough to count directly: 3 total! (But if you really want to use permutations and combinations, the appropriate count at this step is 3C1 = 3.)

By the way, sign up for our 1 Week Free Trial to try out Magoosh GMAT Prep!

No comments yet.


Magoosh blog comment policy: To create the best experience for our readers, we will only approve comments that are relevant to the article, general enough to be helpful to other students, concise, and well-written! 😄 Due to the high volume of comments across all of our blogs, we cannot promise that all comments will receive responses from our instructors.

We highly encourage students to help each other out and respond to other students' comments if you can!

If you are a Premium Magoosh student and would like more personalized service from our instructors, you can use the Help tab on the Magoosh dashboard. Thanks!

Leave a Reply