---
tag: 040WY0TT2G
kind: concept
name: Lattice path
msc: [05A15]
sources:
  - url: https://en.wikipedia.org/wiki/Lattice_path
    locator: North-East lattice paths
same_as:
  wikidata: Q18888837
  wikipedia: Lattice path
---

## Summary

A lattice path is a finite sequence of points of the integer lattice $\mathbb{Z}^2$. Each step between consecutive points is from a given finite set of steps.
The most common case uses the steps $E = (1, 0)$ and $N = (0, 1)$. These are North-East lattice paths.

A North-East path from $(0, 0)$ to $(a, b)$, with $a, b \in \mathbb{N}$, has $a$ steps $E$ and $b$ steps $N$.
It is a word of length $a + b$ in $E$ and $N$. Thus the number of such paths is the [[binomial coefficient|092GEF38YD]] $\binom{a + b}{a}$.

## Remarks

The number of North-East paths from $(0, 0)$ to $(n, n)$ is the [[central binomial coefficient|01WHD9T0V6]] $\binom{2n}{n}$.
The paths of this type that never go above the diagonal $y = x$ are counted by the [[Catalan numbers|092DRBFKMG]]. They correspond to [[Dyck words|0R9JR0465V]].

## Explanations

### L1 human

Think of a city grid where you may only walk east or north.
To go 3 blocks east and 2 blocks north, you choose which 2 of your 5 steps go north, so there are $\binom{5}{2} = 10$ routes.