Question

A young man walks daily through a gridded city section to visit his girlfriend, who lives m blocks East and n blocks North of where the young man resides. Because the young man is anxious to see his girlfriend, his route to her never doubles back—he always approaches her location. In terms of m and n, how many different routes are there for the young man to take?

Answer 1

The number of distinct possibilities is the same as counting the number of ways we can place N=m+n objects, m of one type and n of other in m+n places.

1st place can be occupied in any of N ways

2nd place can be occupied in any of N-1 ways

3rd place can be occupied in any of N-2 ways

.

.

.

N-1th place can be occupied in only 2 ways

and the Nth place can be occupied in only 1 way.

So, All the available places can be occupied in

  ways

This analysis doesn’t take into account the fact that there are only 2 distinguishable kinds of objects: m of the 1st type & n of the 2nd type. All m! possible permutations of the 1st type of object lead to exactly the same N! possible arrangements of the objects. Similarly, all n! possible permutations of the 2nd type of object also lead to exactly the same N! arrangements.

So, we need to divide the result by m!n!

So, the number of distinct ways in which N objects can be arranged with m of the 1st type & n of the 2nd type is

This is the same as the total number of ways the man can reach his girlfriend.