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).