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.

For great diagrams relating to the Catalan number and the number of monotonic paths not crossing the diagonal, see this: http://en.wikipedia.org/wiki/Catalan_number#Second_proof

So why is the number of monotonic paths not crossing the diagonal the Catalan number?

I understand that through the "reflection method", we arrive at $2n \choose n$ - $2n \choose n-1$ which is indeed the definition of the Catalan number.

However, a definition of the Catalan number is also given by the recurrence relation: $C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0$

Can anyone point out a way to intuitively visualize the solution for the number of monotonic paths not crossing the diagonal in terms of this recurrence relation instead of the explicit formula of the "reflection method" above?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Sorry for pictures like that but...

Lets denote C as the point, where our good path touched diagonal the last time. enter image description here

Lets put good paths to the sets according to their points $C(m,m)$. We have $C(0,0),\dots,C(n-1,n-1)$. How many paths belong to the set of point $C(m,m)$?

enter image description here

There are $P_m$ ways to go to the point $C(m,m)$. We know that for the rest part of the path we wont touch the diagonal anymore, so that means that our path lies under the line DE. Which means, that for the rest part of the path we have $P_{n-(m+1)}$ ways to do that. So the group of $C(m,m)$ consists of $P_m\cdot P_{n-(m+1)}$ good paths. We may take $m=0,\dots,n-1$ and then the sum of all possible paths is $\sum_{m=0}^{n-1}P_m\cdot P_{n-m-1}=P_n$

share|improve this answer
    
Wow this is fantastic. Thank you for going to the trouble of drawing the diagrams. This is such a neat way to visualize the problem. –  hollow7 Mar 25 '12 at 19:02

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.