Lesson: Introduction to Combinations

Comment on Introduction to Combinations

Dear Brent
I solved the "Will must choose a 3-character computer password, consisting of 1 letter from the alphabet and 2 distinct digits" question in the following way:

1L 2D
The letter can be chosen out in 26 ways
The digits in 10 x 9 (since the two must be distinct)
And the letter can take one of 3 places within the code.

Therefore, it can be achieved in 26 x 10 x 9 x 3 ways.
(I know the math turns out to be the same, but is the approach wrong? )
gmat-admin's picture

Question link: https://gmatclub.com/forum/will-must-choose-a-3-character-computer-passw...

That's a perfectly valid approach - great work!

Hi Brent

Can you please explain this part of the solution:

Stage 2: Select the two digits to be used in the code
Since the order in which we select the two digits does not matter, we can use combinations.
We can select 2 digits from 10 women in 10C2 ways (45 ways)
So, we can complete stage 2 in 45 ways

Thanks
gmat-admin's picture

You're referring to my solution here: https://gmatclub.com/forum/will-must-choose-a-3-character-computer-passw...

In stages 1 and 2, I select one letter and two digits. During these stages, I'm not doing any arranging. So the order in which I select the two digits does not matter.

Later, in stage 3, I get around to arranging the three characters (1 letter and 2 digits), at which point order does matter.

Since order doesn't matter when I'm selecting the two digits (in stage 2), we can use combinations to select 2 digits from 10 digits.

Does that help?

Hey Brent, saw your solution on GMAT Club and want to understand why you use this Combination question. As stated by the previous user, it said distinct. So my approach was just like the above but forgot the (3). Is there another way to solve for this different from your solution and the above?
gmat-admin's picture

Here's a longer way that examines all 3 cases separately: https://gmatclub.com/forum/will-must-choose-a-3-character-computer-passw...

Can you pls help me understand my query marked in ALL CAPS:

S is a set of points in the plane (IT DOES NOT MENTION IF THE POINTS ARE COLLINEAR OR DISPERSED). How many distinct triangles can be drawn that have three of the points in S as vertices?

(1) The number of distinct points in S is 5. - SO WHY IS (1) NOT SUFFICIENT ON ITS OWN?

(2) No three of the points in S are collinear.
gmat-admin's picture

Question link: https://gmatclub.com/forum/s-is-a-set-of-points-in-the-plane-how-many-di...

If it isn't stated whether the points are collinear or dispersed, then we can't make any conclusion about their location.

So, when statement 1 tells us that there are 5 points, we have no idea whether the points are collinear or dispersed. Let's examine two possible cases.

Case a - All 5 points are collinear. In this case, we cannot create ANY triangles

Case b - The 5 points are dispersed (no 3 points are collinear). In this case, we can create 10 triangles, since any 3 selected points will create a triangle. 5C3 = 10

Does that help?

How do we identify if the question is counting question or combination question?
gmat-admin's picture

I'm not sure what you mean. Combination questions are a type of counting question. So, if a question is a combination question, then it is also a counting question.

If you're looking for guidance regarding when we need to use combinations and when we need to use a different approach, I cover that in the following video: https://www.gmatprepnow.com/module/gmat-counting/video/788

I've also written 3 articles on that topic:

Article #1: https://www.gmatprepnow.com/articles/combinations-and-non-combinations-%...

Article #2: https://www.gmatprepnow.com/articles/combinations-and-non-combinations-%...

Article #3: https://www.gmatprepnow.com/articles/does-order-matter-combinations-and-...

Brent,

In the problem below, on the second criteria... what is the quickest way to come up with finding 6 choose 2 or 4 other than trying out each one. This can take more than 2 minutes in the exam, unless you know (as your explanation goes).

https://gmatclub.com/forum/from-a-group-of-6-employees-k-employees-are-chosen-to-be-on-the-party-237543.html

Thanks
Sri
gmat-admin's picture

Question link: https://gmatclub.com/forum/from-a-group-of-6-employees-k-employees-are-c...

Great question, Sri.

An interesting property of combinations is that nCr = nC(n-r)

