# 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
add comment

## 1 Answer

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.

If you look at the pictures of the monotonic paths, you can see a clear correspondence with nondecreasing functions.

Catalan numbers also count certain rooted trees, which may be what you were getting at in the later part of your question.

-
+1. I was typing up the same answer, but you beat me to it! –  Mike Spivey Sep 18 '11 at 22:29
@Mike Now I feel a little selfish for trying to post my answer as quickly as possible. –  Rahul Sep 19 '11 at 6:21
Don't feel bad - you have a perfectly good answer! –  Mike Spivey Sep 19 '11 at 12:54
add comment