|
A lattice path is a path in
 whose vertices are lattice points in some lattice (for example, points of
 all of whose coordinates are integers). This article considers lattice paths in the plane from  to  for  whose vertices fall on
 .
As a warm-up, how many paths altogether are there from  to  if we restrict the step sizes to  and  (that is, a path can travel only one step north or one step east at a time)? There are  steps altogether, and we can choose any  of them to be vertical
steps, so the answer is obviously
Another way of visualizing the answer is to encode a path as a sequence of  's and  's corresponding to horizontal and vertical steps; the question then is: how many sequences of length  are there with exactly   's? Again, the answer is clearly as above.
Suppose we are interested in paths from  to  for  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  to  that stay strictly below the diagonal. We know how many total paths there are:
 (use the above formula, starting at  instead of  ). 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  to  that touch or cross the diagonal is the same as the total number of paths from  to  . 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  . This gives a path from  to  ; 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  to  . But also, every path from  to  must cross the diagonal at some point, since  , and thus it is the reflection of some unwanted path from  to  . So we have established the required bijection.
Now, the total number of paths from  to  is
 , so the total number of paths from  to  that never touch the diagonal is then
These numbers are called ballot numbers: if we had an election between two candidates in which the winner received  votes and the loser  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
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  , i.e. paths from
 staying below the diagonal. These are counted, per the above, by
which are the Catalan numbers.
| 
