A347506 Number of self-avoiding walks on a 2-dimensional square lattice where the walk consists of steps with incrementing lengths equal to the square numbers, from 1 to n^2.

1, 4, 12, 36, 108, 324, 972, 2916, 8676, 25572, 74124, 213788, 614444, 1757012, 5001372, 14175996, 40113156, 113363284, 319328028, 897533236, 2521069708, 7052715556, 19742289948, 55129924484, 153874225436

Offset

0,2

Comments

This sequence gives the number of self-avoiding walks on a 2-dimensional square lattice where the walk starts with a step length of 1 which then increments at each step to the next square number until the step length is n^2.

The first time a collision with a previous step can occur is for n = 8, i.e., a walk with step lengths of 1,4,9,16,25,36,49,64. For a walk with one or more initial steps to the right followed by an upward step this can occur in nine different ways. For example, consider a walk with steps of length 1,4,9,16,25 to the right, a step of length 36 upward, then a step of length 49 to the left. A step of length 64 downward would now result in a collision. Requiring eight steps before a collision is in contrast to the standard 2D square lattice SAW of A001411 where a collision can occur on the fourth step.

Links

Table of n, a(n) for n=0..24.

A. R. Conway et al., Algebraic techniques for enumerating self-avoiding walks on the square lattice, J. Phys A 26 (1993) 1519-1534.

A. J. Guttmann, On the critical behavior of self-avoiding walks, J. Phys. A 20 (1987), 1839-1854.

A. J. Guttmann and A. R. Conway, Self-Avoiding Walks and Polygons, Annals of Combinatorics 5 (2001) 319-345.

Example

a(1) = 4. These are the four directions one can step away from a point on a 2D square lattice.
a(2) = 12. These consist of the two following walks:
.
    *
    |
    .
    |
    . 4
    |        1         4
    .      *---*---.---.---.---*
    |
*---*
  1
.
The first walk can be taken in 8 different ways, the second in 4 ways, giving a total of 12 walks.
a(8) = 8676. If we consider only walks starting with one or more steps to the right followed by an upward step, and ignoring collisions, then the total number of walks is 3^6 + 3^5 + 3^4 + 3^3 + 3^2 + 3^1 + 3^0 = 1093. However, nine of these are forbidden due to the collisions given in the comments, leaving 1084 in total. These can be walked in eight different ways on the 2D grid. There are also the four straight walks along the axes. This gives a total of 1084*8 + 4 = 8676 walks.

Crossrefs

Cf. A000290, A334877, A336262, A001411.

Sequence in context: A163877 A336262 A164353 * A164697 A165184 A165756

Adjacent sequences: A347503 A347504 A347505 * A347507 A347508 A347509

Keyword

nonn,walk,more

Author

Scott R. Shannon, Sep 04 2021

Status

approved