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?
number of ways to travel on L-shaped grid
2
$\begingroup$
combinatorics
1 Answers
0
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}$
-
1I 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 – 2012-12-09