Exactly-solvable self-trapping lattice walks on lattices of arbitrary height

Abstract

A growing self-avoiding walk (GSAW) is a walk on a graph that is directed, does not visit the same vertex twice, and has a trapped endpoint. We show that the generating function enumerating GSAWs on a half-infinite strip of finite height is rational, and we give a procedure to construct a combinatorial finite state machine that allows one to compute this generating function. We then modify this procedure to compute generating functions for GSAWs under two probabilistic models. We derive the mean trapping lengths for GSAWs in strips of height 2 to 5 to gain insight into the empirically known square lattice result of 71 steps. Finally, we prove that the generating functions for Greek key tours (GSAWs on a finite grid that visit every vertex) on a half-infinite strip of fixed height are also rational, allowing us to resolve several conjectures.