2
$\begingroup$

Consider an $N\times N$ grid. A path in this grid is understood to be a sequence of moves (left, right, up, down) which connect two spaces on the grid, and which never travels over the same space twice; in other words I consider only non-intersecting paths that can't move along diagonals.

Q1) How many paths are there connecting the top left and bottom right corners of an $N\times N$ grid?

Q2) Given that one space is removed from the grid, how does the number of paths depend on which space is removed?

Q3) Given that multiple spaces are removed from the grid, how does the number of paths depend on which spaces are removed?

These questions are easily answered for a $3\times 3$ grid by simply checking every possible case; but I was wondering if there is a better way to go about things for the general situation of an $N \times N$ grid.

  • 3
    The keyword here is "self-avoiding walk" or "self-avoiding random walk," and as I understand it enumerating them is very, very hard. See http://en.wikipedia.org/wiki/Self-avoiding_walk .2012-02-18

0 Answers 0