Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
The keyword here is "self-avoiding walk" or "self-avoiding random walk," and as I understand it enumerating them is very, very hard. See . – Qiaochu Yuan Feb 18 '12 at 22:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.