# The number of non-decreasing sequences of digits

What's the numer of n-digit natural numbers, in which digits are in non-decreasing order?

I know the answer is $n+8 \choose 8$, but I don't understand how to get this score - could anyone try to explain it to me?

Sure.

First, the digit "0" can't appear in the number. If it appeared, it would have to appear first, but then the number wouldn't be an n digit number.

So we have a non-decreasing sequence of digits, $d_1,d_2, ... ,d_n$, all of whom belong to the set $\{1, ... ,9\}$. To specify such a sequence, it is sufficient to say where the $1$'s end and the $2$'s start, where the $2$'s end and the $3$'s start, and so on. Now, imagine that we have $8$ lines that we can place between the digits. The digits up to the first line are $1$, the digits between the first and second lines are $2$, and so on. Thus, the arrangement $$d_1 d_2 \vert \vert d_3 \vert d_4 d_5 d_6 \vert d_7 \vert d_8 \vert d_9 d_{10} d_{11} \vert d_{12} \vert d_{13}$$
corresponds to the thirteen digit number $$1134445677789 .$$ In how many ways can we place 8 lines between $n$ digits? Well, we just need to choose $8$ spots out of $n+8$ posible locations, so the answer is $\binom{n+8}{8}$.

• if the number is, for example, 22222 where are the lines placed? – foxneSs Oct 29 '15 at 16:41
• @foxneSs it would just be |d1 d2 d3 d4 d5||||||| – Lucas Jan 18 '17 at 21:17

The digit $0$ can appear in the number only if $n$ is equal to $1$. So, if $n=1$, then the answer is $10$ different numbers. If $n>1$, then the numbers can contain only digits from set $A = \{1,2, ... ,8,9\}$. $0$ cant't appear in the number when $n>1$ becouse you couldn't then construct n-digit natural number, in which digits are in non-decreasing order.
Let's focus on the situation where $n > 1$. So, we have non-decreasing n-digit number $a = d_1d_2 ... d_{n - 1}d_{n}$, where the digits are elements of the set $A = \{1,2, ... ,8,9\}$. The numer of n-digit natural numbers, in which digits are in non-decreasing order is a $n$-combination with repeated elements chosen within the set $A$. Why? Because if you just take any $n$-combination with repeated elements from the set $A$ (for example, $\{2,4,4,2,5\}$) and sort it ascending then you will get one of the desired number ($\{2,2,4,4,5\}$). Each combination represents exactly one searched number. Thus, Simply find the total number of $n$-combination with repeated elements from the set $A$.

The number $C^{{\prime}}_{{a,n}}$ of the $n$-combinations with repeated elements within $a$-element set is given by the formula: $$C^{{\prime}}_{{a,n}}=\binom{a+n-1}{n}.$$ Thus, for $n>1$ the solution is equal to the number of: $$C^{{\prime}}_{{9,n}}=\binom{9+n-1}{n}=\binom{n+8}{n}.$$ Widely known is the following rule : $$\binom{m}{k}=\binom{m}{m-k}.$$ Using the given above rule let's give final answer for $n>1$: $$\binom{n+8}{n}=\binom{n+8}{n+8 -n}=\binom{n+8}{8}$$