8
$\begingroup$

A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit.

For example, the four-digit number $1234$ is composed of digits that are non-decreasing. Some other four-digit numbers that are composed of non-decreasing digits are $0011$, $1111$, $1112$, $1122$, $2223$.

Notice that leading zeroes are required: $0000$, $0001$, $0002$ are all valid four-digit numbers with non-decreasing digits.

The question is

How many four-digit numbers are non-decreasing?

5 Answers 5

13

Letting $i$ correspond to the first digit, $j$ to the second, $k$ to the third and $l$ to the fourth, the number of numbers is $\sum_{l=0}^9 \sum_{k=0}^l \sum_{j=0}^k \sum_{i=0}^j 1$ $= \sum_{l=0}^9 \sum_{k=0}^l \sum_{j=0}^k \binom{j+1}{1}$ $= \sum_{l=0}^9 \sum_{k=0}^l \binom{k+2}{2}$ $= \sum_{l=0}^9 \binom{l+3}{3}$ $= \binom{9+4}{4} = 715$

  • 0
    OK now I understand. Thank you. – 2012-06-16
11

Let the four digits be $d_1,d_2,d_3$, and $d_4$ from left to right. Let $a_1=d_1,a_2=d_2-d_1,a_3=d_3-d_2$, $a_4=d_4-d_3$, and $a_5=9-d_4$. Note that each non-decreasing four-digit number corresponds to a unique $5$-tuple $\langle a_1,a_2,a_3,a_4,a_5\rangle$ of non-negative integers such that $a_1+a_2+a_3+a_4+a_5=9$ and vice versa: given such a $5$-tuple, we can recover the number because $d_1=a_1,d_2=a_1+a_2$, $d_3=a_1+a_2+a_3$, and $d_4=a_1+a_2+a_3+a_4$. (The fifth number, $a_5$, merely serves to ensure that the total is a known number.)

The problem of counting non-negative integer solutions is a standard stars-and-bars problem. The Wikipedia article gives a decent explanation of the reasoning involved; the answer is $\binom{9+5-1}{5-1}=\binom{13}4=715\;.$

  • 0
    @N.S.: You could look at it that way, though it’s not how I think of it: I think of it as counting the number of ways to distribute $9$ identical marbles among $5$ distinguishable boxes. – 2012-06-16
4

There are 10!/(4!*6!) = 210 to get 4 different numbers

There are 3* [10!/(3!*7!)] =3*120 =360 to get 3 differnt numbers with 1 repeating

There are 10!/(2!*8!) = 45 to get 2 differnt numbers with each repeating

There are 2* [10!/(2!*8!) ] = 2*45 =90 to get 2 different numbers with 1 repeating 3 times

There are 10 ways to get 1 number repeating 4 times

210 +360 +45 +90 +10 = 715

  • 0
    your method is the best to understand but i needed a formula for direct computation – 2012-06-16