A348334 Table read by downward antidiagonals: T(n,k) is the number of self-avoiding walks on a 2D square lattice for a chain growing to total length n after taking k steps (see Comments lines).

4, 12, 4, 36, 12, 4, 108, 36, 12, 4, 324, 108, 36, 12, 4, 972, 324, 108, 36, 12, 4, 2916, 972, 324, 100, 36, 12, 4, 8748, 2916, 972, 284, 100, 36, 12, 4, 26244, 8748, 2916, 804, 284, 100, 36, 12, 4, 78732, 26244, 8748, 2276, 804, 284, 100, 36, 12, 4

Offset

1,1

Comments

Consider a chain starting at the origin of a 2D square lattice with an initial length of one and where after each step it grows by one unit in length up to a maximum length of n. Like a standard self-avoiding walk it cannot visit any lattice coordinate it already occupies. After k steps, where k > n, the tail of the chain moves away from the origin as the head of the chain continues to move to all unoccupied coordinates. This means that the chain can eventually revisit the origin when it has taken more than n steps as the tail of the chain no longer occupies that coordinate. In general if a coordinate is visited after m steps then it can be revisited on step m + n + 1 or beyond. This sequence lists the total number of possible walks for a chain growing to maximum length n, with n>=1, after it has taken k steps, with k>= 1.

Links

Table of n, a(n) for n=1..55.

Formula

row(1..3,k) = A003946(k);

row(n,k) = A001411(k) for k <= n.

Example

For n = 1, 2, 3 the total number of walks is the same as the non-backtracking random walk of A003946 as the chain can never intersect itself.
For n = 4 and beyond for small k the number of walks is the same as the standard 2D SAW of A001411 as for k<=n the chain has not moved away from the origin or any previously visited coordinate. However for k>n and beyond previously visited coordinates become free to move to so the number of possible walks is more than A001411. The first time this happens is for a(4,6):
.
        *---*---*
        |       ^
        *---X > +
.
The arrows indicate the direction of the walk on its first and second step. By time the sixth step occurs the origin, marked with an 'X', and the coordinate at (1,0), are unoccupied, thus the chain is able to step back to the origin, something not possible in A001411. If the walk starts with one or more steps to the right followed by an upward step this can occur in three ways. These walks can be performed in eight total ways on a 2D lattice so that total number of such walks is 8*3 = 24. Therefore a(4,6) = A001411(6) + 24 = 780 + 24 = 804.
.
The table begins:
.
4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, ...
4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, ...
4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, ...
4, 12, 36, 100, 284, 804, 2276, 6444, 18244, 51652, 146236, 414020, 1172164, ...
4, 12, 36, 100, 284, 804, 2276, 6444, 18244, 51652, 146236, 414020, 1172164, ...
4, 12, 36, 100, 284, 780, 2172, 6028, 16732, 46436, 128892, 357748,  992964, ...
4, 12, 36, 100, 284, 780, 2172, 6028, 16732, 46436, 128892, 357748,  992964, ...
4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44660, 122596, 336428,  923316, ...
4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44660, 122596, 336428,  923316, ...
4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100, 120292, 327908,  893788, ...
4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100, 120292, 327908,  893788, ...
4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100, 120292, 324932,  881500, ...
4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100, 120292, 324932,  881500, ...
...

Crossrefs

Cf. A003946, A001411, A010566.

Sequence in context: A286682 A262621 A255289 * A337403 A203031 A336862

Adjacent sequences: A348331 A348332 A348333 * A348335 A348336 A348337

Keyword

nonn,walk,tabl

Author

Scott R. Shannon, Oct 13 2021

Status

approved