Finding the number of non-decreasing sequences.

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.

You can use the bars and stars method to solve this problem. As a matter of fact, you deal with a n bits number (this will correspond to the stars). The bars will correspond to a changement of the value that we place. For example *** | ** |* correspond to 111223. As you can pick up m different values for your sequence , you need m-1 bars to make the necessary switches. You will obtain n+m-1 available places for the bars. Then you just need to select m-1 positions to place the bars. The answer is C(n+m-1, m-1)