Counting Lattice Paths

How many distinct routes are there from the bottom-left corner to the top-right corner of a 4-by-3 grid, moving only right or up along the grid lines, one unit at a time? Trying to draw and count every path by hand is slow and error-prone, and the grid could easily be much bigger. But every such route has an unavoidable structure hiding underneath: it's always exactly 4 rightward moves and 3 upward moves, in some order — and counting orderings is exactly what a binomial coefficient does.

The idea: a path is just a sequence of R's and U's

To go from $(0,0)$ to $(m,n)$ moving only right (R) or up (U), any valid path is a string of exactly $m$ R's and $n$ U's, and every arrangement of those letters corresponds to exactly one path — reading the string left to right tells you the move order. So the number of paths equals the number of ways to arrange $m$ R's and $n$ U's in a row, which is the number of ways to choose which $n$ of the $m+n$ total positions are U's:

$$\binom{m+n}{n} = \frac{(m+n)!}{m!\,n!} .$$

In plain English: once you fix how many total steps there are and how many of them go up, a path is fully determined by which steps are the up-moves, and counting subsets is exactly what the binomial coefficient was built for.

Worked example 1: the 4-by-3 grid

From $(0,0)$ to $(4,3)$ needs 4 R's and 3 U's, 7 steps total. The number of distinct orderings is $\binom{7}{3} = \dfrac{7!}{4!\,3!} = \dfrac{5040}{24\times6} = \dfrac{5040}{144} = 35$. There are 35 distinct routes — confirmable on a small grid by Pascal's-triangle-style counting (the number of ways to reach each intersection is the sum of the ways to reach the intersection below and the one to its left), but the binomial coefficient gets there in one step for grids far too large to enumerate by hand.

Worked example 2: paths through a required checkpoint

How many paths from $(0,0)$ to $(4,3)$ pass through the point $(2,1)$? Split the trip into two independent legs: $(0,0)\to(2,1)$ needs 2 R's and 1 U, giving $\binom{3}{1}=3$ paths; $(2,1)\to(4,3)$ needs 2 more R's and 2 more U's, giving $\binom{4}{2}=6$ paths. Since any first-leg path can be combined with any second-leg path, the total is $3\times6=18$ — a multiplication rule, not an addition, because the two choices (how to get to the checkpoint, and how to leave it) are made independently. Note $18 < 35$: about half of all paths happen to pass through this particular checkpoint.