6
$\begingroup$

Suppose we are on a finite 2D grid of points from $(0,0)$ to $(a,b)$. Each turn we can move up/down/left/right on this grid (we have 3 possible moves on edges and 2 on corners). In the beginning we are at the point $(x_0,y_0)$ inside the grid. How many ways are there to make $N$ steps on the grid?

I know a recursive solution when the number of ways to make $N$ steps is sum of number of ways to make $N-1$ steps from cell to the left/right/up/down. I wonder is there a combinatorial solution?

  • 0
    +1 The really hard problem here is that there are certain partial walks which lead to no further possible walks, such as when you walk yourself into a dead end near the grid's edge, or spiral yourself in. So it becomes less than trivial to determine the number of permutations.2011-10-14
  • 0
    Total number of walks on infinite grid is obviously (4 ^ N). The problem is to find walks that leave our grid.2011-10-14
  • 0
    @Nick: You seem to be assuming that the path can’t intersect itself, but the statement of the problem imposes no such restriction.2011-10-14
  • 0
    Yes. No restrictions on self-intersection.2011-10-14
  • 0
    I don’t know whether this is at all useful, but your problem is equivalent to the following problem. Let $A=\{a,b,c,d\}$. For $w\in A^*$ let $h(w)=|w|_b-|w|_a$ and $v(w)=|w|_d-|w|_c$. For $u,w\in A^*$ write $u\preceq w$ iff $u$ is an initial segment of $w$. Given integers $m_0$$|\{w\in A^k:\forall u\preceq w[m_0\le h(u)\le m_1\land n_0\le v(u)\le n_1]\}|\;?$$2011-10-14
  • 0
    The answer to this question http://math.stackexchange.com/questions/17972/probability-of-never-reach-1-for-a-1d-random-walk-of-n-steps which uses reflection principle might be helpful but I can't extend it to the second bound and 2D.2011-10-14

2 Answers 2