Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
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 en.wikipedia.org/wiki/Self-avoiding_walk . –  Qiaochu Yuan Feb 18 '12 at 22:18

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.