Self avoiding walks

A self avoiding walk is a path through a graph where no vertex is visited more than once. One problem is to consider the cartesian lattice, and the paths from \((0,0)\) to \((m,n)\). If we only allow paths in the “positive direction”, so that from \((i,j)\) the path can only proceed to \((i+1,j)\) or \((i,j+1)\) we have what are sometimes called “staircase paths”:

The number of such paths can be easily shown to be

\[ \dbinom{m+n}{n}. \]

Suppose that the number of ways of reaching \((x,y)\) is \(N(x,y)\). There is only one way to reach either of \((i,0)\) or \((0,j)\), that is \(N(i,0) = N(0,j) = 1\). Also, the number of ways of reaching \((x,y)\) is the sum of the numbers of ways of reaching \((x-1,y)\) and \((x,y-1)\); that is \(N(x,y) = N(x-1,y)+N(x,y-1)\).

We thus have the following numbers:

\[\begin{array}{rrrrrrr} \vdots \\ 1&6&21&56&126&252\\ 1&5&15&35&70&126\\ 1&4&10&20&35&56\\ 1&3&6&10&15&21\\ 1&2&3&4&5&6\\ 1&1&1&1&1&1&\ldots \end{array}\]

which are obviously the binomial coefficients, and with

\[ N(x,y) = \dbinom{x+y}{x}. \]

So for the \(10\times 10\) grid above, the number of staircase walks is

\[ \dbinom{20}{10}=184{,}756. \]

If we allow walks that can go in any direction (with the only restriction being that they stay within the grid, and never visit a lattice point more than once), the number of self avoiding walks becomes very large.

There is in fact no known formula for the number of such paths on an \(n\times n\) grid, but the numbers are given as sequence A007764 of the OEIS, and for a \(10\times 10\) grid there are

\[ 1{,}568{,}758{,}030{,}464{,}750{,}013{,}214{,}100 \]

such paths. That’s about 1.6 heptillion.