Some examples:
10C3 = 10C7
5C1 = 5C4
7C5 = 7C2

I'll use an illustrative example to show WHY this is the case.

Let's say you have 6 friends, and you can choose 4 of them to attend your party. We can do this in 6C4 ways

However, we can think of this situation in a different way. Rather than select 4 friends (out of 6 friends) to attend your party, we could just select 2 friends (out of 6 friends) to NOT attend the party, and then the remaining 4 friends get to attend the party. Notice that the outcome is exactly the same.

We can select 2 friends from 6 friends in 6C2 ways.

Since the outcome for each approach is the same, it must be the case that 6C4 = 6C2

Now to your question!

If I have the option of calculating 6C4 or 6C2, it's faster to calculate the one that has the smaller second number.

So, we can calculate 6C2 faster than we can calculate 6C4

6C2 = (6)(5)/(2)(1) = 15 (for more, see https://www.gmatprepnow.com/module/gmat-counting/video/789)

Does that help?

Cheers,
Brent

How do we determine when to use FCP vs Combination formula.

Can you please break this down it is really confusing to me deciding what question I should use FCP for and which one to use the combination formula for.

Thank you
gmat-admin's picture

We have a video that specifically answers your question: https://www.gmatprepnow.com/module/gmat-counting/video/788

Cheers,
Brent

Hi Brent, facing some understanding issue of the question below. The question clearly states "in any order" and if I follow the answer that I get is 26C1*10C2, why the solution wants to multiply that with 3! when the order does not matter as stated.

https://gmatclub.com/forum/will-must-choose-a-3-character-computer-password-consisting-of-1-lett-223186.html
gmat-admin's picture

Question link: https://gmatclub.com/forum/will-must-choose-a-3-character-computer-passw...

In Stages 1 & 2, we select the 3 letters that we will be using.
For example, during those two stages, we might select two W's and one Q
At this point, we have NOT YET arranged the three letters.

In Stage 3, we arrange the three selected characters.

Cheers,
Brent

Hi Brent,

Have a question, these two questions below look exactly similar to me and I followed the same approach (FCP) to answer both. While I got the answer correct for one (triangle) and not for the other (Rectangle). Could you help me understand why FCP approach doesn't apply to Rectangle one?

https://gmatclub.com/forum/right-triangle-pqr-is-to-be-constructed-in-the-xy-plane-so-71597.html

https://gmatclub.com/forum/rectangle-abcd-is-constructed-in-the-coordinate-plane-parall-142272.html
gmat-admin's picture

Question links:
1) https://gmatclub.com/forum/right-triangle-pqr-is-to-be-constructed-in-th...
2) https://gmatclub.com/forum/rectangle-abcd-is-constructed-in-the-coordina...

I have a feeling that, for question #2, you counted some rectangles more than once.
If you can show me your solution to the rectangle question, I should be able to pinpoint the problem.

Cheers,
Brent

Sure! In the rectangle ABCD where AB is parallel to x axis and AD is parallel to y axis, the coordinates for the vertices are
A - x1 y1
B - x2 y1
C - x2 y2
D - x1 y2

So we need to find two values of x and two values of y
x1 and x2 can have 9*8 = 72 ways
y1 and y2 can have 11*10 = 110 ways, totaling into 7920 ways.

gmat-admin's picture

This solution has the same issue as your solution below (regarding the 4 pairs of twins).

You wrote: x1 and x2 can have 9*8 = 72 ways
One possible outcome is that we choose 4 for x1 and choose 10 for x2
Another possible outcome is that we choose 10 for x1 and choose 4 for x2
These two outcomes are IDENTICAL.

Since the order in which we select values for x1 and x2 does not matter, we should use combinations.
We can select 2 x-values from 9 possible values in 9C2 ways (36 ways)

The same applies to selecting the y-values.

Does that help?

Cheers,
Brent

Understood. So why does the same logic is not applicable to the Triangle question?
gmat-admin's picture

Notice that a rectangle in this question can be defined by any two points on the diagonal of the rectangle.
For example, if I tell you that (4, 7) and (2, 5) are points on the diagonal of a rectangle, then we automatically know the other two points will be (4, 5) and (2, 7).

