# The number of non-decreasing sequences of digits

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

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?

• How do you know that this is the answer? Commented Jan 5, 2014 at 10:25
• Also have a look at this question: math.stackexchange.com/questions/73330/… Commented Jan 5, 2014 at 10:25
• Commented Jan 5, 2014 at 10:27

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? Commented Oct 29, 2015 at 16:41
• @foxneSs it would just be |d1 d2 d3 d4 d5||||||| Commented Jan 18, 2017 at 21:17
• a book I am solving combinatorics problems from used your solution. Commented Aug 27, 2021 at 12:44
• See "stars and bars". Commented Jun 3, 2022 at 22:11

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