The basics of GMAT Combinatorics
Posted on
24
Jun 2021

The Basics of GMAT Combinatorics

By: Apex GMAT
Contributor: Svetozara Saykova
Date: 24th June 2021

Combinatorics can seem like one of the most difficult types of questions to come across on the GMAT. Luckily there are not many of them within the exam. Still these questions make up the top level of scoring on the test and therefore it is best if you are well equipped to solve them successfully, especially if you are aiming for a 700+ score. The most important rule to follow when considering this question type is the “Fundamental Counting Principle” also known as the “Counting Rule.” This rule is used to calculate the total number of outcomes given by a probability problem. 

The most basic rule in Combinatorics is “The Fundamental Counting Principle”. It states that for any given situation the number of overall outcomes is equal to the product of the number of each discrete outcome.

Let’s say you have 4 dresses and 3 pairs of shoes, this would mean that you have 3 x 4 = 12 outfits. The Fundamental Counting Principle also applies for more than 2 options. For example, you are at the ice cream shop and you have a variety of 5 flavors, 3 types of cones and 4 choices for toppings. That means you have 5 x 3 x 4 = 60 different combinations of single-scoop ice creams. 

The Fundamental Counting Principle applies only for choices that are independent of one another. Meaning that any option can be paired with any other option and there are no exceptions. Going back to the example, there is no policy against putting sprinkles on strawberry vanilla ice cream because it is superb on its own. If there were, that would mean that this basic principle of Combinatorics would not apply because the combinations (outcomes) are dependent. You could still resort to a reasoning solution path or even a graphical solution path since the numbers are not so high. 

Let’s Level Up a Notch

The next topic in Combinatorics is essential to a proper GMAT prep is  permutations. A permutation is a possible order in which you put a set of objects.

Permutations

There are two subtypes of permutations and they are determined by whether repetition is allowed or not.

  • Permutations with repetition allowed

When there are n options and r number of slots to fill, we have n x n x …. (r times) = nr permutations. In other words, there are n possibilities for the first slot, n possibilities for the second and so on and so forth up until n possibilities for position number r.

The essential mathematical knowledge for these types of questions is that of exponents

To exemplify this let’s take your high school locker. You probably had to memorize a 3 digit combination in order to unlock it. So you have 10 options (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) for 3 available slots. The total number of locker passwords you can have is 103 = 1,000. 

  • Permutation without repetition allowed 

When repetition is restricted in the given GMAT problem, we would have to reduce the number of available choices for each position. 

Let’s take the previous example and add a restriction to the password options – you cannot have repeating numbers in your locker password. Following the “we reduce the options available each time we move to the next slot” rule, we get 10x9x8 = 720 options for a locker combination (or mathematically speaking permutation). 

To be more mathematically precise and derive a formula we use the factorial function (n!). In our case we will take all the possible options 10! for if we had 10 positions available  and divide them by 7!, which are the slots we do not have. 

10! =  10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 

7! =  7 x 6 x 5 x 4 x 3 x 2 x 1 

And when we divide them (7 x 6 x 5 x 4 x 3 x 2 x 1) cancels and we are left with 10 x 9 x 8 = 720. 

Pro tip: Taking problems and deeply examining them by running different scenarios, and changing some of the conditions or numbers is a great way to train for the GMAT. This technique will allow you to not only deeply understand the problem but also the idea behind it, and make you alert for what language and piece of information stands for which particular concept. 

So those are the fundamentals, folks. Learning to recognize whether order matters and whether repetition is allowed is essential when it comes to Combinatorics on the GMAT. Another vital point is that if you end up with an endless equation which confuses you more than helps, remember doing math on the GMAT Quant section is not the most efficient tactic. In fact, most of the time visualizing the data by putting it into a graph or running a scenario following your reasoning are far more efficient solution paths. 

Feeling confident and want to test you GMAT Combinatorics skills? Check out this GMAT problem and try solving it. Let us know how it goes!

Read more
Permutations with Restrictions GMAT Article
Posted on
02
Mar 2021

Permutations with Restrictions

By: Rich Zwelling, Apex GMAT Instructor
Date: 2nd March, 2021

So far, we’ve covered the basics of GMAT combinatorics, the difference between permutations and combinations, some basic permutation and combination math, and permutations with repeat elements. Now, we’ll see what happens when permutation problems involve conceptual restrictions that can obscure how to approach the math.

To illustrate this directly, let’s take a look at the following Official Guide problem:

The letters D, G, I, I , and T can be used to form 5-letter strings as DIGIT or DGIIT. Using these letters, how many 5-letter strings can be formed in which the two occurrences of the letter I are separated by at least one other letter?

