Lesson: When to use Combinations

Rate this video: 
5

Comment on When to use Combinations

so what is the answer to the 50 students in school, electing Pres, VP, and treasurer? Do you mind explaining?
gmat-admin's picture

The answer is 117600. The solution for that question starts around 3:10 in the video

I have similar question to 8 people hand shake,

There are 8 teams in a certain league and each team plays each of the other teams exactly once. If each game is played by 2 teams, what is the total number of games played?

The outcome is not 56 but 28, I guess it's because of wording" each team plays with other team only once"
Is my reasoning correct?
gmat-admin's picture

There are two approaches we can use. One is mathematical, and the other involves some number sense.

Number sense: Once all of the teams have finished playing their games, ask each of the 8 teams, "How many teams did you play?" We'll find that EACH TEAM played 7 teams, which gives us a total of 56 games (since 8 x 7 = 56).

From here we need to recognize that every game has been counted TWICE. For example, if Team A and Team B play a game, then Team A counts it as a game, AND Team B also counts it as a game. Of course only one game occurred between these teams. So, to account for the duplication, we'll divide 56 by 2 to get 28.

The mathematical approach: there are 8 teams, and we want to determine how many different ways they can be matched to play a game. This is the same as asking, "In how many different ways can we select 2 teams to play a game?" Notice that the order in which we select the 2 teams does not matter. For example, choosing Team A then Team B to play a game against each other is the same as choosing Team B then Team A to play a game against each other. Since order does not matter, we can select 2 teams from 8 teams in 8C2 ways (= 28 ways)

A company that ships boxes to a total of 12 distribution centers uses color coding to identify each center. If either a single color or a pair of two different centers is chosen to represent each center and if each center is uniquely represented by that choice of one or two colors, what is the minimum number of colors needed for the coding? (Assume that the order of the colors in a pair does not matter)
(A) 4
(B) 5
(C) 6
(D) 12
(E) 24
gmat-admin's picture

I have answered that question here: http://www.beatthegmat.com/distribution-centers-t263732.html

Please let me know if you have any questions

How did we arrive at the figure 15?
gmat-admin's picture

Good catch! I meant to say 12. I have edited my response accordingly (http://www.beatthegmat.com/distribution-centers-t263732.html)

Thanks!

How do combinations relate to the MISSISSIPPI rule, given that here the order of some letters matters, whereas the order in other letters (e.g. S and I) it does not matter?
gmat-admin's picture

I wouldn't place too much energy into trying to determine whether there's a relationship between combinations and the MISSISSIPPI rule. Only in very specific cases are they similar.

gmat-admin's picture

Allow me to expand on my comment above.

In the video question at https://www.gmatprepnow.com/module/gmat-counting/video/786 we note that the number of possible routes is equal to the number of ways to arrange the letters DDDRRRR.

In the video solution, we use the MISSISSIPPI rule to determine the number of ways to arrange the letters DDDRRRR.

HOWEVER, since there are only 2 different letters (R and D), we could have also used COMBINATIONS to determine the number of ways to arrange the letters DDDRRRR.

Here's what I mean:

One way to arrange the 7 letters (DDDRRRR) is to think of which letter will go in the FIRST spot, which letter will go in the SECOND spot, which letter will go in the THIRD spot, etc.

Of the seven possible spots, 3 of them must be D's and 4 must be R's.

So, let's first place ALL THREE D's.
To do this, we'll CHOOSE 3 of the 7 spots that will have D's
We can CHOOSE 3 spots from 7 spots on 7C3 ways (= 35 ways)
Once we've placed the 3 D's in those 3 spots, we'll place the 4 R's in the 4 remaining spots.
This will complete the arrangement.

So, the number of ways to arrange the letters DDDRRRR is equal to 7C3 (35)

You need to put your reindeer, Lancer, Prancer, Gloopin, and Bloopin, in a single-file line to pull your sleigh. However, Prancer and Lancer are fighting, so you have to keep them apart, or they won't fly.How many ways you can arrange your reindeer?
gmat-admin's picture

One approach is to first IGNORE the restriction about keeping Prancer and Lancer apart.

So, we can arrange the 4 reindeer in 4! ways (= 24 ways)

Of course, some of those 24 arrangements include cases in which Prancer and Lancer are TOGETHER. So, we must subtract those instances from 24.

To determine how many cases there are in which Prancer and Lancer are TOGETHER, let's "glue" them together to make ONE big reindeer (PRANCERLANCER).

So, we now have 3 objects to arrange: PRANCERLANCER, Gloopin, and Bloopin
We can arrange those 3 objects in 3! ways (= 6 ways).

Also note that we can also "glue" Prancer and Lancer together so that Lancer is first to get LANCERPRANCER, Gloopin and Bloopin.
Once again, we have 3 objects to arrange: LANCERPRANCER, Gloopin, and Bloopin.
We can arrange those 3 objects in 3! ways (= 6 ways).

So, the total number of arrangements where Prancer and Lancer are TOGETHER = 3! + 3! = 6 + 6 = 12

We'll now subtract that amount from the 4! arrangements that IGNORE the restriction about keeping Prancer and Lancer apart.

So, the TOTAL number of arrangements in which keeping Prancer and Lancer are APART = 24 - 12 = 12

Cheers,
Brent

I have a verbal type question :)

You said at 6:01 "of the 2 remaining stages selecting the 1st is the more restrictive" You used more not most. Can you explain why?
gmat-admin's picture

Good question, Kaori.

When we are comparing more than 2 things, we use the superlative "most"
When we are comparing exactly 2 things, we use the comparative "more"

