GMAT Combinatorics: an Introduction
At the risk of blowing all the secrets too early, let’s do this at the beginning.
If you can answer three Core Questions, you’ll be able to answer any Combinatorics question that the GMAT decides to throw at you.
Here they are:
How Many Spaces?
How Many Choices?
Does Order Matter?
Figuring out the number of Spaces, Choices, and whether Order Matters are basically the substance of the rest of this post.
As a note, I have a potentially violent disdain for the standard Permutation and Combinations equations:
It is not worth your time to memorize these, or apply them (for that matter).
As detailed in the book, we ultimately will make sure you are comfortable enough with the concepts to build these equations. If you know how to build them, it’s pointless to memorize them, eh?
Allow me to further my point: we do not need these equations because 1) we are not using Excel and 2) we are not twelve.
So–if your butt is sore by this point and you really want to learn about using those equations in an attempt to spend as long as humanly possible doing GMAT Permutations and Combinations / Combinatorics questions, then it’s your party (and you can cry if you want to).
Now is the appropriate time to close this page and report me to the gods of unnecessary work.
If, on the other hand, you are interested in learning GMAT Combinatorics the correct way, then step inside…
Chapter 1: Factorials
The first and only place to start our discussion of Permutations and Combinations problems is with Factorials.
If we don’t get the concept of Factorials straight, the rest of this is never going to work.
The idea of a Factorial is best described in situ:
There are seven paintings to hang on a wall, and there are an unlimited number of places that we can hang them. In how many ways can the seven paintings be arranged?
That is, we have no restriction on which particular paintings we’re hanging–rather, we can just put them any damn place we please.
Let’s start with the Core Questions as discussed in the Introduction:
How Many Spaces?
This is sort of convenient, isn’t it? We don’t have any restriction on the spaces, so in this case the number of spaces is simply the number of objects: that is, seven total spaces because there are seven paintings. I guess we could theoretically say eight, nine, or 37 spaces, but there are only seven total things to count so we’re still limited back to seven.
So here are our seven spaces:
_ _ _ _ _ _ _
Let’s go to the next question.
How Many Choices?
This one’s probably easier on the surface. We have seven things, so that of course means that we can choose from–wait for it–seven paintings!
What this means in practice, of course, is that we can simply fill the spaces, counting down from seven. In other words, we have seven choices for the first space. We have then chosen one painting, meaning that we have six choices for the second space, etc.
7*6*5*4*3*2*1 = 7!
Note that as we work through the spaces left-to-right we multiply: seven choices for the first space times six choices for the second space times five choices for the third space, etc.
7 x 6 x 5 x 4 x 3 x 2 x 1 = 7! = 5040
(At this risk of assuming too much knowledge, I’m taking it for granted that if you’ve picked up this book you’re aware that the exclamation point is the mathematical shorthand for Factorial.)
Now, all that said, it’s possible that the multiplication business doesn’t come naturally. This is OK–you can remember a simple example here and refer to it if you get lost later on.
Let’s say that we have three main courses and four appetizers available. How many different meals can be made from these possibilities?
It might be simplest to look at a diagram here:
What we see is that if we choose Main Course 1–that is, we “lock Main Course 1 into place”– we have four choices: one for each of the four appetizers. Likewise, if we lock Main Course 2 into place, we could have a further four, and the same for Main Course 3.
This, of course, gives us 3 4 =12 different meal possibilities. It’s no different when you have more than two spaces: you just multiply each space by the value in the successive space, and you’re good.
Now on to the third question.
Does Order Matter?
It bloody well should, should it not? That’s the point of the question, after all: we are calculating how many different orders we can put the paintings in.
Put this on your phone’s home screen if you need to: the most basic, native calculation in Combinatorics, provides a situation where Order Matters.
So that’s a useful thing to tattoo on the inside of your eyelids:
The Factorial calculation always creates a situation where Order Matters.
Everything else is just variations on this theme.
If you understand Factorials, we only have two more essential building blocks to worry about: 1) how to clip the Factorials by restricting the number of possible spaces (Permutations); 2) how to take one of those clipped Factorials and randomize the bastard (Combinations).
Onward and upward.
Chapter 2: GMAT Permutations
As noted above, this is simply a clipped factorial.
Let’s take the case from above and modify it slightly.
Three paintings, from a group of seven total paintings, are chosen to be hung on a wall. In how many ways can these three paintings be arranged?
So: seven paintings to choose from, but need to figure out how many different ways (orders) we can hang the three paintings.
All we have to do is ask the three Core Questions, of course.
How Many Spaces?
There are three spaces to hang the paintings. That makes… three.
How Many Choices?
There are seven paintings to choose from.
That means that we count down from the seven just as before. Only we’re limited by the three spaces. That gives us:
7 x 6 x 5
Last but not least…
Does Order Matter?
Remember, we’re looking for the different orders (or different ways) that the paintings can be organized. So… er… yeah–order matters. That means we just keep it the way it is, because the original Factorial calculation tells us that order matters.
That gives us:
7 x 6 x 5 = 210
If it helps, that means the order Painting A, Painting B, Painting C would be considered different from the order Painting B, Painting A, Painting C and so forth even though we have selected the same paintings.
All that said, if we wanted to find the situation where order doesn’t matter, this would mean that Painting A, Painting B, Painting C would be considered the same as Painting B, Painting A, Painting C and so forth.
This is getting slightly ahead, so let’s move on and catch up with ourselves. Next topic: Combinations.
Like what you’re seeing so far?
Get this information plus an absolute TON of worked examples in the GMAT Permutations and Combinations Guide.
(PS There’s still lots to read after the break!)The GMAT Permutations and Combinations Guide
Chapter 3: GMAT Combinations
Combinations are simply Permutations where the order is randomized. In other words, the order doesn’t matter.
Three paintings, from a group of seven total paintings, are chosen to be hung on a wall. How many groups of three paintings can be chosen?
Think about it this way: we have calculated everything thus far assuming that the order does matter. In fact, simply by virtue of the fact that we are using Factorials to build these circumstances we must build everything using situations where order matters.
A Combination is, essentially (and precisely), a Permutation where we have randomized the orders of the chosen objects. You would be correct and deserve a cookie if you noticed that we are actually doing extra work to make the situation simpler. If that seems a bit stupid, well, it is. So much of math could be more efficient, eh?
Let’s work this out with the above situation.
The Combination would be asking how many groups of three paintings could be selected (rather than how many ways three paintings could be selected). That means that if we pick Painting A, Painting B, and Painting C, that would be the same group as Painting B, Painting A, Painting C and so forth.
In other words:
abc = acb = bac = bca = cab =cba
= 3! possibilities
That means six different situations are counted as the same, so we really just need to count one for every six. We get the value six by taking the factorial of the size of the group, in this case 3!.
That is, the combination in our sample case becomes this:
Note that the 6 and the 3! Cancel each other easily because 3! = 6.
Really, as we go on from here, knowing that 3! = 6 and 4! = 24 and 5! = 120 will save you a lot of grief; it would be useful to commit these to memory.
…the situation where you need to specifically know the order will be quite rare. You can think about it as situations where you “name the spaces,” e.g., Person A as President and Person B as Secretary would be different from Person A as Secretary and Person B as President.
If you really need to take a guess–and after all, if you ask yourself the Core Questions, the distinction between Permutation and Combination will be clear–then the vast majority of the time you’ll be asked to find the number of different possibilities that constitute a group. That is, a Combination.
In short, if you must, punt on the side of Combinations.
Because it’s a pain to write all the math all the time when one is planning in Combinatorics, the “shorthand versions” or Permutation and Combination are often used.
For our case, the shorthand Permutation would be this:
7P3 = 7*6*5
The shorthand Combination would be this:
In each case, note that the number of Choices is on the left and the number of Spaces is on the right. In the case of the Combination, the number of Spaces is the same as the Factorial on the bottom.
In other words, we can say that a Combination is simply a Permutation divided by the Factorial of the group size. That means we could even choose to write the shorthand this way:
Note: different shorthand systems write the Permutation and Combination in different ways. You’ll often see them written like this, for example:
Ultimately, you won’t see any of this shorthand on GMAT Combinatorics questions–remember, you’re just using it to plan those complicated-ass problems–so you could really pick any shorthand system and it wouldn’t make any difference. I prefer to write in the nPr and nCr form, but you can do whatever the hell you like.
To recap, let’s look at another brief example, proposed in a slightly different way.
Chapter 4: GMAT Permutations and Combinations Recap
Let’s consider a case where we have six different-colored marbles: red, blue, green, yellow, purple, and chartreuse.
If we were to put four of these marbles into a box, we could select four and lay them directly into the box.
How Many Spaces?
Four fit in the box: _ _ _ _
How Many Choices?
We begin with six: 6 x 5 x 4 x 3
Now, we still don’t have enough information to know whether we’re looking at a Permutation or a Combination.
We have put the marbles in a specific order. That is, we’d treat Red, Blue, Green, and Yellow as a different order from Blue, Red, Green, Yellow, and so forth. There will be 4! = 24 ways that this set of four colors could be distributed.
The Permutation counts all of these possibilities as different.
Think about it this way: we have, of course, put the marbles into the box in a particular order. At this point, they’re just sitting there in that same order. The “different orders” refers to the number of different ways that we could have placed them.
Here is our Permutation:
6 x 5 x 4 x 3 = 360
That’s where dividing by the factorial of the group size comes in. That means that we only care about the different groups of 4. We therefore have a factor of 4! = 24 fewer possibilities than we calculated with the Permutation.
In other words, we divide by 4! because we have four spaces. You can think about this as picking the box up and shaking it. Unless you’re very, very lucky, I think we can assume that this action will put the four marbles in a different order. In other words, it randomizes the order.
To yield the Combination, then, we see:
(6*5*4*3)/4! = (6*5*4*3)/(4* 3*2*1) =5*3 =15
If you’re still skeptical, you can double-check by taking the Permutation and dividing by 4! = 24.
So it does work after all!
Using the “Mississippi Rule” (Partial Combinations)
There will be numerous times that we encounter situations where a group has repeated terms but we don’t want to randomize the order of every single term in the group; rather, we simply want to randomize the repeats.
Think about a situation such as this:
If we wanted to know the different number of ways that we could organize these letters, we would be in trouble using the rules that we’ve already seen. The a-terms, of course, are treated the same as one another, as are the b-terms and the c-terms.
Still, we wouldn’t choose to randomize all of the terms by simply dividing by 9! Talk about bringing an AR-15 to a knife fight–not only would it be overkill, it would also be, you know, wrong.
What to do? This leads us to the “Mississippi Rule,” or “Partial Combinations,” as I like to think of them. With a Mississippi situation, we make a special point to account for the repetitions of the terms a, b, and c independently.
The Mississippi Rule also provides a useful mnemonic for remembering how many ways a group that has repeated terms can be arranged.
It all stems from this example:
How many ways can the letters in the word “Mississippi” be arranged?
Let’s start by counting the letters in the word Mississippi. That’s right: there are eleven of them.
If these were all different letters, that would mean there were 11!ways to count them. The problem with this, of course, is the fact that our Ss, Is, and Ps are all stated more than once.
Let’s look at the simplest example, the Ps. There are two Ps that are counted as exactly the same, so if we account for this (by dividing by 2!), we actually have half of the possibilities that we would get from 11! alone. That is…
That’s taking care of the Ps, of course, so let’s take a look at the Ss: there are four of these, so we can account for the repeated terms by dividing by 4! as well. That is…
Then, of course, we can do the exact same thing to account for the Is. Again, the term is repeated four times, so we can divide by 4!. That’s our final value, which is not actually worth calculating.
(OK… it’s actually 34650).
EVEN SO, the final value isn’t as important as the basic idea, which is the factorial of the total divided by the factorial of each repeated term:
Yup. Simple as that.
Now, for practice, let’s apply this to our above example:
That is, there are 1260 different ways that we could organize the letters aabbbcccc. If that seems like a lot of ways, well, it is.
Chapter 5: Ignore This Chapter (Formal Equations for GMAT Permutations)
This whole chapter will be an exercise in pedantry, and I fully encourage you not to read it. I’m not saying you’ll go to hell if you use these equations rather than doing it the correct way, but I am saying I won’t cry at your funeral if you do.
Seriously, I’m writing it because there’s going to be some trainspotter who flames me on Reddit because I didn’t include this section in this book.
In fact, that idiot is probably really angry that I’m calling him a trainspotter right now and will just leave the flame right now. So be it. You know who you are, buddy; I’m waiting.
To the point, then. The equations that we mentioned before are here:
The next question is how do these relate to what we are talking about? After all, we’ve been building our Permutations and Combinations from scratch just fine so far, and that’s sufficient for the GMAT.
Basically, we don’t need these equations because they’re a fluffy, universalized way to do exactly the same thing.
If you’re plugging random variables into Excel rather than working from scratch given actual values, then you’d need something like this. The GMAT expects you to use actual values, of course, which precludes needing to use these ridiculous equations.
Using these equations to solve a GMAT Combinatorics question is analogous to, for example, using the Quadratic Formula to solve for x in x^2-5x +6 = 0. You could use the equation and, naturally, you’d get the values 2 and 3 to pop out of the equation.
However you probably already knew that it would be 2 and 3 because you did it in your head. That’s because a quadratic like this would almost always be easier to break by hand (or head) using guess-and-check.
Nevertheless, let’s look at how these cute, if a bit slow, little P&C equations work.
We can use the seven paintings case again. For the Permutation, we start with the factorial of the total number of paintings on top. This is our n, which presumably means “number” but I don’t really know that for sure–don’t take my word for it.
At this point, we divide by the factorial of the difference between the “number” n and the “restriction” r. Again, don’t know if that’s the right term, but hey, I chose something that starts with r so let’s roll with it. Note that our restriction r is the same number as the Number of Spaces when you do this question the correct way.
And… we’re right back where we started. See how it’s easier just to say “three spaces and count down from seven?”
In essence, we arrive at the Number of Spaces, r, by chopping off what isn’t r. Effectively, we’re saying something like this…
…and cleverly ignoring the fact that WE NEED TO KNOW THE VALUE OF r TO GET THE EQUATION TO SPIT OUT THE VALUE OF r. Jeez.
For Combinations we do the same thing but put in the extra instance of r! on the bottom. That means we’re dividing by the factorial of the number of spaces. In other words, the extra r! simply randomizes–shakes the box–as discussed before.
Yet again, we’re back where we started, despite loads of extra work. Now that work didn’t make it wrong or anything, but it sure as shit didn’t help, either.
All this and much, much more–loads of worked examples, the promised relationship between those dumbass P&C equations and the Slot Method, and plenty of terrible jokes to be found here:The GMAT Permutations and Combinations Guide