Mathwords logoMathwords

Lattice Path — Definition, Formula & Example

A lattice path is a route across a grid that moves from one integer point to another using only fixed unit steps, most often one unit right or one unit up. Counting how many such routes exist is a classic counting problem.

A lattice path from (0,0)(0,0) to (m,n)(m,n) with step set S={(1,0),(0,1)}S=\{(1,0),(0,1)\} is a sequence of lattice points P0=(0,0),P1,…,Pm+n=(m,n)P_0=(0,0), P_1, \dots, P_{m+n}=(m,n) in Z2\mathbb{Z}^2 such that each difference Pi−Pi−1P_i - P_{i-1} belongs to SS. Each such path corresponds to exactly one arrangement of mm R's and nn U's, so the number of paths is (m+nm)\binom{m+n}{m}.

Key Formula

#paths from (0,0) to (m,n)=(m+nm)=(m+n)!m! n!\#\text{paths from }(0,0)\text{ to }(m,n) = \binom{m+n}{m} = \frac{(m+n)!}{m!\,n!}
Where:
  • mm = number of right steps (horizontal distance)
  • nn = number of up steps (vertical distance)
  • (m+nm)\binom{m+n}{m} = binomial coefficient: ways to choose which of the m + n steps go right

Worked Example

Problem: Your town's streets form a grid. Your home is 4 blocks west and 3 blocks south of the library. You walk only east or north along streets. (a) How many shortest routes are there? (b) How many of them pass the corner that is 2 blocks east and 1 block north of your home?
Step 1: Every shortest route uses exactly 4 east steps (E) and 3 north steps (N), for 7 steps in total. A route is just a string of 4 E's and 3 N's.
4+3=7 steps4 + 3 = 7 \text{ steps}
Step 2: Choose which 3 of the 7 positions are N steps. The other 4 positions are automatically E.
(73)=7!3! 4!=35\binom{7}{3} = \frac{7!}{3!\,4!} = 35
Step 3: For part (b), split each route at the corner (2,1)(2,1). Count routes from home to the corner, then routes from the corner to the library, and multiply.
(31)⋅(42)=3⋅6=18\binom{3}{1}\cdot\binom{4}{2} = 3 \cdot 6 = 18
Answer: (a) There are 35 shortest routes. (b) 18 of them pass through the corner 2 blocks east and 1 block north.

Why It Matters

Lattice paths explain why Pascal's triangle works: the entry (m+nm)\binom{m+n}{m} counts the paths to the point (m,n)(m,n). Restricted versions lead to the Catalan numbers. For example, the paths from (0,0)(0,0) to (3,3)(3,3) that never rise above the line y=xy=x number 14(63)=5\frac{1}{4}\binom{6}{3}=5. These counts reappear in combinatorics courses, random-walk probability, and the grid-based sequence alignment used in bioinformatics.

Common Mistakes

Mistake: Counting grid lines or intersections instead of steps. On a grid 4 blocks wide and 3 blocks tall, students often use 5 and 4 because there are 5 vertical and 4 horizontal street lines.
Correction: Use the number of unit steps, which is the number of blocks: m=4m=4 and n=3n=3. The count is (73)=35\binom{7}{3}=35, not (94)\binom{9}{4}.

Related Terms

  • Lattice — Defines the integer grid points a lattice path visits
  • Graph Path — General path idea; lattice paths are paths on grid graphs
  • Discrete Mathematics — Field where lattice path counting is a core technique
  • Combinatorics — Branch of math that covers counting routes like these
  • Catalan Number — Counts lattice paths that never rise above the diagonal
  • Combination — Choosing which of the m + n steps go right gives the path count
  • Pascal's Triangle — Each entry counts the lattice paths to one grid point