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?

  • $\begingroup$ +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. $\endgroup$ – Engineer Oct 14 '11 at 13:59
  • $\begingroup$ Total number of walks on infinite grid is obviously (4 ^ N). The problem is to find walks that leave our grid. $\endgroup$ – man Oct 14 '11 at 14:20
  • $\begingroup$ @Nick: You seem to be assuming that the path can’t intersect itself, but the statement of the problem imposes no such restriction. $\endgroup$ – Brian M. Scott Oct 14 '11 at 20:50
  • $\begingroup$ Yes. No restrictions on self-intersection. $\endgroup$ – man Oct 14 '11 at 20:59
  • $\begingroup$ 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<m_1$ and $n_0<n_1$ and a positive integer $k$, what is $$|\{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]\}|\;?$$ $\endgroup$ – Brian M. Scott Oct 14 '11 at 21:04

I don't know of a combinatorial solution, but I do know a trick...

The number of $n$-step walks starting at $(x,y)$ that don't leave the grid is obviously the total number of $n$-step walks ($4^n$) times the probability $p_n(x,y)$ that a random $n$-step walk started at $(x,y)$ doesn't leave the grid.

What is that probability? Obviously, $p_0(x,y) = \chi(x,y)$, where $\chi(x,y)$ equals $1$ inside the grid and $0$ on the points surrounding it. For higher $n$, we have the recurrence relation $$p_{n+1}(x,y) = \chi(x,y) \frac{p_n(x-1,y) + p_n(x+1,y) + p_n(x,y-1) + p_n(x,y+1)}{4}.$$

Except for the $\chi(x,y)$ term, this is almost a convolution, and by making use of the fact that the grid is rectangular, we can get rid of the unwanted term by extending $p_0$ suitably beyond the edges of the grid.

Here it turns out to be much more convenient to let the grid extend from $(1,1)$ to $(a-1, b-1)$, so I'm going to adopt that convention, and then define $p_0(x,y) = f(x)g(y)$, where $$f(x) = \begin{cases} \phantom{+}0 & \text{if }x = ka, k \in \mathbb Z \\ \phantom{+}1 & \text{if }(2k+0)a < x < (2k+1)a, k \in \mathbb Z \\ -1 & \text{if }(2k+1)a < x < (2k+2)a, k \in \mathbb Z \end{cases}$$ $$g(y) = \begin{cases} \phantom{+}0 & \text{if }y = kb, k \in \mathbb Z \\ \phantom{+}1 & \text{if }(2k+0)b < y < (2k+1)b, k \in \mathbb Z \\ -1 & \text{if }(2k+1)b < y < (2k+2)b, k \in \mathbb Z.\end{cases}$$

It is then not hard to show that, even if we drop the $\chi(x,y)$ term from the recurrence, $p_n(x,y) = 0$ whenever $x$ is divisible by $a$ or $y$ is divisible by $b$. Thus, we can calculate $p_{n+1}$ for $n \ge 0$ via the convolution $p_{n+1} = p_n * K$, i.e. $$p_{n+1}(x,y) = \sum_{u,v \in \mathbb Z} p_n(x-u,y-v) K(u,v),$$ where the kernel $K$ is given by $K(1,0) = K(0,1) = K(-1,0) = K(0,-1) = \frac 1 4$ and $K(u,v) = 0$ for all other values of $u$ and $v$.

Why would we want to do that? Well, it just happens that convolutions of discrete periodic functions can be efficiently calculated using discrete Fourier transforms. In particular, letting $\tilde p_n$ and $\tilde K$ denote the Fourier transforms of $p_n$ and $K$, we have $$\tilde p_n = \tilde p_{n-1} \tilde K = \tilde p_0 \tilde K^n,$$ where the multiplication is simply done pointwise.


Very elegant the answer of Ilmari. However, it seems that by this proceeding we also count the "degenerate" paths in following sense: suppose, for example, that we are at the step 1 and are at the point $(x_{1},y_{1})$ such that $x_{1} = x_{0}$ and $y_{1} = y_{0}+1$. Now, for the next step we can't move backward to the previous point $(x_{0},y_{0})$, otherwise $(x_{2},y_{2}) = (x_{0},y_{0}) $ and the trace of the path would only have two points $ \left \{ (x_{0},y_{0}), (x_{1},y_{1}) \right \}$. In the same manner, if , at each step we still have 4 possible moves, we would be counting these "degenerate" paths,i.e., those paths that after having made any number of movements, the trace is the same.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.