Lesson: When to use Combinations

Comment on When to use Combinations

so what is the answer to the

so what is the answer to the 50 students in school, electing Pres, VP, and treasurer? Do you mind explaining?

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

I have similar question to 8

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?

There are two approaches we

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 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

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

How did we arrive at the figure 15?

Good catch! I meant to say 12

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

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?

I wouldn't place too much

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.

Allow me to expand on my

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

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?

One approach is to first

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

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?

Good question, Kaori.

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"

https://www.gmatprepnow.com/module/gmat-sentence-correction/video/1182 (starting at 2:38)

Cheers,
Brent

Thanks :)

Hi Brent,

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.

(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?)

Great question, Roger!

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

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?

You're referring to the

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

Brent, in this question https

Brent, in this question https://www.beatthegmat.com/code-in-alphabetical-order-t296532.html , since we have to follow an alphabetical order, the order should matter, nevertheless in the solution combinations are used and i dont understand why since if we know that order does matter we shoukd use the FC principle or other strategies. thank you

Great question!

It all comes down to the fact that, if we have three different letters, there is only ONE way to arrange those three letters in alphabetical order.

So, for example, consider this question:
In how many ways can we arrange the letters B, K, A in alphabetical order?

Rather than ask the question "Does order matter?", think about how you might solve the above question by listing and counting.
When we do this, we see that there's only ONE way to arrange those three letters in alphabetical order.

In my solution, stage 1 involves choosing 3 different letters.
So, some possible outcomes are: DLG, MWA, BPZ, UDX, etc
There are 2600 possible outcomes consisting of 3 different letters.

At this point, we need to take each of the 2600 possible outcomes and arrange the three letters in alphabetical order.

We take EACH outcome and arrange the 3 letters.

So, DLG becomes DGL
MWA becomes AMW
BPZ becomes BPZ
UDX becomes DUX
etc

When all 2600 outcomes are arranged in alphabetical order, we still have 2600 outcomes.

Does that help?

Cheers,
Brent

Thanks Brent. now everything

Thanks Brent. now everything is clear.

Hi Brent,

Hi Brent,

https://gmatclub.com/forum/a-researcher-plans-to-identify-each-participant-in-a-certain-medical-134584.html

In this question , as most solutions suggest to use combinations menthod, wont that be inaccurate ?

We can, indeed, use combinations.
See my solution here: https://gmatclub.com/forum/a-researcher-plans-to-identify-each-participa...

Another approach is to LIST & COUNT as shown here: https://gmatclub.com/forum/a-researcher-plans-to-identify-each-participa...

Cheers,
Brent

"Clarissa will create her

"Clarissa will create her summer reading list by randomly choosing 4 books from the 10 books approved for summer reading. She will list the books in the order in which they are chosen. How many different lists are possible?"

I used the formula nCr that you explain din this video but the results was wrong WHY? How is this DIFFERENT from the pizza toppings exercise??
Thank you

The key word here is ORDER

"She will list the books in the ORDER in which they are chosen."
For example, "Book D 1st - Book C 2nd - Book A 3rd - Book H 4th" is considered different from the list "Book C 1st - Book A 2nd - Book H 3rd - Book D 4th"
In other words, order matters.

For the pizza question, the ORDER of the toppings does not matter.
For example, "Pepperoni 1st - Mushrooms 2nd - Onions 3rd" is the same as "Onions 1st - Pepperoni 2nd - Mushrooms 3rd"
In other words, order does not matter.

Does that help?

Cheers,
Brent

Hi Brent,

Hi Brent,

I couldnt quite grasp as to why the the choosing of President, VP and treasurer is not a combinations questions ? How does it matter if Gita got selected first or last ? As the president or the VP ?

am i getting confused in the semantics ? Please let me know if you need further explanation of my doubt.

Karaan

Consider, for example, these 3 stages:
Stage 1) Select President
Stage 2) Select VP
Stage 3) Select treasurer

If someone is selected in stage 1, then the corresponding outcome is that the person gets to be President.
This outcome is DIFFERENT from the outcome in stage 2, where the selected person gets to be the VP

Since the outcomes are different, we can't use combinations (instead, we can use the FCP).
----------------------------------

Now let's consider a similar example.
Let's say we have 7 people, and we want to invite three people to come to a party.
Let's define our three stages as follows:

