# 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

My solution is a bit different from Brian's answer even though I use the same "stars and bar" technique. Let $$d_1d_2d_3d_4$$ be one such number and the range of values for each digit $$d_i$$ will be [0-9]. For any given combination of 4 digits, we always have exactly one non-decreasing number. eg.: 2,5,2,4 has only one combination of non-decreasing number i.e., 2245. So, our problem comes down to simply finding "total number of combinations where 4 digits must be selected from a set of 10 digits (0-9 digits) where each digit can be repeated". For each combination, we have exactly one non-decreasing number. So basically we need to find non-negative integral solutions to the equation $$x_0 + x_1 + ... +x_{9} = 4$$, which turns out to be $$\binom{10+4-1}{10-1}=\binom{13}4=715\;.$$

Here is a simple solution.

It is easy to observe that there is only one permutation of any collection of 4 digits such that it forms a non-decreasing sequence. So, there is a one-to-correspondence between finding the number of required sequences and number of collection of $$4$$ digits (repetition allowed) i.e. choosing $$4$$ out of $$10$$ digits with repetition.

Represinting choices by binary digits. Numbers of $$1$$ represent number of times the digit is choosen;$$0$$ represent switch to next digit.

Number of permutations of $$10101010000000$$ will give all possible choices which is $$13\choose4=715$$