2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Can you explain this with an example please?Suppose N=4 M=4 P=2 K=2. $\endgroup$ – Divya Dec 9 '12 at 10:22
  • 1
    $\begingroup$ 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 $\endgroup$ – Divya Dec 9 '12 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.