Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
Maybe you can setup an adjacence matrix for your problem and use this answer... – 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 :, this gives the answer to your the question.

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

Your Answer


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.