Given K numbers $n_1, \, \ldots \,, n_k$ s.t. $0 \leq n_i \leq b$
How many ways are there to write the numbers $n_1$ to $n_k$ such that they are descending. (Descending here is used in the analysis sense)
Given $k=4$ and $b=4$ we could say that:
$0000$ is descending
$3321$ is descending
yet $2321$ is not.
I know this is a combinatorics problem and I have encountered solutions for strictly descending, but not descending.
Thank you in advance for any help.
On
For $n_1$, we can choose any number between $0$ and $b$ (inclusive). For $n_2$, we can choose any number between $0$ and $n_1$ (inclusive), and so forth. This structure suggests dynamic programming.
Let $f(a,b,k)$ be the number of ways to choose a descending a sequence of length $k$ with numbers between $a$ and $b$ (inclusive). By the above argument, $$ f(a,b,k)=\begin{cases} 1 & \text{if }k=0\\ f(a,a,k-1)+f(a,a+1,k-1)\cdots+f(a,b,k-1) & \text{if }k\geq1. \end{cases} $$
Next, note that $f(a,b,k) = f(0,b-a,k)$ and hence it is sufficient to check the case of $a=0$.
Lastly, you can verify that $f(0,b,k) = \binom{b+k}{b}$ by induction.
Notice that such a string is completely determined by how many times each digit appears in the string. For instance, if we have a descending string of length $6$ consisting of three $3$s, two $2$s, and one $1$, then it must be $333221$ since there is only one way to arrange the digits in descending order.
Let's consider the concrete example of the number of strings of length $12$ that can be formed using the decimal digits. Let $x_i$, $0 \leq i \leq 9$, be the number of times the digit $i$ appears in the string of descending decimal digits. Since there are a total of $k$ digits in the string, $$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 12$$ which is an equation in the nonnegative integers. A particular solution of the equation corresponds to the placement of nine addition signs in a row of twelve ones. For instance, $$1 1 + 1 + + + 1 1 1 + 1 + + 1 1 1 1 + 1 +$$ corresponds to the solution $x_0 = 2$, $x_1 = 1$, $x_2 = 0$, $x_3 = 0$, $x_4 = 3$, $x_5 = 1$, $x_6 = 0$, $x_7 = 4$, $x_8 = 1$, $x_9 = 0$ and the string $877775444100$. The number of such solutions is the number of ways we can place nine addition signs in a row of twelve ones, which is $$\binom{12 + 9}{9} = \binom{21}{9}$$ since we must select which $9$ of the $21$ positions required for twelve ones and nine addition signs will be filled with addition signs.
We wish to count the number of descending strings of length $k$ that can be formed with digits no larger than $b$. Let $x_i$, $0 \leq i \leq b$, be the number of times the digit $i$ appears in the string. The number of such strings that can be formed is the number solutions of the equation $$x_0 + x_1 + x_2 + \cdots + x_b = k$$ in the nonnegative integers. A particular solution of this equation requires placing $b$ addition signs in a row of $k$ ones. Therefore, the number of such solutions is $$\binom{k + b}{b}$$ since we must choose which $b$ of the $k + b$ positions required for $k$ ones and $b$ addition signs will be filled with addition signs.