A001411 -id:A001411 - cp's OEIS frontend

A336988 Table read by antidiagonals: T(h,n) is the number of n-step self avoiding walks on a 2D square grid confined to an infinite strip of height 2h where the walk starts at coordinate (0,h).

4, 10, 4, 22, 12, 4, 42, 34, 12, 4, 90, 82, 36, 12, 4, 182, 194, 98, 36, 12, 4, 382, 438, 262, 100, 36, 12, 4, 742, 1034, 650, 282, 100, 36, 12, 4, 1486, 2362, 1610, 754, 284, 100, 36, 12, 4, 2866, 5558, 3870, 1994, 778, 284, 100, 36, 12, 4

Offset: 1

Scott R. Shannon, Aug 10 2020

			T(1,3) = 22. The five 3-step walks taking a first step to the right and upward or a step upward and then to the right are:
.
      +  +--+     +--+  +--+--+  +--+
      |     |     |     |        |  |
X--+--+  X--+  X--+     X        X  +
.
The same steps can be taken to the right then down, to the left then down, and to the left then up. There is also the two straight walks right and left. This give a total number of walks of 4*5+2 = 22.
.
The table begins:
.
4 10 22  42  90 182  382  742  1486  2866   5646  10878  21198   40694   78758...
4 12 34  82 194 438 1034 2362  5558 12662  29366  66330 151566  339514  767798...
4 12 36  98 262 650 1610 3870  9490 22830  55826 134242 326934  784770 1901246...
4 12 36 100 282 754 1994 5046 12786 31746  79566 196858 491506 1214262 3024890...
4 12 36 100 284 778 2142 5682 14986 38462  98762 249894 635290 1599394 4048366...
4 12 36 100 284 780 2170 5882 15970 42286 111554 288962 748414 1916762 4921146...
4 12 36 100 284 780 2172 5914 16230 43730 117810 311894 823682 2146886 5593690...
4 12 36 100 284 780 2172 5916 16266 44058 119842 321630 862674 2284682 6040622...
4 12 36 100 284 780 2172 5916 16268 44098 120246 324394 877210 2348022 6281498...
4 12 36 100 284 780 2172 5916 16268 44100 120290 324882 880866 2368982 6380418...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324930 881446 2373706 6409762...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324932 881498 2374386 6415746...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324932 881500 2374442 6416534...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324932 881500 2374444 6416594...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324932 881500 2374444 6416596...

Cf. A336769 (start at origin), A001411 (h->infinity), A007825 (h=1), A116903, A038373, A336863, A336818.

For n <= h, T(h,n) = A001411(n).

Row 1 = T(1,n) = A007825(n).

A337367 Sum of square end-to-end distance over all self-avoiding n-step walks on a square lattice where no adjacent points are allowed, except those for consecutive steps.

Original entry on oeis.org

0, 4, 32, 156, 608, 2116, 6816, 20844, 61376, 175628, 491248, 1349172, 3650144, 9751532, 25774672, 67501556, 175375136, 452454276, 1160098576, 2958123556, 7505767840, 18959922796, 47701159264, 119570463980, 298719578688, 743984084700, 1847709517360, 4576818079076, 11309417827072

Offset: 0

Scott R. Shannon, Aug 25 2020

The corresponding number of n-step walks is given in A173380.

			The allowed 4-step walks with their associated end-to-end square distances are:
.
         + 10
4        |        8              8      8           16
+--+     +     +--+              +      +    X--+---+---+---+
   |     |     |          10     |      |
   +     +     +     +--+--+  +--+      +        +--+ 10      + 10
   |     |     |     |        |         |        |            |
X--+  X--+  X--+  X--+     X--+   X--+--+  X--+--+   X--+--+--+
.
The eight non-straight walks sum to 68, and these can be walked in eight ways on the square lattice. The remaining straight walk can be walking in four ways. Thus a(4) = 68 * 8 + 16 * 4 = 608.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes the sequence A173380).

Sequence Fans Mailing list, discussion of the sequence A173380, November 2010.

Cf. A173380, A001411.

A348010 Number of n-step self-avoiding walks on the upper half-plane of a 2D square lattice rotated by Pi/4.

Original entry on oeis.org

1, 2, 6, 14, 40, 96, 268, 664, 1820, 4588, 12464, 31712, 85704, 219376, 590640, 1518652, 4077112, 10518364, 28177388, 72883016, 194910964, 505202708, 1349189968, 3503014492, 9344407884, 24296044256, 64748290040, 168550939272

Offset: 0

