# Counting Number of Walks on a non-rectangular Grid

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 ?

• 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 : http://n1b-algo.blogspot.in/2012/07/number-of-paths-in-rectangular-grid.html, this gives the answer to your the question.
• the Catalan numbers! (for $m=n$) – Hendrik Jan Dec 4 '12 at 0:39