3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes. Do you know the transfer-matrix method? $\endgroup$ – Martin Brandenburg Feb 14 at 11:37
  • $\begingroup$ @MartinBrandenburg: The OP wants self-avoiding walks only. $\endgroup$ – Mark Sapir Feb 14 at 14:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Brandenburg Feb 14 at 16:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Hopkins Feb 15 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.