• NEW! FREE Beat The GMAT Quizzes
    NEW! FREE Beat The GMAT Quizzes
    NEW! FREE Beat The GMAT Quizzes
    Hundreds of Questions Highly Detailed Reporting Expert Explanations TAKE A FREE GMAT QUIZ
  • 7 CATs FREE!
    If you earn 100 Forum Points

    Engage in the Beat The GMAT forums to earn
    100 points for $49 worth of Veritas practice GMATs FREE

    Veritas Prep
    VERITAS PRACTICE GMAT EXAMS
    Earn 10 Points Per Post
    Earn 10 Points Per Thanks
    Earn 10 Points Per Upvote
    REDEEM NOW

Permutation and combination

This topic has 5 expert replies and 3 member replies

Permutation and combination

Post
The number of natural numbers of two or more than two digits in which digits from left to right are in increasing order is
a.127
b.128
c.502
d.501
e.512

OA: C

  • +1 Upvote Post
  • Quote
  • Flag

GMAT/MBA Expert

Post
parveen110 wrote:
The number of natural numbers of two or more than two digits in which digits from left to right are in increasing order is
a.127
b.128
c.502
d.501
e.512

OA: C
This problem seems a bit too convoluted for the GMAT.
Also, the GMAT would say positive integers rather than natural numbers.
That said, the problem does provide some worthwhile take-aways, so here's one approach:

For the digits to increase from left to right, they must be DISTINCT.
For each combination of distinct digits, there is only ONE acceptable ordering: from least to greatest.
For example, only one viable integer can be formed if the selected digits are 7, 1 and 3:
137.
Thus, for the each of the following cases, we need to count how many COMBINATIONS of distinct digits can be formed, since each combination of distinct digits will yield exactly one viable integer.

Note the following constraint:
None of the digits in the following cases can be 0.
The reason:
Since the digits must increase from left to right, any combination that includes 0 must place 0 in the leftmost position -- not possible, since the leftmost digit of a positive integer must be at least 1.
Thus, all of the following cases must be formed from the following pool of digits:
1, 2, 3, 4, 5, 6, 7, 8, 9.

We should also note the following:
nCr = nC(n-r).
To illustrate:
6C5 = 6C(6-5) = 6C1.
From 6 options, the number of ways to choose 5 = 6C5 = (6*5*4*3*2)/(5*4*3*2*1) = 6.
From 6 options, the number of ways to choose 1 = 6C1 = 6.
Thus:
6C5 = 6C1.

2-digit integers:
Number of ways to choose 2 distinct integers from 9 options = 9C2 = (9*8)/(2*1) = 36.

3-digit integers:
Number of ways to choose 3 distinct integers from 9 options = 9C3 = (9*8*7)/(3*2*1) = 84.

4-digit integers:
Number of ways to choose 4 distinct integers from 9 options = 9C4 = (9*8*7*6)/(4*3*2*1) = 126.

5-digit integers:
Number of ways to choose 5 distinct integers from 9 options = 9C5 = 9C4 = 126.

6-digit integers:
Number of ways to choose 6 distinct integers from 9 options = 9C6 = 9C3 = 84.

7-digit integers:
Number of ways to choose 7 distinct integers from 9 options = 9C7 = 9C2 = 36.

8-digit integers:
Number of ways to choose 8 distinct integers from 9 options = 9C8 = 9C1 = 9.

9-digit integers:
Here, there is only 1 option:
123456789.

Total options = 36+84+126+126+84+36+9+1 = 502.

The correct answer is C.

_________________
Mitch Hunt
Private Tutor for the GMAT and GRE
GMATGuruNY@gmail.com

If you find one of my posts helpful, please take a moment to click on the "UPVOTE" icon.

Available for tutoring in NYC and long-distance.
For more information, please email me at GMATGuruNY@gmail.com.
Student Review #1
Student Review #2
Student Review #3

  • +1 Upvote Post
  • Quote
  • Flag
