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.

I've encountered this whilst writing an optimisation benchmark for some heuristic search algorithms. Feels like there should be a basic solution out there!

A square-grid graph is constructed from $n \times m$ vertices embedded into the cartesian plane, such that each vertex corresponds to a pair of integers. Say that a vertex is on a boundary if the $x$ or $y$ coordinate is minimal or maximal (i.e. it is at the lower/upper bound of the grid).

Is there a general expression for the number of simple paths (paths that do not revisit the same vertex) between a pair of vertices $(a,b)$ on a square-grid graph. Where $a$ is on a boundary and $b$ is not?

Thanks

share|improve this question
    
Do you want the count of shortest-length paths only, or all possible simple paths? –  Isaac Feb 21 '11 at 20:18
    
The second is correct, all possible simple paths. –  Tom Seaton Feb 21 '11 at 22:52

1 Answer 1

up vote 10 down vote accepted

This is a variation of the problem of enumerating self avoiding walks. In general there are no closed form expressions for the number of self avoiding walks between two arbitrary points in a grid of arbitrary dimension; although I have not seen the problem considered with the particular constraints in question, I would be surprised if there was a closed form solution in this case. However, reliable approximation methods do exist for such enumeration problems, and such an approximation may be suitable for your purposes.

Edit: Using a rather naive approach, I've worked out the following lower bound for the number of self-avoiding walks on an $n\times m$ rectangular grid from a given boundary point to a given interior point. With more mathematical sophistication, it is likely that significant improvements could be made on this bound.

Let $A$ be an $n\times m$ rectangular grid, with $n>2$ and $m>2$. That is, let $A$ be the collection of integer points in an $xy$ cartesian plane satisfying the conditions $0 \leq x \leq n$ and $0 \leq y \leq m$. Let $\left(a,b\right)$ be a point in the interior of $A$. In the wikipedia article it discusses the case of walks from one diagonal to another with moves only in the positive direction. I shall call such walks positive walks. There is a simple formula for the number of positive walks from one point to another in a rectangular grid.

We claim that the number of self-avoiding walks from a given point on the boundary to $\left(a,b\right)$ is bounded below, independently of the choice of the point on the boundary by

$$ \binom{a+b}{b} + \binom{a+m-b}{m-b} + \binom{n-a+b}{b} + \binom{n-a+m-b}{m-b}$$

That is, by the number of positive walks from any of the four corners of the grid to the point $\left(a,b\right)$.

Let $\alpha$ be a point on the boundary of $A$. We first bound the number of self-avoiding walks from $\alpha$ to $\left(a,b\right)$ below by the number of positive walks from any point on the boundary of an $\left(n-2\right)\times\left(m-2\right)$ rectangular grid $B$ to the point $\left(a-1,b-1\right)$ within $B$. Our requirement that $n>2$ and $m>2$ is to allow this step to work with a minimum of headache. There is probably an exact solution in the case where $n \leq 2$ or $m \leq 2$.

We may consider those walks which first move $k$ steps in the counter-clockwise direction around the boundary, then move one step into the interior, and whose successive moves follow a positive walk directly to $\left(a,b\right)$. We may do this for $k$ from 0 to $2n+2m-1$, excluding those values of $k$ which place the walker upon a corner, where there is no move into the interior. It is clear that we have produced a disjoint collection of self-avoiding walks equal in number to the number of positive walks from the boundary of an $\left(n-2\right)\times\left(m-2\right)$ $B$ to the point $\left(a-1,b-1\right)$ in $B$.

Now we use the result that the number of positive walks from one diagonal to another on an $j\times k$ grid equals

$$\binom{j+k}{j} = \binom{j+k}{j,k} = \binom{j+k}{k} $$

Using this result, we may express the number of positive walks from any point on the boundary of $B$ to the point $\left(a-1,b-1\right)$ as the sum

$$\sum_{i=0}^{b-1}\binom{a-1+i}{a-1} + \sum_{i=0}^{m-b-1}\binom{a-1+i}{a-1} + \sum_{i=0}^{b-1}\binom{n-a-1+i}{n-a-1} + $$ $$\sum_{i=0}^{m-b-1}\binom{n-a-1+i}{n-a-1} + \sum_{i=0}^{a-1}\binom{b-1+i}{b-1} + \sum_{i=0}^{n-a-1}\binom{b-1+i}{b-1} + $$ $$ \sum_{i=0}^{a-1}\binom{m-b-1+i}{m-b-1} + \sum_{i=0}^{n-a-1}\binom{m-b-1+i}{m-b-1} - 4$$

Where we subtract 4 because the above expression involving binomial coefficients counts each straight line path from the boundary of $B$ to $\left(a-1,b-1\right)$ twice. Since we have specified that $n>2$ and $m>2$, we may safely ignore this 4 by adding in some walks that first move $k$ steps in the clock-wise direction, move away from the boundary, and then follow a positive walk to the finish point.

Using the well known binomial coefficient identity $$ \sum_{i=0}^{k}\binom{r+i}{r} = \binom{r+k+1}{r+1}$$

We may express the above sum, without the addition of the constant $-4$, as $$\binom{a+b-1}{a}+\binom{a-1+m-b}{a}+\binom{n-a-1+b}{n-a}+\binom{n-a-1+m-b}{n-a} + $$ $$\binom{b-1+a}{b}+\binom{b-1+n-a}{b}+\binom{m-b-1+a}{m-b}+\binom{m-b-1+n-a}{m-b}$$

After some simple manipulations, we may pair up the terms and combine each pair using the identity $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$ to get

$$ \binom{a+b}{b} + \binom{a+m-b}{m-b} + \binom{n-a+b}{b} + \binom{n-a+m-b}{m-b}$$

The result we were attempting to prove.

I'm not sure how useful this result is, but I thought it was interesting how easily things lined up to be simplified by standard binomial coefficient identities. I also thought it was interesting how the final formula has a straightforward combinatorial interpretation.

share|improve this answer
    
Thanks - useful observation. I was aware of the case along the diagonal detailed in the wikipedia link, but hadn't associated it with the general problem described. –  Tom Seaton Feb 21 '11 at 22:47

Your Answer

 
discard

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

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