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
GMAT Combinations with Restrictions Article
Posted on
04
Mar 2021

Combinations with Restrictions

By: Rich Zwelling, Apex GMAT Instructor
Date: 4th March, 2021

In our previous post, we discussed how GMAT combinatorics problems can involve subtracting out restrictions. However, we discussed only PERMUTATIONS and not COMBINATIONS.

Today, we’ll take a look at how the same technique can be applied to COMBINATION problems. This may be a bit more complicated, as you’ll have to use the formula for combinations, but the approach will be the same.

Let’s start with a basic example. Suppose I were to give you the following problem:

The board of a large oil company is tasked with selecting a committee of three people to head a certain project for the following year. It has a list of ten applicants to choose from. How many potential committees are possible?

This is a straightforward combination problem. (And we know it’s a COMBINATION situation because we do not care about the order in which the three people appear. Even if we shift the order, the same three people will still comprise the same committee.)

We would simply use the combination math discussed in our Intro to Combination Math post:

                         10!
 10C3 =       ————-
                     3! (10-3!)

 

   10!
———
3! (7!)

 

10*9*8
———
3!

 

10*9*8
———
3*2*1

= 120 Combinations 

However, what if we shifted the problem slightly to look like the following? (As always, give the problem a shot before reading on…):

The board of a large oil company is tasked with selecting a committee of three people to head a certain project for the following year. It has a list of ten applicants to choose from, three of whom are women and the remainder of whom are men. How many potential committees are possible if the committee must contain at least one woman?

A) 60
B) 75
C) 85
D) 90
E) 95

In this case, there’s a very important SIGNAL. The language “at least one” is a huge giveaway. This means there could be 1 woman, 2 women, or 3 women which means we would have to examine three separate cases. That’s a lot of busy work. 

But as we discussed in the previous post, why not instead look at what we don’t want and subtract it from the total? In this case, that would be the case of 0 women. Then, we could subtract that from the total number of combinations without restrictions. This would leave behind the cases we do want (i.e. all the cases involving at least one woman). 

We already discussed what happens without restrictions: There are 10 people to choose from, and we’re selecting a subgroup of 3 people, leading to 10C3  or 120 combinations possible. 

But how do we consider the combinations we don’t want? Well, we want to eliminate every combination that involves 0 women. In other words, we want to eliminate every possible committee of three people that involves all men. So how do we find that?

Well, there are seven men to choose from, and since we are choosing a subgroup of 3, we can simply use 7C3 to find the number of committees involving all men:

                       7!
7C3 =       ————-
                 3! (7-3!)

 

  7!
———
3! (4!)

 

7*6*5
———
    3!

= 7*5 = 35 Combinations involving all men

So, out of the 120 committees available, 35 of them involve all men. That means 120-35 = 85 involve at least one woman. The correct answer is C. 

Next time, we’ll return to probability and talk about how the principle of subtracting out elements that we don’t want can aid us on certain questions. Then we’ll dovetail the two and talk about how probability and combinatorics can show up simultaneously on certain questions.

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
Posted on
18
Feb 2021

A Continuation of Permutation Math

Review of Example From Last Post

Last time, when we started our discussion of GMAT Combinatorics, we gave a brief example of GMAT permutations in which we had five paintings and asked how many arrangements could be made on a wall with those paintings. As it turns out, no complicated combinatorics formula is necessary. You can create an easy graph with dashes and list five options for the first slot, leaving four for the second slot, and so on:

_5_  _4_ _3_ _2_ _1_

Then multiply 5*4*3*2*1 to get 120 arrangements of the five paintings. Remember you could see this notationally as 5!, or 5 factorial. (It’s helpful to memorize factorials up to 6!)

More Permutation Math

But there could be fewer slots then items. Take the following combinatorics practice problem:

At a cheese tasting, a chef is to present some of his best creations to the event’s head judge. Due to the event’s very bizarre restrictions, he must present exactly three or four cheeses. He has brought his best cheddar, brie, gouda, roquefort, gruyere, and camembert. How many potential orderings of cheeses can the chef create to present to the judge?

A) 120
B) 240
C) 360
D) 480
E) 600

First, as a review, how do we know this is a PERMUTATION and not a COMBINATION? Because order matters. In the previous problem, the word “arrangements” gave away that we care about the order in which items appear. In this problem, we’re told that we’re interested in the “orderings” of cheeses. Cheddar followed by gouda would be considered distinct from gouda followed by cheddar. (Look for signal words like “arrangements” or “orderings” to indicate a PERMUTATION problem.)

In this case, we must consider the options of three or four cheeses separately, as they are independent (i.e. they cannot both happen). But for each case, the process is actually no different from what we discussed last time. We can simply consider each case separately and create dashes (slots) for each option. In the first case (three cheeses), there are six options for the first slot, five for the second, and four for the third:

_6_  _5_  _4_

We multiply those together to give us 6*5*4 = 120 possible ways to present three cheeses. We do likewise for the four-cheese case:

_6_  _5_  _4_  _3_