Free GMAT Practice Test How can you improve your test score if you don't know your baseline score? Take a free online practice exam. Get started on achieving your dream score today! Sign up now.

GMAT/MBA Expert

Post
parveen110 wrote:
The number of natural numbers of two or more than two digits in which digits from left to right are in increasing order is
a.127
b.128
c.502
d.501
e.512

Consider the arrangement 123456789

Now PRETEND that each digit has a lightbulb inside of it, and each lightbulb is either on or off.
If the lightbulb is ON, we can see that digit, if that lightbulb is OFF, we cannot see the digit.
So, for example, if we turn on the lightbulbs for digits 2, 5, 7 and 8, and turn off the remaining lightbulbs, we see the resulting number 2578
Notice that the digits are nicely arranged in ascending order. In fact, with this ON/OFF setup, every resulting number will have its digits arranged in ascending order.

So, all we need to do now is count the number different ways to turn on and turn off the indivudual lightbulbs.
Let's take the task of turning the lightbulbs on and off, and break it into stages.

Stage 1: Determine the lightbulb situation for digit 1
There are only two possibilities here: the lightbulb is ON or it's OFF
So, we can complete stage 1 in 2 ways

Stage 2: Determine the lightbulb situation for digit 2
There are only two possibilities here: the lightbulb is ON or it's OFF
So, we can complete stage 2 in 2 ways

Stage 3: Determine the lightbulb situation for digit 3
There are only two possibilities here: the lightbulb is ON or it's OFF
So, we can complete stage 3 in 2 ways
.
.
.
Stage 9: Determine the lightbulb situation for digit 9
There are only two possibilities here: the lightbulb is ON or it's OFF
So, we can complete stage 9 in 2 ways

