A334877 Number of self-avoiding walks on a 2-dimensional square lattice where the walk consists of steps with incrementing length from 1 to n.

1, 4, 12, 36, 108, 324, 948, 2740, 7892, 22540, 64020, 181396, 511828, 1440652, 4045676, 11322732, 31615780, 88100644, 245143676, 681002276, 1888943100, 5233741636, 14484853148, 40043579596, 110590828396, 305133547724

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 by 1 after each step up until the step length is n.

The first time a collision with a previous step can occur is for n = 6. This can occur in three different ways. For example a walk with steps of length 1,2 and 3 to the right, a step of length 4 upward, then a step of length 5 to the left. A step of length 6 downward would now result in a collision. Requiring six 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.

Note that this sequence agrees with a SAW on the diamond lattice, A001394, for the first 7 terms, even though the seventh term here has some walks removed due to the above collision.

Links

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

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:
.
    *
    |        1     2
    . 2    *---*---.---*
    |
*---*
  1
.
The first walk can be taken in 8 different ways, the second in 4 ways, giving a total of 12 walks.
a(3) = 36. These consist of the following five walks:
.
    *                                                           *
    |                                                           |
    .              3                     3                      .
    | 3      *---.---.---*         *---.---.---*                | 3
    .                    |         |                            .
    |                    . 2       . 2                          |
    *                    |         |                *---*---.---*
    |                *---*     *---*                  1     2
    . 2                1         1
    |                                     *---*---.---*---.---.---*
*---*                                       1     2          3
  1
.
The first four can be taken in 8 different ways, while the last straight walk can be taken in 4 ways, giving a total of 36 walks. Notice it is not possible to form a collision from any of these walks by adding a step of length 4.

Crossrefs

Cf. A001411, A334720, A077482, A334720, A001394.

Sequence in context: A006817 A163315 A326339 * A003119 A001394 A156946

Adjacent sequences: A334874 A334875 A334876 * A334878 A334879 A334880

Keyword

nonn,more,walk

Author

Scott R. Shannon, May 13 2020

Status

approved