# Number of all of finite monotone sequences

Let $X = \{1, 2,\ldots ,n\}, n\in\mathbb{N}$. Find the number of $f: X\to X$ such that $f$ is monotone i.e $$i<j\Longrightarrow f(i)\leq f(j)$$

Put another way, find the number of monotone finite sequences. Counting them is so painful even for $n=5$, lest the beginning is easy...

If $f(1)=5$, there's only one way: $f(j)=5$ for every $j$.
If $f(1) = 4$, then it starts to depend on subsequent choices. $f$ doesn't even have to be onto.

This will clearly be a headache, so I was hoping to make the reasoning inductive/recursive (somehow).
If $1\mapsto 5$, 1 possibility.

If $1\mapsto 4$, then we allow $f(2)\in\{4,5\}$
Since we have ($k$) four elements left to map, we get a total of $5$ possibilities of doing so [counted manually from diagram]. ($k+1$?).

If $1\mapsto 3$ and $2\mapsto 5$, 1 possibility.
If $1\mapsto 3$ and $2\mapsto 4$, then $f(3)\in\{4,5\}$. $4$ possibilities by hypothesis (result, perhaps?).
If $1\mapsto 3$ and $2\mapsto 3$, then $f(3)\in\{3,4,5\}$:

Lost hope at this point. I can apply the result for set with 2 elements recursively, but would still need to recompute possibilities for set with $3$ elements and then $4$ el etc$\ldots$

Are there any tips/hints on how to, perhaps, simplify the counting?

• Hint: take $f(0) = 1, f(n+1) = n$, then there are $n-1$ increases in value which can be placed in $n+1$ different places... – Abstraction Sep 6 '16 at 12:05

## 2 Answers

Hint There is a bijection between your set and the set fo strictly increasing functions $g: \{1,2,.., n\} \to \{2,3,.., 2n\}$ which are strictly increasing given by $$g(k)=f(k)+k$$

• Suppose $f(k)+k = f(m)+m$, why is this one-to-one? – Alvin Lepik Sep 6 '16 at 12:33
• @AlvinLepik If $k <m$ then $f(k) \leq f(m)$ and hence $f(k)+k < f(m)+m$. They cannot be equal. – N. S. Sep 6 '16 at 14:28

Given $n$ numbers chosen from $\{1,...,n\}$ there is only one way to put them in monotone increasing order. Hence there is a bijection between the set of functions $f$ you're looking for and the number of size $n$ subsets of $\{1,...,n\}$ with repeats allowed.

Hence the answer is

$${2n-1 \choose n}.$$