By the Fundamental Counting Principle (FCP), we can complete all 9 stages (and thus create a number with its digits in ascending order) in (2)(2)(2)(2)(2)(2)(2)(2)(2) ways (= 512 ways

IMPORTANT: Among the 512 possibilities, we have accidentally included some scenarios that don't meet the conditions in the question.
For example, among the 512 possibilities, we have accidentally included 1 scenario where ALL of the lightbulbs are off. In this case, there is NO resulting number.
Likewise, the question tells us that we must have 2 or more digits, and among the 512 possibilities, we have accidentally included 9 scenarios where EXACTLY ONE lightbulb is on (resulting in 1, 2, 3, 4,...8, and 9).

So, the number of numbers that meet the given conditions = 512 - 1 - 9
= 502
= C

Cheers,
Brent


Aside: For more information about the FCP, watch our free video: http://www.gmatprepnow.com/module/gmat-counting?id=775

_________________
Brent Hanneson – Creator of GMATPrepNow.com
Use my video course along with Beat The GMAT's free 60-Day Study Guide

Sign up for free Question of the Day emails
And check out all of these free resources



Last edited by Brent@GMATPrepNow on Thu Feb 13, 2014 6:30 am; edited 1 time in total

  • +1 Upvote Post
  • Quote
  • Flag
GMAT Prep Now's comprehensive video course can be used in conjunction with Beat The GMAT’s FREE 60-Day Study Guide and reach your target score in 2 months!
Senior | Next Rank: 100 Posts Default Avatar
Joined
17 Jan 2014
Posted:
91 messages
Upvotes:
7
Post
Brent@GMATPrepNow wrote:
parveen110 wrote:
The number of natural numbers of two or more than two digits in which digits from left to right are in increasing order is
a.127
b.128
c.502
d.501
e.512

Consider the arrangement 123456789

Now PRETEND that each digit has a lightbulb inside of it, and each lightbulb is either on or off.
If the lightbulb is ON, we can see that digit, if that lightbulb is OFF, we cannot see the digit.
So, for example, if we turn on the lightbulbs for digits 2, 5, 7 and 8, and turn off the remaining lightbulbs, we see the resulting number 2578
Notice that the digits are nicely arranged in ascending order. In fact, with this ON/OFF setup, every resulting number will have its digits arranged in ascending order.

So, all we need to do now is count the number different ways to turn on and turn off the indivudual lightbulbs.
Let's take the task of turning the lightbulbs on and off, and break it into stages.

Stage 1: Determine the lightbulb situation for digit 1
There are only two possibilities here: the lightbulb is ON or it's OFF
So, we can complete stage 1 in 2 ways

Stage 2: Determine the lightbulb situation for digit 2
There are only two possibilities here: the lightbulb is ON or it's OFF
So, we can complete stage 2 in 2 ways

Stage 3: Determine the lightbulb situation for digit 3
There are only two possibilities here: the lightbulb is ON or it's OFF
So, we can complete stage 3 in 2 ways
.
.
.
Stage 9: Determine the lightbulb situation for digit 9
There are only two possibilities here: the lightbulb is ON or it's OFF
So, we can complete stage 9 in 2 ways

By the Fundamental Counting Principle (FCP), we can complete all 9 stages (and thus create a number with its digits in ascending order) in (2)(2)(2)(2)(2)(2)(2)(2)(2) ways (= 512 ways

IMPORTANT: Among the 512 possibilities, we have accidentally included some scenarios that don't meet the conditions in the question.
For example, among the 512 possibilities, we have accidentally included 1 scenario where ALL of the lightbulbs are off. In this case, there is NO resulting number.
Likewise, the question tells us that we must have 2 or more digits, and among the 512 possibilities, we have accidentally included 9 scenarios where EXACTLY ONE lightbulb is off (resulting in 1, 2, 3, 4,...8, and 9).

So, the number of numbers that meet the given conditions = 512 - 1 - 9
= 502
= C

Cheers,
Brent


Aside: For more information about the FCP, watch our free video: http://www.gmatprepnow.com/module/gmat-counting?id=775
Hi Brent,

Brilliant approach,as usual..but in the solution you suggested, are you meaning to say that "we have accidentally included 9 scenarios where EXACTLY ONE lightbulb is 'ON' (resulting in 1, 2, 3, 4,...8, and 9)?? Thanks.

  • +1 Upvote Post
  • Quote
  • Flag

GMAT/MBA Expert

Post
parveen110 wrote:
Hi Brent,

Brilliant approach,as usual..but in the solution you suggested, are you meaning to say that "we have accidentally included 9 scenarios where EXACTLY ONE lightbulb is 'ON' (resulting in 1, 2, 3, 4,...8, and 9)?? Thanks.
Good catch, parveen110, thanks!
I've edited my solution accordingly.

Cheers,
Brent

_________________
Brent Hanneson – Creator of GMATPrepNow.com
Use my video course along with Beat The GMAT's free 60-Day Study Guide

Sign up for free Question of the Day emails
And check out all of these free resources

  • +1 Upvote Post
  • Quote
  • Flag
GMAT Prep Now's comprehensive video course can be used in conjunction with Beat The GMAT’s FREE 60-Day Study Guide and reach your target score in 2 months!
Legendary Member Default Avatar
Joined
12 May 2015
Posted:
518 messages
Upvotes:
10
Test Date:
3 Oct
Target GMAT Score:
750
Post
This question seems too tough for GMAT.

  • +1 Upvote Post
  • Quote
  • Flag
Newbie | Next Rank: 10 Posts Default Avatar
Joined
07 May 2017
Posted:
1 messages
Post
just wondering how to formulate that digit..i am seeing an explanation but can’t understand the ‘ask’ here. n >= 2 digits does it mean 2 digit or 3 or 4,5,6,7,..keeps going on. what is the limitation that we apply or how best can this be broken? why should we consider 123456789 and not any repetitions witin it. (looks like old post but just stuck with this understanding)

  • +1 Upvote Post
  • Quote
  • Flag

GMAT/MBA Expert

Post
vinsmba wrote:
just wondering how to formulate that digit..i am seeing an explanation but can’t understand the ‘ask’ here. n >= 2 digits does it mean 2 digit or 3 or 4,5,6,7,..keeps going on. what is the limitation that we apply or how best can this be broken? why should we consider 123456789 and not any repetitions witin it. (looks like old post but just stuck with this understanding)
Can you rephrase your question please.

Aside: "of two or more than two digits" means "two or more digits" (if that's what you're asking)

Cheers,
Brent

_________________
Brent Hanneson – Creator of GMATPrepNow.com
Use my video course along with Beat The GMAT's free 60-Day Study Guide

Sign up for free Question of the Day emails
And check out all of these free resources

  • +1 Upvote Post
  • Quote
  • Flag
GMAT Prep Now's comprehensive video course can be used in conjunction with Beat The GMAT’s FREE 60-Day Study Guide and reach your target score in 2 months!

GMAT/MBA Expert

Post
nikhilgmat31 wrote:
This question seems too tough for GMAT.
Quite possibly.
If it is within the scope of the GMAT, it's a 750+ level question.

Cheers,
Brent

_________________
Brent Hanneson – Creator of GMATPrepNow.com
Use my video course along with Beat The GMAT's free 60-Day Study Guide

Sign up for free Question of the Day emails
And check out all of these free resources

  • +1 Upvote Post
  • Quote
  • Flag
GMAT Prep Now's comprehensive video course can be used in conjunction with Beat The GMAT’s FREE 60-Day Study Guide and reach your target score in 2 months!
  • e-gmat Exclusive Offer
    Get 300+ Practice Questions
    25 Video lessons and 6 Webinars for FREE

    Available with Beat the GMAT members only code

    MORE DETAILS
    e-gmat Exclusive Offer
  • Kaplan Test Prep
    Free Practice Test & Review
    How would you score if you took the GMAT

    Available with Beat the GMAT members only code

    MORE DETAILS
    Kaplan Test Prep
  • The Princeton Review
    FREE GMAT Exam
    Know how you'd score today for $0

    Available with Beat the GMAT members only code

    MORE DETAILS
    The Princeton Review
  • PrepScholar GMAT
    5 Day FREE Trial
    Study Smarter, Not Harder

    Available with Beat the GMAT members only code

    MORE DETAILS
    PrepScholar GMAT
  • EMPOWERgmat Slider
    1 Hour Free
    BEAT THE GMAT EXCLUSIVE

    Available with Beat the GMAT members only code

    MORE DETAILS
    EMPOWERgmat Slider
  • Magoosh
    Magoosh
    Study with Magoosh GMAT prep

    Available with Beat the GMAT members only code

    MORE DETAILS
    Magoosh
  • Veritas Prep
    Free Veritas GMAT Class
    Experience Lesson 1 Live Free

    Available with Beat the GMAT members only code

    MORE DETAILS
    Veritas Prep
  • Target Test Prep
    5-Day Free Trial
    5-day free, full-access trial TTP Quant

    Available with Beat the GMAT members only code

    MORE DETAILS
    Target Test Prep
  • Economist Test Prep
    Free Trial & Practice Exam
    BEAT THE GMAT EXCLUSIVE

    Available with Beat the GMAT members only code

    MORE DETAILS
    Economist Test Prep
  • Varsity Tutors
    Award-winning private GMAT tutoring
    Register now and save up to $200

    Available with Beat the GMAT members only code

    MORE DETAILS
    Varsity Tutors

Top First Responders*

1 Ian Stewart 41 first replies
2 Brent@GMATPrepNow 40 first replies
3 Scott@TargetTestPrep 39 first replies
4 Jay@ManhattanReview 32 first replies
5 GMATGuruNY 26 first replies
* Only counts replies to topics started in last 30 days
See More Top Beat The GMAT Members

Most Active Experts

1 image description Scott@TargetTestPrep

Target Test Prep

159 posts
2 image description Max@Math Revolution

Math Revolution

92 posts
3 image description Brent@GMATPrepNow

GMAT Prep Now Teacher

60 posts
4 image description Ian Stewart

GMATiX Teacher

50 posts
5 image description GMATGuruNY

The Princeton Review Teacher

37 posts
See More Top Beat The GMAT Experts