A374297 Number of growing self-avoiding walks of length n on a half-infinite strip of height 3 with a trapped endpoint.

1, 2, 2, 6, 10, 20, 41, 79, 146, 285, 538, 1039, 1982, 3812, 7272, 13961, 26686, 51161, 97865, 187518, 358835, 687327, 1315616, 2519472, 4823116, 9235610, 17681264, 33855310, 64817361, 124105590, 237610012, 454943624, 871035486, 1667726103, 3193049603

Offset: 4

Author

Jay Pantone, Jul 03 2024

Keywords

• nonn
• easy

Comments

A growing self-avoiding walk (GSAW) is a walk on a graph that is directed, does not visit the same vertex twice, and for which all neighbors of the endpoint are part of the walk, i.e., the endpoint is trapped. This sequence is about GSAWs on the grid graph of integer points (x,y) where x >= 0 and y is in {0,1,2}. The GSAW must start at the point (0,0). The length of a GSAW is the number of edges.

Examples

			The a(4) = 1 and a(5) = 2 walks are:
  *--*  *    *--*  *    *  *  *
     |       |  |
  *--*  *    *  *  *    *--*--*
  |             |       |     |
  *     *    *--*  *    *  *--*
The GSAW below has length 10.
  *--*--*  *  *  *
        |
  *--*  *--*  *  *
  |  |     |
  *  *--*--*  *  *
		

Links

• Jay Pantone, A. R. Klotz, and E. Sullivan, Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height., arXiv:2407.18205 [math.CO], 2024.
• Index entries for linear recurrences with constant coefficients, signature (1,2,0,0,-1,2,-4,-3,-2,0,-4,-4).

Crossrefs

Cf. A078528.

Formula

G.f.: x^4*(1 + x - 2*x^2 - x^5 + x^6 - 2*x^8 - 5*x^9 - 5*x^10 - 2*x^11 - 2*x^12)/((1 + x^4)*(1 - 2*x^2)*(1 - x - 2*x^3 - x^4 - 2*x^5 - 2*x^6)).