Stage 1) Select someone to come to the party
Stage 2) Select another person to come to the party
Stage 3) Select another person to come to the party

If someone is selected in stage 1 then the corresponding outcome is that the person gets to come to the party.
If someone is selected in stage 2 then the corresponding outcome is that the person gets to come to the party.
If someone is selected in stage 3 then the corresponding outcome is that the person gets to come to the party.

Noticed that the three OUTCOMES are all the SAME: The person gets to come to the party.
As such we cannot use the FCP.

Does that help?

Not quite. Can you possibly

Not quite. Can you possibly explain using how does order matter in one example whereas order does not matter in another example ? I am still confused.

In the first example, say we have 5 people to choose from for filling the 3 positions.
The President position can be filled by 5 people, the VP is then left to be filled by 4 people and finally the treasurer can be filled by 3 people. So using FCP, 3 positions can be fulfilled in 60 ways.

Am I applying FCP correctly in this ?

For the second example, can you possibly elaborate how order does not matter ? Because combinations can be used when order of the selected objects does not matter isnt it ?

Thanks,
Karaan

First example:

First example:
Stage 1) Select President
Stage 2) Select VP
Stage 3) Select treasurer
So, if we select Joe in stage 1, Ann in stage 2 and Bea in stage 3, we get President Joe, VP Ann and Treasurer Bea.
Notice that this outcome is DIFFERENT from selecting Ann in stage 1, Joe in stage 2 and Bea in stage 3.
So, order matters.
-----------------------------

Second example:
Stage 1) Select someone to come to the party
Stage 2) Select another person to come to the party
Stage 3) Select another person to come to the party
So, if we select Joe in stage 1, Ann in stage 2 and Bea in stage 3, we get Joe, Ann and Bea coming to the party.
Notice that this outcome is the SAME as selecting Ann in stage 1, Joe in stage 2 and Bea in stage 3.
So, order does not matter.
-----------------------------

"In the first example, say we have 5 people to choose from for filling the 3 positions.
The President position can be filled by 5 people, the VP is then left to be filled by 4 people and finally the treasurer can be filled by 3 people. So using FCP, 3 positions can be fulfilled in 60 ways." Am I applying FCP correctly in this?

Yes, you have applied it perfectly.

Does that help?

Hi Brent,

Hi Brent,

A group of 5 friends—Archie, Betty, Jerry, Moose, and Veronica—arrived at the movie theater to see a movie. Because they arrived late, their only seating option consists of 3 middle seats in the front row, an aisle seat in the front row, and an adjoining seat in the third row. If Archie, Jerry, or Moose must sit in the aisle seat while Betty and Veronica refuse to sit next to each other, how many possible seating arrangements are there?

Thanks, much appreciated!

Hi Brent,

Hi Brent,

Thank you! :)

Can you look at this question and explain the concept of negative remainders? Is it going to be a focus area?

Question 2: What is the remainder when 3^(7^11) is divided by 5? (here, 3 is raised to the power (7^11))

(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

Thanks

You'll never get tested on

You'll never get tested on negative remainders.
When it comes to remainder questions on the GMAT, all values will be positive.
So, for example, if positive integer N is divided by 6, then the remainders must be 0, 1, 2, 3, 4, or 5.
As you can see, the question as tagged as "out of scope"

Hi Brent,

Hi Brent,
Could you explain how would you go about solving the following question?

How many numbers between 1 and 100 (inclusive) are divisible by 5 or 3?

Although I get the correct answers for such questions!

Thanks,

Here's one approach:

Here's one approach:

Multiples of 3: 3, 6, 9, 12, 15...96, 99
99/3 = 33. There are 33 multiples of 3 from 1 to 100 inclusive.

Multiples of 5: 5, 10, 15, 20,....95, 100
100/5 = 20. There are 20 multiples of 5 from 1 to 100 inclusive.

So far, we have 33 + 20 = 53 multiples of 5 or 3.

IMPORTANT: Since 15 is a multiple of both 3 and 5, multiples of 15 appear in BOTH lists.
This means we have counted those multiples (of 15) TWICE

Multiples of 15: 15, 30, 45,...75, 90,
90/15 = 6. So, there are 6 multiples of 15 from 1 to 100 inclusive.

53 - 6 = 47
So, 47 integers from 1 to 100 inclusive are divisible by 3 or 5.