Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 1

up vote 5 down vote accepted

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.

share|improve this answer
    
+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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.