# Counting self avoiding walks in a strip

Consider the strip $$\{0,1,\ldots n\}\times\{0,1,2\}$$ in $$\mathbb{N}^2.$$ Is a formula known for the total number of self avoiding walks in this strip starting at $$(0,0)$$ in terms of the parameter $$n$$?

Edit: I mean all the walks that take steps of $$(\pm 1,0),(0,\pm1)$$ as long as they are confined to that strip.

Note: Asked on math.stackexchange (see here) a week ago with no specific answer.

• Yes. Do you know the transfer-matrix method? – Martin Brandenburg Feb 14 at 11:37
• @MartinBrandenburg: The OP wants self-avoiding walks only. – Mark Sapir Feb 14 at 14:46
• I know. This is why the method has to be applied to a suitable graph. See Faase, "On the number of specific spanning subgraphs of $G \times P_n$". Here it is explained how to count self-avoiding paths from one point on the "left" to one point on the "right", but something similar works for general end-points, and then we just sum up. – Martin Brandenburg Feb 14 at 16:00
• A special case of this was Problem A2 of the 2005 Putnam exam. It was in the context of a rook's tour on 3 by $n$ chessboard, counting paths from $(1,1)$ to $(n,1)$ that visited each square exactly once. For the current problem, these are maximal SAWs with a specified endpoint. – Brian Hopkins Feb 15 at 16:37