6
$\begingroup$

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

  • 0
    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.2011-09-18

1 Answers 1

5

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.

  • 0
    Don't feel bad - you have a perfectly good answer!2011-09-19