# Given positive interger N, now many non-decreasing sequences of length

1. Jan 4, 2010

### Dragonfall

Given positive interger N, now many non-decreasing sequences of length N are there whose entries are less than N?

2. Jan 4, 2010

### matticus

Re: Sequence

are the entries positive integers?

3. Jan 4, 2010

Yes .

4. Jan 4, 2010

### rasmhop

Re: Sequence

This isn't in the homework section so I'm assuming it isn't homework.

Let A be the set of sequences of the type in the post.
Let B be the set of sequences of N+1 non-negative integers with sum N-2.
A and B are in bijection by associating a sequence $a_1,a_2, \ldots ,a_N$ of A to $b_1,b_2,\ldots,b_{N+1}$ defined by $b_i = a_i - a_{i-1}$ where we let $a_0 = 1, a_{N+1}=N$. The inverse is given by associating a sequence $b_1,b_2,\ldots,b_{N+1}$ of B to $a_1,\ldots,a_N$ defined by $a_{i+1} = a_{i}+b_{i+1}$ where we let $a_0 = 1$.

Thus we can just count B which has
$$\binom{(N+1)+(N-2)-1}{(N+1)-1} = \binom{2N-2}{N}$$
elements.

5. Jan 5, 2010

### Dragonfall

Re: Sequence

Wow I would never have thought of that. Thanks. Unfortunately it grows too fast for my purposes.