info prev up next book cdrom email home

Lattice Path

A path composed of connected horizontal and vertical line segments, each passing between adjacent Lattice Points. A lattice path is therefore a Sequence of points $P_0$, $P_1$, ..., $P_n$ with $n\geq 0$ such that each $P_i$ is a Lattice Point and $P_{i+1}$ is obtained by offsetting one unit east (or west) or one unit north (or south).


The number of paths of length $a+b$ from the Origin (0,0) to a point $(a,b)$ which are restricted to east and north steps is given by the Binomial Coefficient ${a+b\choose a}$.

See also Ballot Problem, Golygon, Kings Problem, Lattice Point, p-Good Path, Random Walk


References

Dickau, R. M. ``Shortest-Path Diagrams.'' http://forum.swarthmore.edu/advanced/robertd/manhattan.html.

Hilton, P. and Pederson, J. ``Catalan Numbers, Their Generalization, and Their Uses.'' Math. Intel. 13, 64-75, 1991.




© 1996-9 Eric W. Weisstein
1999-05-26