# number of ways to travel on L-shaped grid

No. of ways to travel from top left to bottom right in a rectangular grid of width N and height M is given by C(N+M,N).What will be the number of ways to travel from top left to bottom right when a rectangular grid of width P and height K is removed from top right corner?

-

## 1 Answer

Let $i$ be the height at which you leave the line $x=i$ to the right. That is, first you travel from $(0,M)$ to $(N-P,i)$, then to go to $(N-P+1,i)$ and then travel from there to $(N,0)$. There are $N+M-P-i\choose i$ possibiliteis for the first part and $P-1+i\choose i$ possibilities for the last part. Adding up, we find $$\sum_{i=0}^{M-K}{N+M-P-i\choose i}{P-1+i\choose i}$$

-
Can you explain this with an example please?Suppose N=4 M=4 P=2 K=2. –  Divya Dec 9 '12 at 10:22
I have tried this but its giving me wrong answer for N=4 M=4 P=2 K=2.your answer gives 29 whereas the correct answer is 53 –  Divya Dec 9 '12 at 12:02