Here is the problem, I have a grid like below,


now i am at the top-left point, and i want to goto bottom right corner point. from a point i can only go to bottom row, or right column, i cannot backtrack. more simply to say that if i am at (r,c) point where r points to row, and c points to column, i can go from (r,c) to (r+1,c) and (r,c+1) only.

Here is a fact, number of row and column can be larger than 100000

Now how many ways to go to the bottom right corner point from the top left corner ?

is there any combinatorial formula ?

  • $\begingroup$ Maybe you can setup an adjacence matrix for your problem and use this answer... $\endgroup$ – draks ... Dec 3 '12 at 11:06

Can you see that this is same as the no. of ways of moving from $(0,0)$ to $(m,n)$ without crossing the line $y=x$ (assuming the size of the grid is $m\times n$ and possible moves are right and up) ?. Look at the problem no. $2$ here : http://n1b-algo.blogspot.in/2012/07/number-of-paths-in-rectangular-grid.html, this gives the answer to your the question.

  • 1
    $\begingroup$ the Catalan numbers! (for $m=n$) $\endgroup$ – Hendrik Jan Dec 4 '12 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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