Non-Decreasing Digits

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?

-

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$$

-
can you please explain?? i am unable to understand what you did –  Ashhar Jawaid Jun 16 '12 at 20:52
The top equation represents the number of possibilities: all I did is note that each digit is bounded below by zero and bounded above by its neighbour to the right. The remaining steps use the identity $\sum_{j=0}^k \binom{n+j}{n} = \binom{k+n+1}{n+1}$ which you can verify using induction on k. –  Cocopuffs Jun 16 '12 at 21:02
I think you mean $9$ instead of $k$ over the leftmost $\Sigma$ in line $3$. –  Cameron Buie Jun 16 '12 at 21:04
@CameronBuie Fixed, thanks –  Cocopuffs Jun 16 '12 at 21:04
OK now I understand. Thank you. –  Ashhar Jawaid Jun 16 '12 at 21:05

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\;.$$

-
Thanks. Your method is also very good. –  Ashhar Jawaid Jun 16 '12 at 21:10
Nice solution. If I am not mistaken, you basically say that $(a_1,a_2,a_3,a_4) \to (a_1,a_2+1,a_3+2, a_4+3)$ is a bijection between all such four digit numbers and the strictly increasing sequences of four numbers between $0$ and $12$. –  N. S. Jun 16 '12 at 21:28
@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. –  Brian M. Scott Jun 16 '12 at 21:33

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

-
your method is the best to understand but i needed a formula for direct computation –  Ashhar Jawaid Jun 16 '12 at 21:38