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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ How do you know that this is the answer? $\endgroup$– PhiraCommented Jan 5, 2014 at 10:25
-
1$\begingroup$ Also have a look at this question: math.stackexchange.com/questions/73330/… $\endgroup$– PhiraCommented Jan 5, 2014 at 10:25
-
1$\begingroup$ Also see here math.stackexchange.com/questions/159210/non-decreasing-digits $\endgroup$– mathloveCommented Jan 5, 2014 at 10:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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}$.
-
$\begingroup$ if the number is, for example, 22222 where are the lines placed? $\endgroup$– foxneSsCommented Oct 29, 2015 at 16:41
-
$\begingroup$ @foxneSs it would just be |d1 d2 d3 d4 d5||||||| $\endgroup$– StephenCommented Jan 18, 2017 at 21:17
-
$\begingroup$ a book I am solving combinatorics problems from used your solution. $\endgroup$ Commented Aug 27, 2021 at 12:44
-
$\begingroup$
$\endgroup$
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}
$$