The same cannot be said of the right triangles in the other question.

Cheers,
Brent

Hi Brent,

In the question below, I followed a different approach. Here it is - 4 sets of twin = 8 people overall

Stage 1: select the 1st member in 8C1 = 8 ways
Stage 2: Supposing that the selected member is from Set 1 of the 4 sets of twins, total number of people to choose from becomes 6, therefore select the 2nd member in 6C1 = 6 ways
Stage 3: similarly, select the 3rd member in 4C1 = 4 ways.

Wanted to understand what's wrong with this approach since the restricted is followed.

https://www.beatthegmat.com/combinations-t123249.html
gmat-admin's picture

Question link: https://www.beatthegmat.com/combinations-t123249.html

In your solution, you have counted each outcomes 6 times.

Let's say that a pair twins is represented by uppercase and lowercase versions of the same letter (e.g., B and b)
So, the 8 people are: A, a, B, b, C, c, D, d

Using your approach, one possible outcome is as follows:
Stage 1: select B, Stage 2: select d, Stage 3: select A

Here's another possible outcome:
Stage 1: select B, Stage 2: select A, Stage 3: select d

Another possible outcome:
Stage 1: select d, Stage 2: select A, Stage 3: select B

Another possible outcome:
Stage 1: select d, Stage 2: select B, Stage 3: select A

Another possible outcome:
Stage 1: select A, Stage 2: select B, Stage 3: select d

Another possible outcome:
Stage 1: select A, Stage 2: select d, Stage 3: select B

Your approach treats the 6 outcomes above as 6 different outcomes, when in actuality, they are all THE SAME.

Since you have counted every outcome 6 times, we need to divide your final answer by 6.
This will give you the correct answer.

Cheers,
Brent

Hi Brent,

Thank you for your explanation. Just a small question since I tried to answer it in another way. If I had to calculate the number of ways in which the two twins are from same group, how would I have gone about doing so?

Thanks
gmat-admin's picture

Here's my full solution that follows that approach: https://www.beatthegmat.com/combinations-t123249.html#828080

Cheers,
Brent

https://gmatclub.com/forum/rectangle-abcd-is-constructed-in-the-coordinate-plane-parall-142272.html

Why do we use different methods for rectangle and triangles. I calculated it as 98*8 for X and 11*1
0 for Y just as I did for triangle. In both cases X & Y take only two values.
gmat-admin's picture

Question link: https://gmatclub.com/forum/rectangle-abcd-is-constructed-in-the-coordina...

I'm assuming you're referring to RIGHT triangles, yes?
The big difference is that triangles have 3 sides and rectangles have 4 sides. So, this will likely affect the outcomes.

Notice that, if I tell you that two diagonally opposite points in a RECTANGLE are (1,3) and (10,7), then I automatically know that the other two points in the rectangle are (1,7) and (10,3)

Conversely, if I tell you that two endpoints of the hypotenuse of a right TRIANGLE are (1,3) and (10,7), then there are TWO possible locations for the 3rd point of the triangle. The 3rd point can be EITHER at (10,3) OR at (1,7)

Does that help?

Cheers,
Brent

Ohkay! So for a rectangle, we use combination formula nC2 for X & Y points.
gmat-admin's picture

That's correct.

https://gmatclub.com/forum/rectangle-abcd-is-constructed-in-the-coordinate-plane-parall-142272.html

In this question - if we use combinations and choose x=3,4 and y = 4,5, dont we get a square instead of a rectangle? Please advise
gmat-admin's picture

Question link: https://gmatclub.com/forum/rectangle-abcd-is-constructed-in-the-coordina...

A rectangle is any quadrilateral that has 4 right angles.
As such, a square is a certain type of rectangle (one in which all 4 sides have equal length)

For more on this, watch: https://www.gmatprepnow.com/module/gmat-geometry/video/874

Cheers,
Brent

Hi Brent,

https://www.beatthegmat.com/a-family-consisting-of-one-mother-t103048.html

