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.

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

grid

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 ?

share|improve this question
    
Maybe you can setup an adjacence matrix for your problem and use this answer... –  draks ... Dec 3 '12 at 11:06

1 Answer 1

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.

share|improve this answer
1  
the Catalan numbers! (for $m=n$) –  Hendrik Jan Dec 4 '12 at 0:39

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.