MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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. – Alex R. Jan 23 '11 at 6:22

Your Answer


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.