Yreka, California, being a town founded by mathematicians...?

Question

Yreka, California, being a town founded by mathematicians, is a town with East-West streets numbered 1 through n and North-South Avenues numbered 1 through m. A taxi cab picks you up at the corner of 1st Avenue and 1st street, and you wish to be dropped off at the corner of mth avenue and nth street. Since you are a smart student, you are obviously not going to permit the cab driver to drive longer than the necessary (n − 1) + (m − 1) blocks and charge you more than the minimum fare.
In other words, the cabby must always be increasing his street number or his avenue number. Suppose there is an accident at the intersection of street i and avenue j, for some i,j where 1 < i < n and 1 < j < m. How many routes can the cab driver take to get you to your destination while avoiding the intersection with the accident? Justify your answer.

Answer 1

Let the street intersection points be lattice points (integer coordinates) on a coordinate system. In a nutshell, we have to find the number of paths from (1,1) to (n,m) that do not go through (i,j). We can do this by taking a complementary counting approach, namely by counting the total number of paths from (1,1) to (n,m) and subtracting the number of paths that do go through (i,j).

First let's count the number of paths between (1,1) to (n,m). We know that we must move n-1 blocks to the right and m-1 blocks up. Let's represent a move rightward by "R" and a move upward by "U." Then we count the number of rearrangements of a sequence of n-1 R's and m-1 U's

RRR....RRRUUU...UU (use your imagination to see that we have n-1 R's and m-1 U's).

This is just a combination problem with a result of (n-1+m-1)C(n-1) = (n+m-2)C(n-1) where aCb reads "a choose b."

Now let's count the number of paths through (i,j). We can break this up into two parts: (1) count the number of paths from (1,1) to (i,j) and (2) count the number of paths from (i,j) to (n,m). From our insights above we can similarly determine these (I'll leave the details to you)

(1) (i+j-2)C(i-1) and
(2) (n-i+m-j)C(n-i).

From this we determine that the number of paths from (1,1) to (n,m) through (i,j) is just (1)*(2) = (i+j-2)C(i-1)*(n-i+m-j)C(n-i). Then our final answer (n+m-2)C(n-1) - [(i+j-2)C(i-1) * (n-i+m-j)C(n-i)].

Answer 2

Let P(a,b)=the number of valid paths from (1,1) to (a,b), where (a,b) represents the corner of street a and avenue b.
Then P(a,b)=P(a-1,b)+P(a,b-1) with P(a,1)=1 and P(1,b)=1. This implies P(a,b)=choose(a+b-2,b-1). Next, the number of valid paths to (m,n) that do not pass through (i,j) is P(m,n)-P(i,j)*P(m-i+1,n-j+1)
=
choose(m+n-2,n-1)
-choose(i+j-2,j-1)*choose(m-i+n-j,n-j)
where
choose(x,y) is defined to be x!/y!/(x-y)!