### counting monotonic paths

A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards. The above diagrams show the case n = 4:

find a linear solution for possible number of paths for n=k.

find a linear solution for possible number of paths for n=k.

catalan numbers :)

ReplyDeleteCan u plz explain the logic or give certain links to understand that? It will be very helpful.

ReplyDelete@saurabh you can read about catalan numbers

ReplyDeletehttp://en.wikipedia.org/wiki/Catalan_number

he nth Catalan number is given directly in terms of binomial coefficients by

ReplyDeletec(n) = (2n)!/(n+1)! * n!