Here are some diagrams that represent the possible paths of length
2*n* from one corner of an *n*-by-*n* grid to the opposite corner.
The number of paths are the central binomial coefficients

or ,

*central* meaning they fall along the center line of Pascal’s triangle.

One reason this makes sense is that all of the paths in the figures below consist
of *n* steps east and *n* steps north, so from the 2*n* steps we
choose *n*, giving
.

You can also use the old trick of numbering the possible ways to get to each point, which gives you Pascal’s triangle turned on its side. The numbers on the diagonal connecting the start and end points—1, 2, 6, and 20, in the figure below—are the central binomial coefficients:

(The Catalan numbers describe how many of these paths stay under the diagonal connecting the start and end points.)

1 × 1 grid, 2 paths:

2 × 2 grid, 6 paths:

3 × 3 grid, 20 paths:

4 × 4 grid, 70 paths:

Designed and rendered using *Mathematica* 3.0 for the Apple Macintosh and (much later) *Mathematica* 7.0 for Microsoft Windows.

Copyright © 1996–2018 by Robert Dickau.

[ home ] || [ 2010-12-29 ]

www.robertdickau.com/manhattan.html