My approach to this question was as follows -

Stage 1 : the driver's seat- can be accomplished in 2 ways
Stage 2 : Backseat middle seat - can be accomplished in 2, as none of the sisters can't sit together and 1 parent already seated at the driver's seat
Stage 3 : passenger's seat front - can be accomplished in 4 ways
Stage 4 : 2 remaining backseats - can be in 2 and 1 ways

Total = 2x2x4x2x1 = 32 ways

What do you think?

Thanks in advance!

gmat-admin's picture

Question link: https://www.beatthegmat.com/a-family-consisting-of-one-mother-t103048.html

Great idea to use the middle backseat to keep the sisters separated!

Cheers,
Brent

Hey Brent,

in this Q:

https://gmatclub.com/forum/s-is-a-set-of-points-in-the-plane-how-many-distinct-triangles-can-be-61337.html

What does collinear mean? Is that an important concept?

Thanks,

Philipp
gmat-admin's picture

Link: https://gmatclub.com/forum/s-is-a-set-of-points-in-the-plane-how-many-di...

"Collinear" means to be on the same line.
So, if 3 points are collinear, we can draw a straight line through all 3 points.
For the above question, this term is important because we cannot draw a triangle by connecting 3 collinear points.

Cheers,
Brent

Considering the Q that we are taking about:

The 2nd statement says no 3 points are colinear. combin ing it with stm. 1, doesn´t that mean that maybe 3 are different and 2 points are the exact same? or that all 5 are different, thus yielding different results?

gmat-admin's picture

Question link: https://gmatclub.com/forum/s-is-a-set-of-points-in-the-plane-how-many-di...

Here's the entire question:

----------------------
S is a set of points in the plane. How many distinct triangles can be drawn that have three of the points in S as vertices?

(1) The number of distinct points in S is 5.
(2) No three of the points in S are collinear.
----------------------

If two points are in the exact same position, then we really just have one point (not two).
That said, the addition of the word "distinct" makes it clear that all 5 points are in different locations.

Cheers,
Brent

HI Brent,

Can you provide your solution to this question please?

https://gmatclub.com/forum/the-carson-family-will-purchase-three-used-cars-there-are-128876.html

thank you :)

Hi Brent,

I have a query. In this question: https://gmatclub.com/forum/a-committee-of-three-people-is-to-be-chosen-from-four-married-couples-94068.html

I did understand your approach and arrived myself at the solution. However, after crossing Stage1 correctly, I assumed Stages 2,3&4 wrong. I considered Stage 2 as the number of ways one person can be chosen from the 3 couples (which was 6), and stage 2 as the number of ways one person can be chosen from remaining 2 couples (which was 4), and finally stage 3 was number of ways one person can be chosen in one couple (answer to which was 2).

Can you help me identify where I went wrong here?

Thank you.
gmat-admin's picture

Question link: https://gmatclub.com/forum/a-committee-of-three-people-is-to-be-chosen-f...
The problem with your solution is that you're counting the each unique outcome 6 times.

Let's say the 4 couples are A&a, B&b, C&c and D&d
Now let's say that, in stage 1, we selected the following three couples: A&a, C&c and D&d (which we can accomplish in 4C3 ways)

Let's say that, using your approach, we choose:
- d for stage 2
- A for stage 3
- C for stage 4
As a result, the three committee members are d, A and C

In your solution, this outcome is considered different from choosing:
- A for stage 2
- C for stage 3
- d for stage 4
As you can see, this committee (consisting of A, C and d) is identical to first committee we created.

Your solution also suggests this outcome is different from choosing:
- C for stage 2
- d for stage 3
- A for stage 4
As you can see, this committee (consisting of C, d and A) is identical to two committees above.

etc.

In your solution, the unique committee consisting of A, C and d will be counted SIX TIMES
In fact, every unique committee will be counted six times.

So, if we take your solution and divide it by 6, we'll reach the correct answer.

Hi Brent,

I was going through the extra questions at the bottom of the topic and wanted to ask a question.

I understand your solution in this question https://gmatclub.com/forum/rectangle-abcd-is-constructed-in-the-coordinate-plane-parall-142272.html

