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$?

Solution 1:

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!

Solution 2:

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?)

Solution 3:

Hint: Instead of $a_n$, consider $b_n=n+a_n$