lattice paths and ballot numbers
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
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.
|Title||lattice paths and ballot numbers|