We multiply those together to give us 6*5*4*3 = 360 possible ways to present four cheeses.

Since these two situations (three cheeses and four cheeses) are independent, we simply add them up to get a final answer of 120+360 = 480 possible orderings of cheeses, and the correct answer is D. 

You might have also noticed that there’s a sneaky arithmetic shortcut. You’ll notice that you have to add 6*5*4 + 6*5*4*3. Instead of multiplying each case separately, you can factor out 6*5*4 from the sum, as follows:

6*5*4 + 6*5*4*3

= 6*5*4 ( 1 + 3)

= 6*5*4*4

= 30*16 OR 20*24

= 480

Develop the habit of looking for quick, efficient ways of doing basic arithmetic to bank time. It will pay off when you have to do more difficult questions in the latter part of the test. 

Now that we have been through GMAT permutations, next time, I’ll give this problem a little twist and show you how to make it a COMBINATION problem. Until then…

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

 

By: Rich Zwelling, Apex GMAT Instructor
Date: 16th February, 2021

Read more
Combinatorics & Permutations
Posted on
11
Feb 2021

Introduction to Combinatorics & Permutations

GMAT Combinatorics. It’s a phrase that’s stricken fear in the hearts of many of my students. And it makes sense because so few of us are taught anything about it growing up. But the good news is that, despite the scary title, what you need to know for GMAT combinatorics problems is actually not terribly complex.

To start, let’s look at one of the most commonly asked questions related to GMAT combinatorics, namely the difference between combinatorics and permutations

Does Order Matter?

It’s important to understand conceptually what makes permutations and combinations differ from one another. Quite simply, it’s whether we care about the order of the elements involved. Let’s look at these concrete examples to make things a little clearer:

Permutations Example

Suppose we have five paintings to hang on a wall, and we want to know in how many different ways we can arrange the paintings. It’s the word “arrange” that often gives away that we care about the order in which the paintings appear. Let’s call the paintings A, B, C, D, and E:

ABCDE
ACDEB
BDCEA

Each of the above three is considered distinct in this problem, because the order, and thus the arrangement, changes. This is what defines this situation as a PERMUTATION problem. 

Mathematically, how would we answer this question? Well, quite simply, we would consider the number of options we have for each “slot” on the wall. We have five options at the start for the first slot:

_5_  ___ ___ ___ ___

After that painting is in place, there are four remaining that are available for the next slot:

_5_  _4_ ___ ___ ___

From there, the pattern continues until all slots are filled:

_5_  _4_ _3_ _2_ _1_

The final step is to simply multiply these numbers to get 5*4*3*2*1 = 120 arrangements of the five paintings. The quantity 5*4*3*2*1 is also often represented by the exclamation point notation 5!, or 5 factorial. (It’s helpful to memorize factorials up to 6!)

Combinations Example

So, what about COMBINATIONS? Obviously if we care about order for permutations, that implies we do NOT care about order for combinations. But what does such a situation look like?

Suppose there’s a local food competition, and I’m told that a group of judges will taste 50 dishes at the competition. A first, a second, and a third prize will be given to the top three dishes, which will then have the honor of competing at the state competition in a few months. I want to know how many possible groups of three dishes out of the original 50 could potentially be selected by the judges to move on to the state competition.

The math here is a little more complicated without a combinatorics formula, but we’re just going to focus on the conceptual element for the moment. How do we know this is a COMBINATION situation instead of a permutation question? 

It’s a little tricky, because at first glance, you might consider the first, second, and third prizes and believe that order matters. Suppose that Dish A wins first prize, Dish B wins second prize, and Dish C wins third prize. Call that ABC. Isn’t that a distinct situation from BAC? Or CAB? 

Well, that’s where you have to pay very close attention to exactly what the question asks. If we were asking about distinct arrangements of prize winnings, then yes, this would be a permutation question, and we would have to consider ABC apart from BAC apart from CAB, etc. 

However, what does the question ask about specifically? It asks about which dishes advance to the state competition. Also notice that the question specifically uses the word “group,” which is often a huge signal for combinations questions. This implies that the total is more important than the individual parts. If we take ABC and switch it to BAC or BCA or ACB, do we end up with a different group of three dishes that advances to the state competition? No. It’s the same COMBINATION of dishes. 

Quantitative Connection

It’s interesting to note that there will always be fewer combinations than permutations, given a common set of elements. Why? Let’s use the above simple scenario of three elements as an illustration and write out all the possible permutations of ABC. It’s straightforward enough to brute-force this by including two each starting with A, two each starting with B, etc:

ABC
ACB
BAC
BCA
CAB
CBA

But you could also see that there are 3*2*1 = 3! = 6 permutations by using the same method we used for the painting example above. Now, how many combinations does this constitute? Notice they all consist of the same group of three letters, and thus this is actually just one combination. We had to divide the original 6 permutations by 3! to get the correct number of permutations.

Next time, we’ll continue our discussion of permutation math and begin a discussion of the mechanics of combination math. 

 

Contributor: Rich Zwelling, Apex GMAT Instructor

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