lattice paths and ballot numbers

A lattice path is a path in ${ℝ}^n$ whose vertices are lattice points in some lattice (for example, points of ${ℝ}^n$ all of whose coordinates are integers). This article considers lattice paths in the plane from $(0,0)$ to $(m,n)$ for $m,n\ge 0$ whose vertices fall on $\mathbb{Z}\times \mathbb{Z}$.

As a warm-up, how many paths altogether are there from $(0,0)$ to $(m,n)$ if we restrict the step sizes to $(1,0)$ and $(0,1)$ (that is, a path can travel only one step north or one step east at a time)? There are $m+n$ steps altogether, and we can choose any $n$ of them to be vertical steps, so the answer is obviously

$$\left(\genfrac{}{}{0pt}{}{m+n}{n}\right)$$

Another way of visualizing the answer is to encode a path as a sequence of $H$’s and $V$’s corresponding to horizontal and vertical steps; the question then is: how many sequences of length $m+n$ are there with exactly $n$ $V$’s? Again, the answer is clearly as above.

Suppose we are interested in paths from $(0,0)$ to $(m,n)$ for $m>n$ that stay strictly below the diagonal (except at the origin)? Note that any such path must start out with a horizontal step, so counting these paths is the same as counting paths from $(1,0)$ to $(m,n)$ that stay strictly below the diagonal. We know how many total paths there are: $\left(\genfrac{}{}{0pt}{}{m+n-1}{n}\right)$ (use the above formula, starting at $(1,0)$ instead of $(0,0)$). We will calculate the number of paths that touch or go above the diagonal, and subtract one from the other.

We can count the number of such unwanted paths by establishing a bijection with something that is easier to count. In fact, the number of paths from $(1,0)$ to $(m,n)$ that touch or cross the diagonal is the same as the total number of paths from $(0,1)$ to $(m,n)$. A bijection can be described as follows. Consider the diagram below:

The red path is one of the unwanted paths which crosses the diagonal. Given such a path, choose the first point at which the path touches the diagonal, and reflect all steps up to that point around the line $x=y$. This gives a path from $(0,1)$ to $(m,n)$; in the diagram, it is the blue path up to the point where the two paths cross, and then it is the same as the red path from that point on.

Clearly reflecting a path twice gives the original path, so the reflection map is injective into paths from $(0,1)$ to $(m,n)$. But also, every path from $(0,1)$ to $(m,n)$ must cross the diagonal at some point, since $m>n$, and thus it is the reflection of some unwanted path from $(1,0)$ to $(m,n)$. So we have established the required bijection.

Now, the total number of paths from $(0,1)$ to $(m,n)$ is $\left({\displaystyle \genfrac{}{}{0pt}{}{m+n-1}{m}}\right)$, so the total number of paths from $(1,0)$ to $(m,n)$ that never touch the diagonal is then

$\left({\displaystyle \genfrac{}{}{0pt}{}{m+n-1}{m-1}}\right)$ $-\left({\displaystyle \genfrac{}{}{0pt}{}{m+n-1}{m}}\right)={\displaystyle \frac{(m+n-1)!}{(m-1)!n!}}-{\displaystyle \frac{(m+n-1)!}{m!(n-1)!}}$

$={\displaystyle \frac{1}{m+n}}\left({\displaystyle \frac{(m+n)!}{(m-1)!n!}}-{\displaystyle \frac{(m+n)!}{m!(n-1)!}}\right)={\displaystyle \frac{1}{m+n}}\left(m{\displaystyle \frac{(m+n)!}{m!n!}}-n{\displaystyle \frac{(m+n)!}{m!n!}}\right)$

$={\displaystyle \frac{m-n}{m+n}}\left({\displaystyle \genfrac{}{}{0pt}{}{m+n}{m}}\right)$

These numbers are called ballot numbers: if we had an election between two candidates in which the winner received $m$ votes and the loser $n$ votes, the ballot number counts the number of ways in which the votes could be counted so that the winner was always ahead. One can also easily see that the probability that the votes are counted in such a way is

$$\frac{m-n}{m+n}$$

By adjusting the start and end points, this argument can be easily used to derive a formula for paths that stay on or below the diagonal.

Now, consider the special case $m=n+1$, i.e. paths from $(1,0)\to (n+1,n)$ staying below the diagonal. These are counted, per the above, by

$$\frac{1}{2n+1}\left(\genfrac{}{}{0pt}{}{2n+1}{n}\right)=\frac{(2n)!}{n!(n+1)!}=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)$$

which are the Catalan numbers.

Title	lattice paths and ballot numbers