A few weeks ago, I found an old physics book on a colleague’s “miscellaneous” shelf: University of Chicago Graduate Problems in Physics, by Cronin, Greenberg and Telegdi (Addison-Wesley, 1967). It looked like fun, so I started working through some of it.

Physics problems age irregularly. Topics fall out of vogue as the frontier of knowledge moves on, and sometimes, the cultural milieu of the time when the problem was written pokes through. Take the first problem in the “statistical physics” chapter. It begins, “A young man, who lives at location $A$ of the city street plan shown in the figure, walks daily to the home of his fiancee…”

No, no, no, that just won’t do any more. Let us set up the problem properly:

Asami is meeting Korra for lunch downtown. Korra is $E$ blocks east and $N$ blocks north of Asami, on the rectangular street grid of downtown Republic City. Because Asami is eager to meet Korra, her path never doubles back. That is, each move Asami takes must bring her closer to Korra on the street grid. How many different routes can Asami take to meet Korra?

Solution below the fold.

Asami must traverse a total of $E + N$ block edges. At each intersection, she must choose whether to move east or to move north, unless she is on the same street as Korra, at which point she keeps going in a straight line along that street. Her path can be represented as a string of ns and es, of total length $E + N$ characters. The question is how many different ways such a string can be written. That is, given a total of $E + N$ slots, how many ways can we pick a subset of $E$ of them to fill with es?

Phrasing the problem this way, we see that it’s a job for binomial coefficients. The number of ways to pick $K$ things out of a set of $M$ items is
$$ \binom{M}{K} = \frac{M!}{K!(M-K)!}. $$
This is one of the more enthusiastic formulas that one encounters in everyday mathematics. The factorial $M!$ of a positive integer $M$ is the product of $M$ with $M – 1$ and $M – 2$ and so on, down to 1:
$$ M! = M(M-1) \cdots 1. $$
If we ever find ourselves needing to take the factorial of 0, we use the special rule that $0! = 1$. The factorial operation counts the number of ways to arrange $M$ items in a line. The special rule $0! = 1$ amounts to saying that if we have no items, there’s only one possible way to order them, i.e., do nothing, because it’s all we can do!

Here, we need the number of ways to pick $E$ items out of a set of size $E + N$, which is
$$ \binom{E+N}{E} = \frac{(E+N)!}{E!\,N!}. $$
Note that we would have gotten the same answer if we decided to pick $N$ items out of $E + N$.

This is what the problem asked us to find, so we’ll repeat it and put it in a box:
$$ \boxed{\binom{E+N}{E} = \frac{(E+N)!}{E!\,N!}.} $$

It’s good practice to check the “limiting cases” of a solution. If we derive a complicated formula which applies across a wide swath of scenarios, and if we have an answer we trust for a special case, then we should check that our complicated calculation gives the right answer for that special case. Here, we know that if Korra and Asami start off on the same street, there’s only one path which meets the “never doubling back” criterion. In such a situation, either $N = 0$ or $E = 0$. Let’s plug that into our boxed equation:
$$ \frac{(E+0)!}{E! \cdot 0!} = \frac{E!}{E! \cdot 1} = 1. $$
Simple enough!

Likewise, if the initial configuration has Korra one block north and one block east of Asami, then it’s pretty plain that Asami has two possible paths that she can take: she can go north-and-then-east, or she can travel east-and-then-north. Here, $E = N = 1$, and our formula says
$$ \frac{(E+N)!}{E!\,N!} = \frac{2!}{1!\, 1!} = 2. $$

The figure in the Chicago book gives for specific numbers $E = 3$ and $N = 4$. Plugging these in, we find
$$ \frac{(E+N)!}{E!\,N!} = \frac{7!}{3!\, 4!} = \frac{7\cdot6\cdot5\cdot4\cdot3\cdot2}{3\cdot2\cdot4\cdot3\cdot2}
= 7 \cdot 5 = 35. $$