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?


2 Answers 2



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

  • $\begingroup$ if the number is, for example, 22222 where are the lines placed? $\endgroup$
    – foxneSs
    Oct 29, 2015 at 16:41
  • $\begingroup$ @foxneSs it would just be |d1 d2 d3 d4 d5||||||| $\endgroup$
    – Stephen
    Jan 18, 2017 at 21:17
  • $\begingroup$ a book I am solving combinatorics problems from used your solution. $\endgroup$ Aug 27, 2021 at 12:44
  • $\begingroup$ See "stars and bars". $\endgroup$
    – rogerl
    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} $$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .