Everything You Need to Know about Combinatorics for the GMAT
Guess what? You can attend the first session of any of our online or in-person GMAT courses absolutely free—we’re not kidding! Check out our upcoming courses here.
It’s a pretty common question we GMAT teachers get: “Can we go over combinatorics?” To which my answer is usually a barely contained sigh.
Sure we can, but the reason you want to go over combinatorics is because they’re hard, and you’re under the mistaken impression that you need to get hard questions right to do well on the GMAT—and this just isn’t really that true. You get a 700 score more by not missing many 600-level questions than by getting 700-level questions correct. And the fact is, you’re just not going to see many combinatorics questions on the test, at any level.
“But if I see a 600-level combinatorics question, and you said I need to not miss those to get a 700, don’t I—”
Yeah, yeah, yeah, I heard myself. You still want to make sure you master the more common topics first: percents, algebraic translations, exponent rules, number properties, testing cases on Data Sufficiency, and the like. But if you’re pretty good on that, sure, let’s get the basics of combinatorics questions down so that you can get them right, as well.
So that’s what this post is meant to be: the definitive guide to getting combinatorics problems through the 600 level. By the end, you’ll have some of the most essential formulas for these questions, but also, I hope, a deeper understanding of the relationships between these formulas.
The Basics on GMAT Combinatorics
Let’s start with the most basic rule involved in combinatorics problems. It’s actually got a name: “The Fundamental Counting Principle.” This rule states that in order to determine the total number of overall outcomes, you multiply the number of each discrete outcome together. Or put more simply, “If I have X options in one case, and Y options in another, I have X*Y total options.”
So if I have four choices of sandwich, ten choices of chips, and three choices of snake venom soda, I have 4*10*3=120 total options for my lunch.
USE THIS WHEN: You’re asked about total number of outcomes from different choices and the choices do not affect one another.
Okay, Let’s Ramp it Up a Little
The next thing you’re going to want to know about is permutations.
A permutation is, quite simply, an arrangement of items. Let’s use a classic game to discuss this topic: Mario Kart 64.
In Mario Kart 64, every race had 8 racers. How many outcomes were possible for a race?
This is a classic arrangement problem. Things are put in a certain order, and every order is considered different. Well, we can solve this by using the Fundamental Counting Principle. With 8 racers, I have 8 possible slots to finish in, first through eighth:
_____ _____ _____ _____ _____ _____ _____ _____
I have 8 choices for who finishes first (which was, let’s be real, always Yoshi, if you were any good at that game). After first place is filled, how many choices do I have left for second? Seven. For third? Six. Then five, four, three, two, one.
So multiplying my number of options together, I end up with 8*7*6*5*4*3*2*1 = 8! options. This is why you see so many factorials in combinatorics problems: we’re multiplying options together as we lose an option at each step.
In general, if I have n items that I am arranging, there are n! total outcomes.
USE THIS WHEN: You’re asked to figure out how many ways there are to arrange items—that is, when order matters.
(You can also use this to help guess on harder questions. If you have n items, you can never have an answer bigger than n! It is the absolute maximum).
And Then We Get Trickier…
“Okay, but you know, in Mario Kart 64, the only places that really mattered were first through third. Anyone after that didn’t get any points for the—”
Good point. Nerdy point, perhaps, but good point. Who cares about fourth place? No one. You don’t get to be on the podium when you’re in fourth. So it doesn’t really matter, does it? What if I only want to know how many options there are for the first three finishers?
Well, this isn’t so bad. We can just use the Fundamental Counting Principle: 8 choices for first, 7 for second, 6 for third means I have 8*7*6 total outcomes for the first three finishers.
USE THIS WHEN: You’re arranging a subset of items from a larger selection of items.
That’s easy enough, but to deepen our understanding (and for clarity later on), I’m going to go a little deeper here. I still have the same eight slots for the race, but I only care about the first three, so I’m going to block those off:
_____ _____ _____ //// _____ _____ _____ _____ _____
Notice there are still 8! total arrangements. But an outcome like this:
Yoshi Toad DK /// Luigi Peach Wario Mario Bowser
is, for our purposes, the same as this:
Yoshi Toad DK /// Peach Mario Bowser Luigi Wario
which is the same for any other arrangement of the last five racers. So how many total outcomes are there when the first three finishers are, in order, Yoshi, Toad, and DK?
Well, we have five other racers, so by using our permutations trick, there are 5! outcomes with those first three finishers.
To treat those 5! total outcomes as the same outcome, we can divide by 5!.
And this is true for any outcome of the first three finishers. There are always 5! outcomes that we really just want to treat as the same outcome.
So consider our 8! total arrangements. Within that 8!, there is every conceivable outcome of the first three finishers 5! times each. Thus we can divide out the 5! repetitions for every arrangement of first, second, and third place, and be left with our answer.
This leaves us with 8!/5! outcomes for the first second and third place finishers.
Now, when factorials are divided, you might recall that there is some great cancellation that happens. Since 8! = 8*7*6*5!, the 5! cancels out of numerator and denominator, leaving us with the 8*7*6 total outcomes—which we found earlier just by thinking about the Fundamental Counting Principle.
This is the function nPk: permuting k items out of n total choices. It equals n!/(n-k)!
(Notice that nPn simply equals n!, because 0! = 1).
This all might have seemed unnecessary, since we got 8*7*6 pretty easily up front. But it illustrates what is about to be a crucial thing to understand about combinatorics: in order to find out any arrangements you’re looking for out of your n total objects, you will need to divide out the ‘repetitions’ from the total n! arrangements.
When Order Really Doesn’t Matter
Now what if Nintendo was trying to figure out which 3 racers to feature on the player’s manual? It doesn’t matter what order they’re in—Nintendo is just curious about the group. How many options are there?
We now find ourselves in a somewhat different situation. Unlike in our previous questions, in this question, our order really doesn’t matter. So you might think the math is completely different—but it actually isn’t. We’re still going to start with our 8 slots and 8! total arrangements, and we’re going to separate them off again with the three characters we might choose left of the brackets and the five that we don’t choose right of them.
_____ _____ _____ /// _____ _____ _____ _____ _____
This time, this outcome:
Yoshi Toad DK /// Luigi Peach Wario Mario Bowser
is, for us, the same as this outcome:
DK Yoshi Toad /// Peach Mario Bowser Luigi Wario
is the same as this outcome:
Yoshi DK Toad /// Mario Wario Peach Bowser Luigi
We don’t care about the order they fall in, we just care who falls on what side of the brackets. So given this outcome—where Yoshi, DK, and Toad fall left of the bracket—how many possible ways are there for this outcome to happen?
As before, we have 5! ways to arrange the back 5. Those are all the same to us. But since we also don’t care about the order of the first 3 anymore, we might recognize that there are 3! ways to arrange them that we consider ‘the same.’
Using the Fundamental Counting Principle, we have 3! * 5! total arrangements that we treat identically. 3! for the arrangements on the left, 5! for the arrangements on the right.
Which means out of 8! total arrangements, we want to get rid of the 3!*5! total duplications for each left-of-bracket/right-of-bracket outcome.
Leaving us with 8!/(5!*3!) total outcomes. Nice cancellation takes this to 8*7 = 56 total outcomes. There are 56 groups of 3 you can choose from a group of 8.
This is often called a ‘combination,’ and its formula you might have seen as:
nCk = n!/((n-k)!*k!)
Notice how similar this is to nPk—except now, we ‘cancel out’ the different order of the k items we’re choosing as well as the n-k items we aren’t. (Fun fact: notice how choosing 3 from 8 is mathematically identical to choosing 5 from 8. When I choose 3, I’m ‘not choosing’ 5, which is, essentially, choosing 5 to ‘not choose’… That makes sense, I promise. Okay, maybe it wasn’t a ‘fun’ fact, but still.)
That nCk formula always looks nasty to me, but notice how the denominator numbers will always add to the number in the numerator, and realize all you’re doing is dividing out the duplications of arrangements we want to treat as ‘the same,’ since the order of those arrangements doesn’t matter to us now.
USE THIS WHEN: You’re picking a subgroup from a bigger group of options and order doesn’t matter.
This can also be used as a guessing strategy. If you’re picking k items out of n total items, but there’s a ‘twist’ (more on that later), it can’t possibly be larger nCk, and you should eliminate it and any number larger.
And One Last Thing about Combinatorics
One final consideration: what if we’re arranging items, but some of the items are the same? A famous example of this is: how many ways are there to arrange the letters of ‘Mississippi’?
Well, there are 11 total slots:
_____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____
and therefore 11! total arrangements. Here’s one possible arrangement:
M _ I _ S _ S _ I _ S _ S _ I _ P _ P _ I
But if I switch the P’s around, and some of the S’s, and some of the I’s, here’s another:
M _ I _ S _ S _ I _ S _ S _ I _ P _ P _ I
Of course, this seems like the same arrangement as before. How do I handle that?
Well, if I treat every S as ‘different,’ how many outcomes are there that keep the spelling ‘Mississippi’?
That is, how many ways are there to arrange the four S’s? Four items, 4! arrangements.
Same with the four I’s. The two P’s have 2! ways to be arranged.
So there are 4!*4!*2! outcomes of ‘Mississippi’ that look the same to me, since I can’t distinguish between identical S’s and I’s and P’s. And there are that many duplications for every arrangement in the spelling of ‘Mississippi.’
Which means in the 11! total outcomes, I can divide out the 4!*4!*2! duplications of each unique arrangement.
11!/(4!*4!*2!)
The general formula here is: n!/(r1! * r2! * r3! *…*rk!)
Where there are n total spots, and each rk is the number of repetitions of a certain item in the group.
USE THIS WHEN: You’re arranging items but some of the items are identical.
Which Combinatorics Not to Do
There you go. These are the principles you’ll need most to get through the 600-level questions. The big question you’ll need to ask yourself when you see one of these problems is, “Does the order of the grouping matter or not?” and decide which tactic above to use.
And let me be clear: this is all you need to know about combinatorics until you’re scoring about a 48 on the Quant. You only need to do be able to do a harder combinatorics question when you’ve absolutely mastered everything else.
So how do you know what a ‘harder’ combinatorics question is?
The easiest clue is that there is an added rule to the problem. You’re not just counting a number of arrangements or figuring out how many groups there are—suddenly there are all these other rules. Two people can’t sit next to each other, or have to sit next to each other, or they’re sitting in a circle, or one person can’t sit on the ends and someone else has to sit in an odd number seat, or… etc. etc. etc.
Exceptions can make these problems exceedingly tedious—and very difficult. The more extreme the exception, the more certain you can be that you’re facing a real dragon of a question. And you just don’t need to be the knight that beats the dragons to get that 700 score you really need—fighting regular ol’ GMAT monsters will do. 📝
Want some more GMAT tips from Reed? Attend the first session of one of his upcoming GMAT courses absolutely free, no strings attached. Seriously.
Reed Arnold
is a Manhattan Prep instructor based in New York, NY. He has a B.A. in economics, philosophy, and mathematics and an M.S. in commerce, both from the University of Virginia. He enjoys writing, acting, Chipotle burritos, and teaching the GMAT. Check out Reed’s upcoming GMAT courses here.
No comments yet