A) 12
B) 18
C) 24
D) 36
E) 48

Did you catch the restriction? Up until the end, this is a standard permutation with repeats combinatorics problem, since there are five letters and two repeats of the letter ‘I’. However, we’re suddenly told that the two I’s must be separated by at least one other letter. Put differently, they are not allowed to be adjacent.

So how do we handle this? Well, in many cases, it’s helpful to set aside what we want and instead consider what we don’t want. It seems counterintuitive at first, but if we consider the number of ways in which the two I’s can appear together (i.e. what is not allowed) and then subtract that number from the total number of permutations without any restrictions, wouldn’t we then be left with the number of ways in which the two I’s would not appear together (i.e. what is allowed)? 

Let’s demonstrate: 

In this case, we’ll pretend this problem has no restrictions. In the word “DIGIT,” there are five letters and two I’s. Using the principle discussed in our Permutations with Restrictions post, this would produce 5! / 2! = 60 permutations. 

However, we now want to subtract out the permutations that involve the two I’s side by side, since this condition is prohibited by the problem. This is where things become less about math and more about logic and conceptual understanding. Situationally, how would I outline every possible way the two I’s could be adjacent? Well, if I imagine the two I’s grouped together as one unit, there are four possible ways for this to happen:

II DGT

D II GT

DG II T

DGT II

For each one of these four situations, however, the three remaining letters can be arranged in 3*2*1 = 6 ways. 

That produces a total of 6*4 = 24 permutations in which the two I’s appear side by side.

Subtract that from the original 60, and we have: 60 – 24 = 36. The correct answer is D

As you can see, this is not about a formula or rote memorization but instead about logic and analytical skills. This is why tougher combinatorics questions are more likely to involve restrictions.

Here’s another Official Guide example. As always, give it a shot before reading on:

Of the 3-digit integers greater than 700, how many have 2 digits that are equal to each other and the remaining digit different from the other 2 ?

(A) 90
(B) 82
(C) 80
(D) 45
(E) 36

Explanation

This is a classic example of a problem that will tie you up in knots if you try to brute force it. You could try writing up examples that fit the description, such as 717, 882, 939, or 772, trying to find some kind of pattern based on what does work. But as with the previous problem, what if we examine conceptually what doesn’t work?

This will be very akin to how we handle some GMAT probability questions. The situation desired is 2 digits equal and 1 different. What other situations are there (i.e. the ones not desired)?  Well, if you take a little time to think about it, there are only two other possibilities: 

  1. The digits are all the same
  2. The digits are all different

If we can figure out the total number of permutations without restrictions and subtract out the number of permutations in the two situations just listed, we will have our answer. 

First, let’s get the total number of permutations without restrictions. In this case, that’s just all the numbers from 701 up to 999. (Be careful of the language. Since it says “greater than 700”, we will not include 700.)

To get the total number of terms, we must subtract the two numbers then add one to account for the end point. So there are (999-701)+1 = 299 numbers in total without restrictions.

(Another way to see this is that the range between 701 and 999 is the same as the range between 001 and 299, since we simply subtracted 700 from each number, keeping the range identical. It’s much easier to see that there are 299 numbers in the latter case.)

Now for the restrictions. How many of these permutations involve all the digits being the same? Well, this is straightforward enough to brute force: there are only 3 cases, namely 777, 888, and 999. 

How about all the digits being different? Here’s where we have to use our blank (or slot) method for each digit:

___ ___ ___

How many choices do we have for the first digit? The only choices we have are 7, 8, and 9. That’s three choices:

_3_  ___ ___

Once that first digit is in place, how many choices do we have left for the second slot? Well, there are 10 digits, but we have to remove the one already used in the first slot from consideration, as every digit must be different. That means we have nine left:

_3_  _9_  ___

Using the same logic, that leaves us eight for the final slot:

_3_  _9_  _8_

Multiplying them together, we have 3*9*8 = 216 permutations in which the digits are different.

So there are 216+3 = 219 restrictions, or permutations that we do not want. We can now subtract that from the total of 299 total permutations without restrictions to get our final answer of 299-219 = 80. The correct answer is C.

Next time, we’ll take a look at a few examples of combinatorics problems involving COMBINATIONS with restrictions.

Permutations and Combinations Intro
A Continuation of Permutation Math
An Intro To Combination Math
Permutations With Repeat Elements
Permutations With Restrictions
Combinations with Restrictions
Independent vs Dependent Probability
GMAT Probability Math – The Undesired Approach
GMAT Probability Meets Combinatorics: One Problem, Two Approaches

Read more