Scott R. Shannon, Sep 24 2021

			The rotated lattice, where * is the origin and + are the lattice points, is:
      +       +       +       +
        \   /   \   /   \   /
          +       +       +
        /   \   /   \   /   \
      +       +       +       +
        \   /   \   /   \   /
     -----+-------*-------+------
.
a(1) = 2 as the only two steps available are the diagonal steps to the northeast and northwest of the origin.
a(2) = 6 as from each of the available first steps three steps are possible, giving a total of 2 * 3 = 6 steps.

A. J. Guttmann and G. M. Torrie, Critical behavior at an edge for the SAW and Ising model, J. Phys. A 17 (1984), 3539-3552.

Cf. A116903 (not rotated), A001411.

A348057 Number of n-step self-avoiding walks on three quadrants of a 2D square lattice.

Original entry on oeis.org

1, 4, 10, 28, 74, 202, 534, 1442, 3822, 10258, 27202, 72718, 192840, 514228, 1363342, 3629316, 9619264, 25575326, 67765590, 180001304, 476807826, 1265567600, 3351529410, 8890447682, 23538665948, 62409037914, 165202281046

Offset: 0

Scott R. Shannon, Sep 26 2021

			a(2) = 10. Assuming the lower left quadrant is the one removed then a walk of left-down or down-left is not permitted, so the total number of 2-step walks is 4 * 3 - 2 = 10.

Cf. A001411 (four quadrants), A116903 (two quadrants), A038373 (one quadrant), A129700 (half quadrant).

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

Original entry on oeis.org

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

Scott R. Shannon, Oct 13 2021

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.

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

Cf. A003946, A001411, A010566.

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

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

A368614 Number of n-step self-avoiding walks on a 2D square lattice where each visited lattice point is either a neighbor of the first visited lattice point, else the first visited lattice point is directly visible (cf. A358036) from the lattice point when it is first visited.

Original entry on oeis.org

4, 8, 16, 24, 48, 80, 168, 296, 624, 1144, 2424, 4552, 9680, 18480, 39368, 76128, 162376, 317288, 677624, 1335688, 2856536, 5672576, 12149080, 24280768, 52079424, 104665200, 224825088, 454047672, 976721744, 1981083216, 4267578200, 8689274768, 18743542208, 38295782400, 82715689712

Offset: 1

Scott R. Shannon, Dec 31 2023

The sequence counts the number of SAWs on the square lattice where, after the first step, all subsequent visited lattice points must be such that the first lattice point is directly visible from it when it is first visited - see A358036 for the definition of visibility.

			a(4) = 24. For walks with a second step in the first quadrant, there are three 4-step saws where the first lattice point is either a neighbor or directly visible from each point as it is first visited. These are:
.
  .---.---.   .---.     .
          |       |     |
      X---.       .     .
                  |     |
              X---.     .
                        |
                    X---.
.
where 'X' marks the position of the first lattice point. These three walks can be taken in eight ways on the 2D square lattice, so the total number of walks is 3 * 8 = 24.

Cf. A358036, A358046, A001411, A337353.

A381979 Decimal expansion of the expected number of steps to termination by self-trapping of a self-avoiding random walk on the square lattice.

Original entry on oeis.org

7, 0, 7, 5, 9

Offset: 2

Yi Yang, Mar 11 2025

The average walk length determined by 1.2*10^12 simulations is 70.75915 +- 0.00010

			70.759...

See under A001411.

Hugo Pfoertner, Results for the 2-dimensional Self-Trapping Random Walk.

Cf. A378903 (The expected walk length on the cubic lattice).
Cf. A077483 (Probability of the occurrence of each walk length).
Cf. A322831.

cp's OEIS Frontend

A336988 Table read by antidiagonals: T(h,n) is the number of n-step self avoiding walks on a 2D square grid confined to an infinite strip of height 2h where the walk starts at coordinate (0,h).

Views

Author

Keywords

Examples

Crossrefs

Formula

A337367 Sum of square end-to-end distance over all self-avoiding n-step walks on a square lattice where no adjacent points are allowed, except those for consecutive steps.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A348010 Number of n-step self-avoiding walks on the upper half-plane of a 2D square lattice rotated by Pi/4.

Views

Author

Keywords

Examples

Links

Crossrefs

A348057 Number of n-step self-avoiding walks on three quadrants of a 2D square lattice.

Views

Author

Keywords

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A368614 Number of n-step self-avoiding walks on a 2D square lattice where each visited lattice point is either a neighbor of the first visited lattice point, else the first visited lattice point is directly visible (cf. A358036) from the lattice point when it is first visited.

Views

Author

Keywords

Comments

Examples

Crossrefs

A381979 Decimal expansion of the expected number of steps to termination by self-trapping of a self-avoiding random walk on the square lattice.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs