Robert M. Dickau - Shortest Paths (text)

Shortest-path diagrams (text version)

_____________________________________
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, ...

1 x 1 grid, 2 paths: 
                                                                              
 #....................................  ##################################### 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #                                   .  .                                   # 
 #####################################  ....................................# 

2 x 2 grid, 6 paths:
                                                                              
 #........................ #....................... #........................ 
 #           .           . #           .          . #           .           . 
 #           .           . #           .          . #           .           . 
 #           .           . #           .          . #           .           . 
 #           .           . #           .          . #           .           . 
 #           .           . #           .          . #           .           . 
 #........................ #############........... ######################### 
 #           .           . .           #          . .           .           # 
 #           .           . .           #          . .           .           # 
 #           .           . .           #          . .           .           # 
 #           .           . .           #          . .           .           # 
 #           .           . .           #          . .           .           # 
 ######################### ............############ ........................# 
 
 
 #############............ #############........... ######################### 
 .           #           . .           #          . .           .           # 
 .           #           . .           #          . .           .           # 
 .           #           . .           #          . .           .           # 
 .           #           . .           #          . .           .           # 
 .           #           . .           #          . .           .           # 
 ............#............ ............############ ........................# 
 .           #           . .           .          # .           .           # 
 .           #           . .           .          # .           .           # 
 .           #           . .           .          # .           .           # 
 .           #           . .           .          # .           .           # 
 .           #           . .           .          # .           .           # 
 ............############# .......................# ........................# 

3 x 3 grid, 20 paths:

 #.............. #............. #............. #............. #.............. 
 #    .    .   . #   .    .   . #   .    .   . #   .    .   . #   .    .    . 
 #.............. #............. #............. #............. #####.......... 
 #    .    .   . #   .    .   . #   .    .   . #   .    .   . .   #    .    . 
 #.............. #####......... ##########.... ############## ....#.......... 
 #    .    .   . .   #    .   . .   .    #   . .   .    .   # .   #    .    . 
 ############### ....########## .........##### .............# ....########### 
 
 #.............. #............. #............. #............. #.............. 
 #    .    .   . #   .    .   . #   .    .   . #   .    .   . #   .    .    . 
 ######......... #####......... ##########.... ##########.... ############### 
 .    #    .   . .   #    .   . .   .    #   . .   .    #   . .   .    .    # 
 .....######.... ....########## .........#.... .........##### ..............# 
 .    .    #   . .   .    .   # .   .    #   . .   .    .   # .   .    .    # 
 ..........##### .............# .........##### .............# ..............# 
 
 ######......... #####......... #####......... #####......... #####.......... 
 .    #    .   . .   #    .   . .   #    .   . .   #    .   . .   #    .    . 
 .....#......... ....#......... ....#......... ....######.... ....######..... 
 .    #    .   . .   #    .   . .   #    .   . .   .    #   . .   .    #    . 
 .....#......... ....######.... ....########## .........#.... .........###### 
 .    #    .   . .   .    #   . .   .    .   # .   .    #   . .   .    .    # 
 .....########## .........##### .............# .........##### ..............# 
 
 ######......... ##########.... ##########.... ##########.... ############### 
 .    #    .   . .   .    #   . .   .    #   . .   .    #   . .   .    .    # 
 .....########## .........#.... .........#.... .........##### ..............# 
 .    .    .   # .   .    #   . .   .    #   . .   .    .   # .   .    .    # 
 ..............# .........#.... .........##### .............# ..............# 
 .    .    .   # .   .    #   . .   .    .   # .   .    .   # .   .    .    # 
 ..............# .........##### .............# .............# ..............# 
                                                                              
                                                                              
Designed and rendered using Mathematica 3.0 for the Apple Macintosh.
Copyright © 1996 by Robert M. Dickau.

[Privacy Policy] [Terms of Use]

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

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

Copyright © 1996/7 Robert M. Dickau