Number of simple paths between two vertices on an $n \times m$ square-grid graph?

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.