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

Author

Scott R. Shannon, Sep 04 2021

Keywords

• nonn
• walk
• more

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.

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A000290, A334877, A336262, A001411.