# Finding the number of non-decreasing sequences.

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

• possible duplicate of Number of Non - Decreasing functions? Commented Sep 22, 2015 at 17:58
• I think you omitted {3,4,4}. Commented Sep 22, 2015 at 22:48

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)

I would also link it to this problem. It is, in effect, counting the number of non-decreasing functions from a set $$A$$ such that $$\|A\|=r$$ to a set $$B$$, with $$\|B\|=n$$, with $$r.