Don't get smaller- Get bigger!

How many 6 digit numbers that only contain the digits 1-9 have digits in non-decresing order?

For example, 113336 is one valid, but 116333 is not, because 6 came before


The answer is 3003.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Alex Li
May 13, 2015

Note that there is a bijection between sets of 6 digits, allowing repetition, and 6 digit numbers satisfying the condition, because once the digits are chosen, there is exactly one way to place the digits in ascending order. Thus we need to count the number of sets of 6 digits, where only the number of appearances of each digit is significant.

Let x 1 x_1 be the number of 1's, x 2 x_2 be the number of 2's, and so on. The equation we now have is x 1 + x 2 + . . . + x 9 = 6 x_1+x_2+...+x_9=6 , where x i x_i is a nonnegative integer for all 1 i 9 1\le i\le9 . By a "stars-and-bars" argument, the number of such 9-tuples ( x 1 , x 2 , . . . , x 9 ) (x_1, x_2, ... , x_9) is ( m + n 1 n 1 ) = ( 9 + 6 1 6 ) = ( 14 6 ) = 3003 \dbinom{m+n-1}{n-1}=\dbinom{9+6-1}{6}=\dbinom{14}{6}=\boxed{3003} .

You have 6 stars and 8 bars, so the answer is actually ( 14 6 ) = 3003 \binom{14}{6} = 3003 .

Jon Haussmann - 6 years, 1 month ago

Log in to reply

how 6 stars and 8 bars ? And why not 6 stars and 9 bars?

Vighnesh Raut - 6 years, 1 month ago

Log in to reply

Because the bars separate the stars for each category. For instance, there is a bar separating the stars for digit 1 and digit 2, and a bar separating the stars for digit 2 and digit 3, and so on, up to digit 8 and digit 9. This gives a total of 8 bars.

Jon Haussmann - 6 years, 1 month ago

Log in to reply

@Jon Haussmann ok..thanks sir....I came to know where I was wrong...

Vighnesh Raut - 6 years, 1 month ago

As Jon sir explained, the flaw here is that the values of m m and n n are interchanged. In this case the value of m m is 6 6 and of n n is 9 9

Vighnesh Raut - 6 years ago

Log in to reply

wait how did you solve the problem without knowing the solution?

Jonathan Hsu - 6 years ago

Log in to reply

Actually, answering 2002 marked it as incorrect, then i typed 3003..

Vighnesh Raut - 6 years ago

Log in to reply

@Vighnesh Raut oh ok i get it

Jonathan Hsu - 6 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...