Number of non decreasing sequences of length $M$ How many non decreasing sequences are there of length $M$, provided the number in the sequences are allowed from $1,2,3,...,N$?
 A: Elaborating user2255279's answer:
For $k=1,2,3 \cdots N$, let $k$ appear $n_k$ number of times in a particular allowed $M$ length sequence.
Since we want the $M$ length sequence to be non decreasing, $n_1$ number of $1$s have to appear at the start of the sequence, followed by $n_2$ number of $2$s and so on. Thus the set of numbers $n_k$ uniquely determines an allowed sequence.
So it remains to count the number of sets of allowed $n_k$s. The only constraint is the length of the sequence is $M$.
Therefore the number of non-negative integer solutions to $n_1 + n_2 + \cdots + n_N = M$ is the answer to your question. By stars and bars, the answer is $\binom{N+M-1}{M}$.
Abhra Abir Kundu's answer matches the above if you write $\dbinom{M-1}{r-1}$ as $\dbinom{M-1}{M - r}$ and then use Vandermonde's identity.
Cheers!
A: The answer is $\displaystyle \sum_{r=1}^{M}{N \choose r}{M-1 \choose r-1}$
Reason as hints:
Hint 1:How many distinct numbers can be there?Can it be $>$ M ?
Hint 2:Consider you select some $M$ numbers from the given set .How many distinct sequences can be formed with it?
Hint 3:For each set of distinct $r$ numbers with $(r\le ...)$ how many $M$ termed sequences can you form out of this $r$ distinct numbers.(Let $p_1,p_2,\dots p_r$ be the selected numbers and let each $p_i$ occur $x_i\ge 1$ times then we have $x_i+x_2+x_3\dots +x_r=M$.Now think of the number solutions of this equation.)
We also have,
$\displaystyle \sum_{r=1}^{M}{N \choose r}{M-1 \choose r-1}={N+M-1 \choose N-1}={N+M-1 \choose M}$(why?)
A: Hint: Instead of $a_n$, consider $b_n=n+a_n$
A: Okay this was easy!
Number of ways form one to one correspondence with the solutions of 
x1 + x2 + .... + xN = M.
