Shortest-path diagrams

_____________________________________
Back to Robert's Math Figures
_____________________________________
Here are some diagrams that represent the possible paths of length 2n from one corner of an n-by-n grid to the opposite corner. The number of paths are the central binomial coefficients

 Binomial[2n, n] or  (2n)!/(n!)^2 ,

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

The first few are 1, 2, 6, 20, 70, 252, ...

(Oddly enough, the Catalan numbers describe how many of these paths stay under the main diagonal.)

1 x 1 grid, 2 paths:
[ 1 x 1 (sorry, but the pictures speak a thousand words) ]

2 x 2 grid, 6 paths:
[ 2 x 2 ]

3 x 3 grid, 20 paths:
[ 3 x 3 ]

4 x 4 grid, 70 paths:
[ 4 x 4 ]

5 x 5 grid, 252 paths:
[ 5 x 5 ]

Designed and rendered using Mathematica 3.0 for the Apple Macintosh.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/

Copyright © 1996/7 Robert M. Dickau