Question

Consider a grid with vertices from (0,0) to (20,20), 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. How many paths, going only up and right, are there in the grid which do not pass through either forbidden intersection, if: (1) There are forbidden nodes at grid points (12,7) and (7,12)? (2) There are forbidden nodes at grid points (6,6) and (13,13)?

Answer 1

Total paths from (20,20) is computed here as:

= (20 + 20)! / (20! 20!)

= 40! / (20! 20!)

= 137846528820

a) Total paths from (0,0) to (20,20) through (12,7) is computed here as:

= [ (12 + 7)! / 12! 7! ]*[ (40 - 19)! / (20 - 12)! (20 - 7)! ]

= (19! / 12!7!)*(21! / 8!13!)

= 10253454120

Total paths from (0,0) to (20,20) through (7,12) is computed here as:

= [ (12 + 7)! / 12! 7! ]*[ (40 - 19)! / (20 - 12)! (20 - 7)! ]

= (19! / 12!7!)*(21! / 8!13!)

= 10253454120

Note that the person cannot pass through both the points (12,7) and (7,12)

Therefore, the total number of paths required here is computed as:
= 137846528820 - 2*10253454120

= 117339620580

Therefore there are 117339620580 total paths possible here.

b) Total paths from (0,0) to (20,20) through (6,6)

= (12!) / (6!6!) * (28! / 14! 14!)

= 37067738400

Total paths from (0,0) to (20,20) through (13,13)

= (26!) / (13!13!) * (14! / 7! 7!)

= 35694859200

Total paths from (0,0) to (20,20) through both the points (6,6) and (13,13)

= (12!) / (6!6!)*(14! / 7!7!)*(14! / 7! 7!)

= 10883448576

Therefore total number of paths allowed here is computed as:

= Total paths - total paths from (0,0) to (20,20) through (6,6) - Total paths from (0,0) to (20,20) through (13,13) + Total paths from (0,0) to (20,20) through both the points (6,6) and (13,13)

= 137846528820 - 37067738400 - 35694859200 + 10883448576

= 75967379796

Therefore 75967379796 is the required total number of paths allowed here.