Discrete Math · Undergraduate

Counting Lattice Paths on a Grid

Quick answer

A shortest path on a grid from (0, 0) to (m, n) uses m steps right and n steps up in some order. Choosing which m of the m + n steps go right fixes the path, so there are C(m + n, m) paths. To count paths through a point, multiply the paths to it by the paths from it. To count paths that avoid a point, subtract those from the total. The same count gives shortest taxi routes on a city grid.

What you'll learn

  • Count lattice paths with a binomial coefficient
  • Count paths through a given point
  • Count paths that avoid a point
  • Extend the count to three dimensions

Steps in some order

A lattice path moves along grid lines, one unit right (RR) or up (UU) at a time. Every shortest path from (0,0)(0, 0) to (m,n)(m, n) uses exactly mm RRs and nn UUs. The path to (4,3)(4, 3) below is RRUURRURRUURRU.

paths from (0,0) to (m,n)=(m+nm)\text{paths from } (0, 0) \text{ to } (m, n) = \binom{m + n}{m}
One of the 35 shortest paths from (0, 0) to (4, 3) A grid from (0, 0) to (4, 3). A highlighted path goes right two units, up two, right two and up one, passing through (2, 1). It is one of the 35 shortest paths. 1234123xy start end (2, 1)
One of the 35 shortest paths from (0, 0) to (4, 3)

Why a path is a choice of positions

Write a path as a word of m+nm + n letters. Once we decide which mm positions hold an RR, the rest are UUs and the path is fixed, so paths match one-to-one with ways to choose mm positions from m+nm + n. That is the combination (m+nm)\binom{m + n}{m}. For paths through a point PP, every path splits at PP into a first part and a second part, chosen independently, so the counts multiply.

Worked examples

Common mistakes

Practice problems

  1. Count the paths from (0,0)(0, 0) to (3,3)(3, 3).

    Answer

    2020

    Full solution

    (63)=20\binom{6}{3} = 20.

  2. Count the paths from (0,0)(0, 0) to (5,2)(5, 2).

    Answer

    2121

    Full solution

    (72)=21\binom{7}{2} = 21.

  3. Count the paths from (0,0)(0, 0) to (6,4)(6, 4).

    Answer

    210210

    Full solution

    (104)=210\binom{10}{4} = 210.

  4. Count the paths from (0,0)(0, 0) to (4,4)(4, 4) through (2,2)(2, 2).

    Answer

    3636

    Full solution

    (42)⋅(42)=6⋅6\binom{4}{2} \cdot \binom{4}{2} = 6 \cdot 6.

  5. Count the paths from (0,0)(0, 0) to (4,4)(4, 4) that avoid (2,2)(2, 2).

    Answer

    3434

    Full solution

    (84)−36=70−36\binom{8}{4} - 36 = 70 - 36.

  6. Count the shortest paths from (0,0,0)(0, 0, 0) to (1,1,1)(1, 1, 1) in space.

    Answer

    66

    Full solution

    The three different steps can go in 3!=63! = 6 orders.

  7. A taxi drives 44 blocks east and 22 blocks north on a city grid. How many shortest routes are there?

    Answer

    1515

    Full solution

    (62)=15\binom{6}{2} = 15.

  8. A student counts the paths from (0,0)(0, 0) to (3,2)(3, 2) as 3⋅2=63 \cdot 2 = 6. How many are there?

    Answer

    1010

    Full solution

    (52)=10\binom{5}{2} = 10.

Frequently asked questions

How many lattice paths go from (0, 0) to (m, n)?

C(m + n, m): choose which m of the m + n steps go right.

How do I count paths through a point?

Multiply the number of paths from the start to the point by the number from the point to the end.

How do I count paths that avoid a point?

Subtract the paths through the point from the total.

What about three dimensions?

A path to (a, b, c) has a + b + c steps, and there are (a + b + c)!/(a! b! c!) of them.

What to learn next