So, at 6:01 in the video, we are examining the TWO remaining stages, so we must use the comparative "more"

For more information about "more/most" see:
https://www.gmatprepnow.com/module/gmat-sentence-correction/video/1182 (starting at 2:38)

Cheers,
Brent

Thanks :)

Hi Brent,

In this question: https://gmatclub.com/forum/if-two-distinct-positive-divisor-of-64-are-randomly-selected-168952.html

Once we've identified the factors, etc. We can solve the question in both ways.

a) As a combination problem: 5C2/7C2 = 10/21
b) As a sequence: 5*4 / 7*6 = 20/42 = 10/21

However, there are similar questions that only the combination approach works (a) (or I think so), as the one I attach at the end. Could you help me with that please? I'm a bit confused.

Thanks in advance,

(e.g.: A basketball coach will select the members of a five-player team from among 9 players, including John and Peter. If the five players are chosen at random, what is the probability that the coach chooses a team that includes both John and Peter?)

gmat-admin's picture

Great question, Roger!

If we're going to use the counting approach to solving a probability question (such as the question below), then there are times when we can use either combinations or the fundamental counting principle (FCP). The most important thing is to use the same strategy for both the numerator and denominator. That is, we can't treat the numerator as though the order of the selections DOES matter and then denominator as though the order of the selections does NOT matter.

The question: A basketball coach will select the members of a five-player team from among 9 players, including John and Peter. If the five players are chosen at random, what is the probability that the coach chooses a team that includes both John and Peter?

Let's solve the question in two ways:
1) Order matters. So, we might say that each selected player will be assigned a SPECIFIC POSITION on the team (center, point guard, power forward, etc).
2) Order does not matter. In other words, the selected players are not assigned a position on the team. They are just on the team.

Let's solve the question each way:
------------------------------------------
1) Order matters.
The NUMERATOR (# of ways to assign the 5 positions so that John and Peter are on the team)
STAGE 1: Assign a position to John. There are 5 different positions (center, point guard, etc). So, this stage can be completed in 5 ways.
STAGE 2: Assign a position to Peter. There are 4 positions remaining. So, this stage can be completed in 4 ways.
NOTE: There are still 3 positions on the team that have not been assigned.
Let's call the 3 unassigned positions Position A, Position B, and Position C
STAGE 3: Assign a player to Position A. There are 7 players remaining to choose from. So, this stage can be completed in 7 ways.
STAGE 4: Assign a player to Position B. There are 6 players remaining to choose from. So, this stage can be completed in 6 ways.
STAGE 5: Assign a player to Position A. There are 5 players remaining to choose from. So, this stage can be completed in 5 ways.
So, the NUMERATOR = (5)(4)(7)(6)(5)

The DENOMINATOR (# of ways to assign the 5 positions to 9 players)
STAGE 1: Assign a player to one position. There are 9 players to choose from. So, this stage can be completed in 9 ways.
STAGE 2: Assign a player to the next position. There are 8 players to choose from. So, this stage can be completed in 8 ways.
STAGE 3: Assign a player to the next position. This stage can be completed in 7 ways.
STAGE 4: Assign a player to the next position. This stage can be completed in 6 ways.
STAGE 5: Assign a player to the last remaining position. This stage can be completed in 5 ways.
So, the NUMERATOR = (9)(8)(7)(6)(5)

So, P(team includes John and Peter) = (5)(4)(7)(6)(5)/(9)(8)(7)(6)(5) = 5/18

------------------------------------------
2) Order does NOT matter.
The NUMERATOR (# of ways to choose 5 players so that John and Peter are on the team)
STAGE 1: Place John and Peter on the team). This stage can be completed in 1 way.
STAGE 2: Choose 3 players from the remaining 7 players. Since order doesn't matter, we can use combinations.
We can select 3 players from 7 players in 7C3 ways (= 35 ways)

So, the NUMERATOR = (1)(35) = 35

The DENOMINATOR (# of ways to choose any 5 players to be on the team)
STAGE 1: Choose 5 players from the 9 players. Since order doesn't matter, we can use combinations.
We can select 5 players from 9 players in 9C5 ways (= 126 ways)

So, P(team includes John and Peter) = 35/126 = 5/18

As we can see, we get the same answer both times.

Cheers,
Brent

Brent, Why is the pizza question not an FCP question? (12)(11)(10)?
1st topping 12 ways to choose -> 2nd topping 11 ways to choose -> 3rd topping 10 ways to choose ->1320 ways?
gmat-admin's picture

You're referring to the question that starts at 3:50 in the above video.

If we say that the correct answer is (12)(11)(10), then we are saying (for example) that selecting onions 1st, pepperoni 2nd and tomatoes 3rd is DIFFERENT FROM selecting onions 1st, tomatoes 2nd and pepperoni 3rd.

That is, we're saying that the ORDER in which we select the toppings MATTERS when, in actuality, the ORDER does NOT matter: an onion, pepperoni and tomatoes pizza is THE SAME AS an onion, tomatoes and pepperoni pizza.

Does that help?

Cheers,
Brent

Add a comment

Ask on Beat The GMAT

If you have any questions, ask them on the Beat The GMAT discussion forums. The average response time is typically less than 30 minutes.

Change Playback Speed

You have the option of watching our videos at various speeds (25% faster, 50% faster, etc). To change the playback speed, click the settings icon on the right side of the video status bar.

Have a question about this video?

Post your question in the Comment section below, and we’ll answer it as fast as humanly possible.

Free “Question of the Day” emails!