Lesson: Calculating Combinations

Comment on Calculating Combinations

Why and how is 0!=1?
gmat-admin's picture

Keep in mind that n! = the product of POSITIVE integers from n to 1. So, 0! doesn't even make any sense, since factorials are only defined for positive integers.

That said, we need to have some agreed-upon convention for dealing with 0! so that we can ensure that calculations involving factorials make sense.

For example, the number of ways to select 3 people from 3 people = 3C3 = 3!/(3!)(0!)

We already know that there is only 1 way to select 3 people from 3 people. So, we need 0! to equal 1. As such, this is an agreed-upon convention.

http://www.beatthegmat.com/mobster-combinatorics-t166632.html
In this case since "though not necessarily right behind him" shouldn't we,
360 - (# of time J is behind F = 120 ) == 240 ?
Please help.
gmat-admin's picture

Question link: http://www.beatthegmat.com/mobster-combinatorics-t166632.html

The words "not necessarily right behind him" do not change the answer.

The key concept here is that, if we IGNORE the restriction, we can arrange the 6 people in 720 ways.

Of these 720 different arrangements, Frankie will be standing behind Joey half the time, and Joey will be standing behind Frankie half the time. (in other words, for every arrangement where Frankie is ahead of Joey, there is an arrangement where Joey is ahead of Frankie).

Does that help?

Cheers,
Brent

Hi Brent,

Could you help me with the below question please.

How many 3 digit integers can be chosen such that none of the digits appear more than twice and none of the digits equal zero ?

A. 729
B. 720
C. 648
D. 640
E. 576

I solved it as 9 * 9* 8 and got it wrong.



gmat-admin's picture

I think you're missing the phrase "more than TWICE." This means it's okay to have a 3-digit number that has a digit appear TWICE, but it's not okay to have a digit appear THREE TIMES. So, for example, the numbers 664 and 922 are okay, but the number 777 is not okay.

The quickest solution is to first determine the number of ways to create ANY 3-digit number that does not contain any zeros.

For each digit, we have 9 options (1,2,3,4,5,6,7,8 or 9).
So, the TOTAL number of outcomes = (9)(9)(9) = 729

Of course, some of these 729 outcomes break rule about not allowing a digit to appear THREE TIMES. So, we must subtract from 729 all of the outcomes that break the rule.

Fortunately, there aren't many rule-breakers among the 729 outcomes.

The rule-breakers are the following numbers: 111, 222, 333, 444, 555, 666, 777, 888 and 999 (9 altogether).

So, the number of outcomes that satisfy the given restrictions = 729 - 9
= 720

Does that help?

Cheers,
Brent

what if the question is changed to say , none of the digits cannot appear more than twice or twice?
that is 666 or 665 is not allowed or 566 or 656 ?
gmat-admin's picture

In other words, what is the answer is NO repetitions are allowed. So, the question becomes:

"How many 3-digit integers can be chosen such that none of the digits appear more than ONCE and none of the digits equal zero?

STAGE 1: Select the hundreds digit
The hundreds digit can be 1, 2, 3, 4, 5, 6, 7, 8 or 9
We can complete this stage in 9 ways

STAGE 2: Select the tens digit
Once we select one of the 9 digits(1, 2, 3, 4, 5, 6, 7, 8 or 9) in stage 1, there are 8 digits remaining from which to choose the tens digit.
So, we can complete this stage in 8 ways

STAGE 3: Select the units digit
Once we select digits for stages 1 and 2, there are 7 digits remaining from which to choose the units digit.
So, we can complete this stage in 7 ways

TOTAL number of outcomes = (9)(8)(7)

Cheers,
Brent

Hi Brent, just to clarify - does this shortcut work for all Combination questions?

Is there an occasion when we are to use the formula over the shortcut?

Thank you!
gmat-admin's picture

Yes, it applies to all combination questions.

Hi Brent,

Need your help with this one https://gmatclub.com/forum/there-are-5-rock-songs-6-pop-songs-and-3-jazz-how-many-different-57548.html
gmat-admin's picture

Here's how I'd solve that question: https://gmatclub.com/forum/there-are-5-rock-songs-6-pop-songs-and-3-jazz...

Cheers,
Brent

Hi Brent, for the following question you have already explained the solution.

How many 3 digit integers can be chosen such that none of the digits appear more than twice and none of the digits equal zero ?

However, I am not able to understand why the below solution is incorrect or where my thinking is flawed.

9 * 9* 8

Please can you clarify. Thanks.
gmat-admin's picture

To help determine why your solution, 9*9*8, is incorrect, we should ask "What does each each number represent?"

Presumably, the first 9 represents choosing any nonzero digit for the first digit.
Likewise, the second 9 represents choosing any nonzero digit for the second digit.
From here, what does the 8 represent?
When you answer that question, you'll understand the problem (let me know if you need a hint).

Hi Brent,
The first 9 represents any non-zero digits
Second 9 represents any non-zero digit, since the digits can appear twice
At this point the first two digits that are already selected can either be same or different as well. putting 8 in the third place doesn’t seem right but I am unable to explain/understand it clearly. Appreciate if you have any insights here.

I am trying to solve the question using fundamental counting principle and I think the answer should be as follows. Please can you clarify?
No of ways all three digits are different is 9*8*7= 504 ways
No of ways in which 2 digits are same SSD, DSS, SDS.
SSD=1*8*9 =72
DSS=9*8*1= 72
SDS=1*9*8 or 8*9*1, both will yield same numbers = 72
Therefore, total 3 digit integers where none of the digits appear more than twice and none of the digits equal zero is 504+72*3 = 720
Many Thanks.
gmat-admin's picture

The problem with your first solution is that, if the first two digits are DIFFERENT (e.g., we select 4 for the hundreds digit, and select 7 for the tens digit), then the units can be 1,2,3,4,5,6,7,8, or 9. So, you can complete the last stage in 9 ways.

However, if the first two digits are the SAME (e.g., we select 7 for the hundreds digit, and select 7 for the tens digit), then the units can be anything but that digit. So, you can complete the last stage in 8 ways.

So, we need to account for both possible cases, which is what you have done in your second solution.

Nice work!

Many Thanks Brent for your comments.

Hi Brent, could you help below question?

There are 3 boys and 3 girls stand in a row. Any boy can not be between 2 girls and any girl can not be between 2 boys. How many ways are possible?
gmat-admin's picture

Unless I'm missing something obvious, this isn't a GMAT-style question, because the steps necessary to first identify every possible configuration aren't very mathematical.

Noted thanks Brent

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.

Tweet about the course!

If you're enjoying this GMAT video course, help spread the word on Twitter.

Free “Question of the Day” emails!