Posted on
23
Feb 2021

An Intro to Combination Math

Last time, we looked at the following GMAT combinatorics practice problem, which gives itself away as a PERMUTATION problem because it’s concerned with “orderings,” and thus we care about the order in which items appear:

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

(Review the previous post if you’d like an explanation of the answer.)

Now, let’s see how a slight frame change switches this to a COMBINATION problem:

At a farmers market, a chef is to sell some of his best cheeses. Due to the market’s very bizarre restrictions, he can sell exactly two or three cheeses. He has brought his best cheddar, brie, gouda, roquefort, gruyere, and camembert. How many potential groupings of cheeses can he create for display to customers? 

A) 6
B) 15
C)
20
D) 35
E) 120

Did you catch why this is a COMBINATION problem instead of a PERMUTATION problem? The problem asked about “groupings.” This implies that we care only about the items involved, not the sequence in which they appear. Cheddar followed by brie followed by gouda is not considered distinct from brie followed by gouda followed by cheddar, because the same three cheeses are involved, thus producing the same grouping

So how does the math work? Well, it turns out there’s a quick combinatorics formula you can use, and it looks like this: 

combinations problem

Let’s demystify it. The left side is simply notational, with the ‘C’ standing for “combination.” The ‘n’ and the ‘k’ indicate larger and smaller groups, respectively. So if I have a group of 10 paintings, and I want to know how many groups of 4 I can create, that would mean n=10 and k=4. Notationally, that would look like this:

combinatorics and permutations on the GMAT, combination math on the gmat

Now remember, the exclamation point indicates a factorial. As a simple example, 4! = 4*3*2*1. You simply multiply every positive integer from the one given with the factorial down to one. 

So, how does this work for our problem? Let’s take a look:

At a farmers market, a chef is to sell some of his best cheeses. Due to the market’s very bizarre restrictions, he can sell exactly two or three cheeses. He has brought his best cheddar, brie, gouda, roquefort, gruyere, and camembert. How many potential groupings of cheeses can he create for display to customers? 

A) 6
B) 15
C)
20
D) 35
E) 120

The process of considering the two cases independently will remain the same. It cannot be both two and three cheeses. So let’s examine the two-cheese case first. There are six cheese to choose from, and we are choosing a subgroup of two. That means n=6 and k=2:

combinations and permutation on the gmat, combination math on the gmat

Now, let’s actually dig in and do the math:

combinatorics and permutations on the GMAT, combination math on the gmat

combinatorics and permutations on the GMAT, combination math on the gmat

From here, you’ll notice that 4*3*2*1 cancels from top and bottom, leaving you with 6*5 = 30 in the numerator and 2*1 in the denominator:

combinatorics and permutations on the GMAT, combination math on the gmat That leaves us with:

6C2 = 15 combinations of two cheeses

Now, how about the three-cheese case? Similarly, there are six cheeses to choose from, but now we are choosing a subgroup of three. That means n=6 and k=3:

solving a combinatorics problem

From here, you’ll notice that the 3*2*1 in the bottom cancels with the 6 in the top, leaving you with 5*4 = 20 in the numerator:

combination problem on the gmat answer

That leaves us with:

6C3 = 20 combinations of three cheeses

With 15 cases in the first situation and 20 in the second, the total is 35 cases, and our final answer is D. 

Next time, we’ll talk about what happens when we have permutations with repeat elements.

In the meantime, as an exercise, scroll back up and return to the 10-painting problem I presented earlier and see if you can find the answer. Bonus question: redo the problem with a subgroup of 6 paintings instead of 4 paintings. Try to anticipate: do you imagine we’ll have more combinations in this new case or fewer?

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: 23rd 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