Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic version of SAW's? We know for example that Catalan numbers count a myriad of things so perhaps SAW appear elsewhere? For reference, $c(n)$ for the usual 2-D integer lattice looks like 1,4,12,36,100,284,780,,... for $n=0,1,2,...

The online integer sequence library gives no results other than the number of SAWs.

Note: I'm not exactly interested in characterizations, such as the ones in this question. Something like the Hammersley and Welsh characterization in terms of excursion width is closer to what I'm looking for. In fact one sees partition functions crop up naturally, with theorems of Hardy and Ramanujan used for growth estimates.


1 Answer 1


I strongly doubt that there exists a non-trivial bijection between self-avoiding walks on Z^d and other combinatorial objects. I don't have any intuition as to whether the generating function may have some other number theoretic interpretation, but I haven't seen or heard anything in this regard.

SAWs are sufficiently complicated that it seems almost certain that the generating function for SAWs even on the square lattice them is non-holonomic (see e.g. Andrew Rechnitzer discussing the related model of self-avoiding polygons, "Haruspicy 2: The anisotropic generating function of self-avoiding polygons is not D-finite", link), and the model is unlikely to be "solvable" in the conventional sense.

FYI, Iwan Jensen has enumerated SAWs on Z^2 to 71 steps here, and higher dimensional enumerations due to Gordon Slade, Richard Liang and I are available here.

  • $\begingroup$ Thanks for the info. I agree that it's pretty unlikely a non-trivial bijection exists. That's probably what makes these SAW so darn complicated. $\endgroup$
    – Alex R.
    Jan 23, 2011 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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