Question

Consider a grid with vertices from (0,0) to (20,15), in which edges can only be traversed up or right. Think of a street grid with intersections labelled by pairs of integers, and all one-way streets. At grid point (5,7) there is a forbidden node (e.g. a blocked intersection). How many paths, going only up and right, are there in the grid which do not pass through the forbidden intersection?

Answer 1

Total paths from (0,0) to (20,15) is computed here as:
= (# of permutation of 20 + 15 items ) / Number of permutation of 20 items * Number of permutation of 15 items

= 35! / (20! * 15!)

= 3247943160

Total number of paths which pass through (5, 7)

= Number of paths from (0,0) to (5,7) * Number of paths from (5,7) to (20,15)

= [ (12! / 5! 7! ) * (35 - 12)! / (15-7)!(20-5)! ]

= 12! * 23! / (5! 7! 8! 15! )

= 388328688

Therefore total number of paths which do not pass through the forbidden intersection is computed here as:

= 3247943160 - 388328688

= 2859614472

Therefore there are 2859614472 which do not pass through the forbidden intersection here.