# The number of functions with a certain property

Let $f$ be chosen uniformly at random from all functions $f:\{1,\ldots,n\}\rightarrow\{1,\ldots,n\}$ such that $f(k)\in\{1,\ldots,k\}$ for $1\leq k\leq n$. What is the probability that $f$ is non-decreasing?

Now, the number of all the function is $n!$ (if I'm not wrong) so I want to know the number of the non-decreasing ones. My approach was to build a rooted tree, in an obvious way such that the number of functions is exactly the number of vertices in the last level. But I'm not able to count this number, could any of you help me? (if you have a different approch is good).

-
You could may be look for a recurrence relation. –  Joel Cohen Sep 18 '11 at 22:09
Since, for all $n$ values of $k$, $f(k) \leq k$, $f(k)$ can take $k$ values, which means there are $1\cdot 2\cdot\dots\cdot n=n!$ such functions. So, you are indeed not wrong on that bit. –  Luke Sep 18 '11 at 22:22

I believe you want the $n$th Catalan number, $$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\mbox{ for }n\ge 0.$$
$C_n$ is the number of monotonic paths along the edges of a grid with $n\times n$ square cells, which do not pass above the diagonal.