A sequence is non-decreasing if $k_1 \leq k_2 \leq k_3$.
Now I need to find the number of non-decreasing sequences of length-$n$ sequences from $\{1,2,….m\}$
I basically see it as sum of the numbers of strictly increasing sequences plus other sequences.
The number of strictly increasing sequences of length $n$ is ${m \choose n}$ because simply any subset of length $n$ can be arranged to be form exactly one strictly increasing sequence.
However, we don't have repetition of digits when we deal with strictly increasing sequences unlike non-decreasing sequences.
Ok to make sense of it, I choose $n=3,m=4$
So Now I am looking at the non-decreasing sequences of length $3$ from $\{1,2,3,4\}$
We have $$\{1,1,1\},\{2,2,2\},\{3,3,3\},\{4,4,4\}$$
This is all the non-decreasing sequences that consists of only one digit and there are $m$ digits of them as we see which can also be represented as ${m \choose 1}$
Now one can choose $$\{1,1,2\},\{1,1,3\},\{1,1,4\},\{1,2,2\},\{1,3,3\},\{1,4,4\},\{2,2,3\},\{2,2,4\},\{2,3,3\},\{2,4,4\},\{3,3,4\}$$
Now this is the non-decreasing sequences of length $3$ but that has exactly two digits. In total they are 11 such sequences But what equation is that ?
I want to build a pattern here to arrive to my answer and hopefully generalize it.
Because after this we have the case of non-decreasing sequence of $3$ digits which is basically the same number as the strictly increasing sequences which is ${m \choose n} = {4 \choose 3} = 4$
and then we add everything together, So I guess there must be a summation formula which answers this question.
So the answer for the special case when $n=3,m=4$ should be
${4
\choose 1} + $ something $ + {4 \choose 3}$ and this something should be equal to $11$ if I got this right
Best Answer
Let $x_i$ be the number of times the digit $i$ appears in the sequence, for $1\le i\le m$.
Then the sequence is determined by the values of the $x_i$ since it is non-decreasing, and
$\hspace{.25 in}x_1+\cdots+x_m=n$ with $x_i\ge0$ for each $i$.
Therefore there are $\displaystyle\binom{n+m-1}{n}$ such sequences.
Here is an alternate method based on the ideas of the OP:
Let $j$ be the number of distinct digits in the sequence, where $1\le j\le n$; then
there are $\binom{n}{j}$ ways to choose these digits.
If $y_i$ is the number of times digit $i$ appears in the sequence, then
$\hspace{.15 in}y_1+\cdots+y_j=n$ where $y_i\ge1$ for each $i$.
Therefore there are $\binom{n-1}{j-1}$ ways to select the $y_i$, so there are a total of
$\hspace{ .3 in}\displaystyle\sum_{j=1}^{n}\binom{m}{j}\binom{n-1}{j-1}=\binom{n+m-1}{n}$ such sequences.