On this page
Grid path questions are standard in Class 11 combinations exercises and in JEE and olympiad practice. Most need one combination; the harder versions add two ideas: multiply for a checkpoint, subtract for a forbidden point. Here is the method, worked on one grid so you can check every number.
How many shortest paths are there on a grid?
Say you start at corner A and must reach corner B, which is 6 blocks to the right and 4 blocks up, moving only right (R) or up (U). Any shortest route uses exactly 10 steps: 6 R and 4 U. A route is just a 10-letter word such as RRRUURRUUR, and choosing a route means choosing which 4 of the 10 positions hold a U.
The number of lattice paths from (0,0) to (a,b) using only east and north steps is the binomial coefficient C(a+b, a), as Wolfram MathWorld states. For our grid that is C(10, 4) = 210.
Two checks on the formula. Project Euler Problem 15 notes that a 2×2 grid has exactly 6 routes from one corner to the opposite one, which is C(4, 2). For a square n×n grid the answer is the central binomial coefficient C(2n, n), listed in OEIS A000984 as 1, 2, 6, 20, 70, 252, … so a 20×20 grid has C(40, 20) = 137,846,528,820 routes.
How do you count paths that pass through a point?
Split the trip at the checkpoint. Put P at (2, 2), that is 2 right and 2 up from A. Every route through P is a route from A to P followed by a route from P to B, so by the multiplication principle:
A to P: 2 R and 2 U, so C(4, 2) = 6
P to B: 4 R and 2 U, so C(6, 2) = 15
Through P: 6 × 15 = 90
How do you count paths that avoid a point?
Use the complement. Routes avoiding P = all routes minus routes through P = 210 − 90 = 120.
With two forbidden points, subtract both and add back the routes you removed twice. This is inclusion-exclusion, the same idea as in three-set Venn diagram problems. Add Q at (4, 3):
Through Q: C(7, 3) × C(3, 1) = 35 × 3 = 105
Through both P and Q: 6 × C(3, 1) × 3 = 6 × 3 × 3 = 54, since P to Q is 2 R and 1 U
Avoiding both: 210 − 90 − 105 + 54 = 69
If one forbidden point sits above and to the left of the other, no route passes through both and the add-back term is 0.
What if squares on the grid are blocked?
When the blocked region is irregular, formulas get messy. Switch to the addition method. The last step into any junction is either an R from the left or a U from below, so:
the count at a junction = the count at the junction to its left + the count at the junction below it
every junction on the bottom row and left column has count 1
a blocked junction has count 0
Without blocks, this table is Pascal's triangle rotated by 135°, as the Wikipedia article on lattice paths notes. Here are the rows for our grid with P blocked, from bottom to top:
1, 1, 1, 1, 1, 1, 1
1, 2, 3, 4, 5, 6, 7
1, 3, 0, 4, 9, 15, 22
1, 4, 4, 8, 17, 32, 54
1, 5, 9, 17, 34, 66, 120
The corner reads 120, the same as the complement method. Block Q too and the table gives 69, matching inclusion-exclusion. If one street between two junctions is closed, skip that one addition. If the question moves from cell to cell, a blocked square is simply a cell with count 0.
A four-step plan for exam questions
Count the right steps and up steps (blocks, not dots). The answer with no conditions is C(right + up, up).
Must pass through a point: multiply the two legs.
Must avoid one or two points: subtract, then add back the routes through both.
Irregular blocks or closed streets: fill in the addition table from the start corner.
If you keep setting up the step counts wrongly, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. If C(n, r) itself still feels shaky, the Fermi Concept Library gives every mathematics concept, the binomial coefficient included, its own lesson and its place in the map.
Rows of Pascal's triangle have useful totals too, covered in sums of binomial coefficients. When streets have different lengths and you want the shortest route itself, see Edsger Dijkstra's shortest path algorithm.
