In: Statistics and Probability
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)?
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.