4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Abstraction Sep 6 '16 at 12:05
1
$\begingroup$

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

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

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}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.