PnC - Number of Routes Problem

"Where there's a will, there's a way". Well we certainly have the will and we surely are going to find the way today. Another interesting type of problem that appears sometimes in MBA examinations is the number of valid paths or the number of routes problem. Let me take your through the two approaches with the help of the example shown in the above image.

We have here a park with a red cemented area in the middle which can't be trespassed. We need to go from point A to point B.

Approach 1 :
Number of paths from point (x1,y1) to (x2,y2) is given by
[(x2 - x1) + (y2 - y1)]! / (x2 - x1)! * (y2 - y1)! A : 0,0
X : 3,2
B : 6,4
Total paths(A to B) = (6 + 4)!/6!4! = 10!/6!4!
The path A->X->B is an invalid path as the cemented area can't be trespassed.
Paths from A to X = (3 + 2)!/3!2! = 5!/3!2!
Paths from X to B : (3 + 2)/!3!2! = 5!/3!2!

Total number of valid paths = Total - (Arrangements for A->X->B)
= 10!/6!4! - ((5!/3!2!) * (5!/3!2!))
= 210 - 10*10 = 110.

Approach 2 :
I will illustrate the concept for a smaller grid and you can extend it to our problem to match the answer with approach 1.Only way to reach point B is through M and N. So total number of routes from A to B can be seen as sum total of number of routes from A to M and number of routes from A to N. Same is true for any point on grid with total routes from origin point being equal to sum of number of routes from origin to the two points(left and bottom) to the destination point.

So, we use this approach to find total paths from A to B in our original image and we find A->X->B path's total number of routes and follow the same Total - Invalid paths formula to get the same answer as by Approach 1.
Usage of either approache is as per your convenience and comfort level. Knowing both of them obviously gives you an extra edge.

I hope you have been able to find your "way" through the grid and reached your destination point with this journey. Leave comments for any doubts or reviews.

Rate,Like and Share the blog and the article if you find it useful.

Cheers!
AS