We use combinations as the outcome of the stages of picking our 2x/2y are the same, in that x= 7,10 is the same as x=10,7.

However it reminded me of a similar question I once read youir solution for.
https://gmatclub.com/forum/right-triangle-pqr-is-to-be-constructed-in-the-xy-plane-so-71597.html

My query is, in the case of a coordinate question such as these, how do we know when to employ combination vs the FCP?
Could a solution using combination be employed for the right angle triangle question?
My gut says no but I cannot wrap my head as to the clear reason why.

Appreciate your help in the matter, have a great day
Best wishes
Matt
gmat-admin's picture

Solution link: https://gmatclub.com/forum/rectangle-abcd-is-constructed-in-the-coordina...

My solution to the linked question above isn't much different from my solution at https://gmatclub.com/forum/right-triangle-pqr-is-to-be-constructed-in-th...

Notice that I use the FCP in both cases.

However, for the top question, each stage required me to choose TWO coordinates. Since the order in which I chose the coordinates didn't matter, I used combinations.

For the bottom question, each stage required me to choose only ONE coordinate. So, for example, in stage 2, I had to choose an integer x-coordinate from –4 to 5 inclusive. Since there are 10 possible values (-4, -3, -2, -1, 0, 1, 2, 3, 4, 5), we can complete stage 2 in 10 ways. Note that I COULD have also used combinations here and said we can select an x-coordinate in 10C1 ways (since the order in which I select that one point doesn't matter).

Does that help?

Hi Brent,
with respect to this question, https://gmatclub.com/forum/in-how-many-different-ways-can-6-identical-belts-and-5-identical-hats-307440.html

1) Is it a good idea to identify what we have to choose when we approach how to solve the question?
In the above question, it's the children we have to choose to decide who receives a belt and a hat, a belt or a hat. since all 6 belts are identical and all hats are identical, it doesn't matter who receives it.

2) If the same question changed slightly where the hats and belts had choices available like different colours or different styles, how would the approach change?

Thanks
Rahul
gmat-admin's picture

Question link: https://gmatclub.com/forum/in-how-many-different-ways-can-6-identical-be...

1) Good question. Since the belts and hat are identical, assigning child A to a specific belt and specific hat would be the same as assigning child A to a different belt and hat.

2) If the belts and hats were all different, the question would become significantly harder.
One approach would be to first:
- Select 3 children to receive both a hat and a belt
- Select 2 children to receive a hat but no belt
- The remaining 3 children would receive a belt but no hat

Then we'd have to go back and:
- Select a specific belt and hat for 1 of the 3 children receiving both a hat and a belt
- Select a specific belt and hat for another of the 3 children receiving both a hat and a belt
- Select a specific belt and hat for the last child receiving both a hat and a belt
- Select a specific hat for 1 of the 2 children receiving a hat only.
- Select a specific hat for the other child receiving a hat only.
- Select a specific belt for 1 of the 3 children receiving a belt only.
- Select a specific belt for another child receiving a belt only.
- Select a specific belt for the last child receiving a belt only.

Hi Brent,

https://gmatclub.com/forum/will-must-choose-a-3-character-computer-password-consisting-of-1-lett-223186.html

For the question, we have to choose 2 "distinct" digits. Should we not use 10C1 x 9C1 for choosing the 2 digits, so that each digit is different?

Thanks!
gmat-admin's picture

Question link: https://gmatclub.com/forum/will-must-choose-a-3-character-computer-passw...

10C2 represents the number of ways to select 2 (different) digits from 10 digits.
So, the distinctness is guaranteed.

If we use 10C1 x 9C1, then we are implying that the order of the digits matters.
That is, selecting the digits 3 and 4 is considered different from selecting the digits 4 and 3.

OG2019, PS 187

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?

Can this be solved simply by using 8C2?

Pages

Office Hours

On December 20, 2023, Brent will stop offering office hours. 

Change Playback Speed

You have the option of watching the 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 a GMAT expert will answer it as fast as humanly possible.

Free “Question of the Day” emails!