Self-avoiding paths: enumeration with graphillion

Determining the number of self-avoiding paths between points on a grid is a very difficult problem; in general unsolved. For example, the number of SAWs between opposite corners of a square grid is known for small grids, but beyond a certain size the computation becomes unviable.

As you can see from the list of numbers here, the number of paths on an \(n\times n\) grid, from \((0,0)\) to \((n-1,n-1)\) grows exponentially. In fact if \(n_k\) is the number of self avoiding walks \(C_k\) on a square grid of edge size \(k\), then

\[ C_k \to \lambda^{k^2+o(k^2)} \]

with \(\lambda = 1.744550 \pm 0.000005\), and \(1.628 < \lambda < 1.782\). See the preprint by Bousquet-Melou, Guttman and Jensen.

If the above list is read into any programming language, the values of

\[ \frac{\sqrt{\log{N_k}}}{k} \]

can be printed out as

0.8325546111576977
0.7881793339380322
0.7612077944956939
0.7520485444596241
0.7496360371765028
0.7485400082233541
0.7477106336904858
0.7471040508645819
0.7466896608622989
0.746406902934072
0.7462084461399834
0.7460656431344197
0.7459612569365978
0.7458841430945673
0.7458267304121244
0.7457837636619853
0.7457515409954109
0.7457274121003646
0.7457094479346138
0.7456962234040198
0.745686671974195
0.7456799862455377
0.7456755486583991
0.7456728824478861
0.7456716164554021

This means that we could say - assuming that the sequence converges to a value close to the last last value - that

\[ \frac{\sqrt{\log N_k}}{k} \approx 0.7467. \]

This can be written as

\[ N_k \approx e^{(0.7467k)^2} = e^{0.7467^2k^2} \approx 1.7461^{k^2} \]

which agrees with the value found above.

As well, it is known that the number of walks \(a_n\) on a \(3\times n\) grid satisfies the recurrence relation

\[ a_0=0,\quad a_1=1,\quad a_2=3,\quad a_3=4,\qquad a_n=4a_{n-1}-3a_{n-2}+2a_{n-3}+a_{n-4}\text{ for } n\ge 4. \]

There is also a generating function

\[ a_n = \left.\frac{1}{(n-1)!}\frac{d^{n-1}}{dx^{n-1}}\frac{(x-1)(x+1)}{(x^2+3x-1)(x^2-x-1)}\right|_{x=0} \]

and an approximation

\[ a_n \approx \frac{4+\sqrt{13}}{13+3\sqrt{13}}\left(\sqrt{\frac{3+\sqrt{13}}{2}}\right)^{\!2m} \]