With rectangular axes of coordinates, the number of paths from (1,1) to (8,10)…
2023
With rectangular axes of coordinates, the number of paths from (1,1) to (8,10) via (4,6), where each step from any point (x,y) is either to (x,y+1) or to (x+1,y) is
- A.
2998
- B.
3947
- C.
3920
- D.
4798
Show answer & explanation
Correct answer: C
In a grid where every step moves either one unit right (R) or one unit up (U), the number of distinct monotonic paths between two points equals the number of ways to arrange the required R's and U's in sequence — given by the combination formula C(m + n, m), where m is the horizontal distance and n is the vertical distance between the two points. When a path must pass through a fixed intermediate point, split the journey into two independent segments and multiply their path counts (the multiplication principle): each way of completing the first segment can be paired with every way of completing the second segment to form one complete path.

From (1, 1) to (4, 6): the horizontal distance is 4 − 1 = 3 and the vertical distance is 6 − 1 = 5, so 8 steps are needed in total (3 rights and 5 ups). The number of ways to arrange them is C(8, 3) = 8!/(3! · 5!) = 56.
From (4, 6) to (8, 10): the horizontal distance is 8 − 4 = 4 and the vertical distance is 10 − 6 = 4, so 8 steps are needed in total (4 rights and 4 ups). The number of ways to arrange them is C(8, 4) = 8!/(4! · 4!) = 70.
By the multiplication principle, the total number of paths from (1, 1) to (8, 10) that pass through (4, 6) is the product of the two segment counts: 56 × 70 = 3920.
As a sanity check, an unrestricted path from (1, 1) to (8, 10) (ignoring the intermediate point) would need 7 rights and 9 ups, giving C(16, 7) = 11440 total paths — the restricted count of 3920 is a proper subset of this, which is consistent, since forcing the path through one specific point can only reduce the number of valid routes.