A token moves on the integer grid from (0,0) to (7,5) using only unit…

Question

A token moves on the integer grid from (0,0) to (7,5) using only unit steps Right (+1 in x) and Up (+1 in y). How many such monotone lattice paths avoid passing through BOTH of the points (3,3) and (5,2) (a path is excluded if it touches either point)?

Accepted Answer

Total monotone paths from (0,0) to (7,5): C(12,5) = 792.

Let A = paths through (3,3): C(6,3)*C(6,2) = 20*15 = 300. Wait check: from (0,0) to (3,3) is C(6,3)=20; from (3,3) to (7,5) needs 4 R and 2 U = C(6,2)=15, so A = 300.

Let B = paths through (5,2): from (0,0) to (5,2) is C(7,2)=21; from (5,2) to (7,5) needs 2 R and 3 U = C(5,2)=10, so B = 210.

Paths through both, in order (3,3) then (5,2): note (5,2) has smaller y than (3,3), so it is impossible to pass (3,3) then reach (5,2) (y cannot decrease). Going (5,2) first then (3,3) also needs y to increase from 2 to 3 but x to drop 5->3, impossible. So A∩B = 0.

Valid = Total - A - B + A∩B = 792 - 300 - 210 + 0 = 282. (The code's AB term is 0 because the segment from (3,3) to (5,2) is non-monotone.)

Final answer: 282

A token moves on the integer grid from (0,0) to (7,5) using only unit…

Stuck on a problem like this?