As in title, how to determine the number of nondecreasing functions $f:\{1,2, \ldots, n\} \to \{1,2, \ldots, n\}$ such that $f(i)\leq i$, for all $i \in \{1,2, \ldots, n\} $?
I know that there is in general ${2n-1}\choose{n-1}$ nondecreasing functions.
I also have tried to solve the problem for small n's:
For n=1 we have one such function, for n=2 we have two such functions and for n=3 we have five such functions.
If we list all the possible values that functions can take for $n=3$, we see that there are as many functions as paths connecting all the columns's, for example f(1)=1, f(2)=2, f(3)=3. Starting with f(3)=3, at each step we can go "left" and "down" or remain "at the same level" but we cannot go "up", because then the function would be decreasing.
$f(1)=1$
$f(1)=2$ $f(2)=2$
$f(1)=3$ $f(2)=3$ $f(3)=3$
Having that said we can count how many nondecreasing sequences of the form $(a_1, a_2, \ldots, a_n)$ we have such that $a_i = f(i)$.
These are just the Catalan numbers. Plot points in the $n\times n$ grid, with coordinates $(i, f(i))$. Then connect the bottom-left corner to the upper-right corner by going through the points (and never going above the diagonal).
In this picture, the yellow line represents the function: $$ f(1) = 1, f(2) = 1, f(3) = 2 $$ and the blue line represents the function $$ f(1) = 1, f(2) = 2, f(3) = 2 $$
[Green is where they overlap.]
The Catalan numbers count the number of paths below the diagonal. And the points you've plotted uniquely identify such a path.