Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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

share|improve this answer
    
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

Your Answer

 
discard

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.