A001411 -id:A001411 - cp's OEIS frontend

A078798 Sum of Manhattan distances over all self-avoiding n-step walks on square lattice. Numerator of mean Manhattan displacement s(n) = a(n)/A046661(n).

1, 6, 23, 80, 263, 834, 2569, 7764, 23095, 67910, 197607, 570560, 1635331, 4661026, 13212739, 37296004, 104836893, 293710714, 820132581, 2283926980, 6343214871, 17578257134, 48604029143, 134141458280, 369519394643

Offset: 1

Hugo Pfoertner, Dec 10 2002

A conjectured asymptotic behavior for the mean Manhattan displacement lim n-> infinity a(n)/(A046661(n)*n^(3/4)) = constant is illustrated in "Asymptotic Behavior of Mean Manhattan Displacement" at first link.

			a(3)=23 because 2 of the A046661(3)=9 walks end at Manhattan distance 1: (0,-1),(0,1) and 7 walks end at Manhattan distance 3: (1,-2),(1,2),2*(2,-1),2*(2,1),(3,0); a(3)=2*1+7*3=23 See also "Distribution of end point distance" at first link.

See under A001411.

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

Cf. A001411, A046661, A078797.

c Source code of "FORTRAN program for distance counting" available at first link.

a(n) = Sum_{k=1..A046661(n)} (|i_k| + |j_k|) where (i_k, j_k) are the end points of all different self-avoiding n-step walks.

a(1)=1 inserted by Sean A. Irvine, Jul 16 2025

A140476 Number of self-avoiding walks on cubic lattice with no more than n steps.

Original entry on oeis.org

1, 7, 37, 187, 913, 4447, 21373, 102763, 490729, 2344615, 11154493, 53088643, 251931385, 1195905895, 5664817573, 26839963627, 126961839601, 600692091703, 2838415775797, 13414448995411, 63331776834145, 299041867336303

Offset: 0

Jonathan Vos Post, Jun 29 2008

nonn

Primes include a(1) = 7, a(2) = 37, a(5) = 4447, a(8) = 102763, a(15) = 26839963627.

			a(9) = 1 + 6 + 30 + 150 + 726 + 3534 + 16926 + 81390 + 387966 + 1853886 = 2344615.

Partial sums of A001412.

Cf. A001411, A001412, A001413, A002902, A078717.

A174517 Partial sums of A077482.

Original entry on oeis.org

1, 3, 14, 39, 134, 362, 1114, 2974, 8715, 23192, 66131, 175889, 493036, 1311265, 3633777, 9664070, 26564611, 70644166, 193023433, 513251110, 1395938840, 3711196199, 10057272214, 26732694893, 72234863272, 191962874523, 517473126631, 1374873851835

Offset: 7

Jonathan Vos Post, Mar 21 2010

Partial sums of number of self-avoiding walks on square lattice trapped after n steps.

A self-trapping walk is a walk which ends when the walker is "trapped" or surrounded by previously visited sites on the lattice.

			a(16) = 1 + 2 + 11 + 25 + 95 + 228 + 752 + 1860 + 5741 + 14477 = 23192.

B. D. Hughes, Random Walks and Random Environments, Vol. I OUP, 1995.
N. Madras & G. Slade, The Self-Avoiding Walk, Birkhäuser, 1993.

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

Cf. A077482, A046661, A001411, A322831.

a(n) = Sum_{i=7..n} A077482(i).

a(26)-a(28) from Alois P. Heinz, Jun 16 2011

a(29)-a(34) from Bert Dobbelaere, Jan 03 2019

A272265 Number of n-step tri-directional self-avoiding walks on the hexagonal lattice.

Original entry on oeis.org

1, 3, 9, 21, 51, 123, 285, 669, 1569, 3603, 8343, 19335, 44193, 101577, 233697, 532569, 1218345, 2789475, 6343161, 14464101, 33004269, 74923059, 170440203, 387945747, 879473277, 1997066751, 4536975315, 10273846185

Offset: 0

Francois Alcover, May 05 2016

Only 3 directions are allowed, separated by 120 degrees.
  o
  x
o   o

Cf. A001334.

mo={{2, 0},{-1, 1}, {-1, -1}}; a[0]=1;
a[tg_, p_:{{0, 0}}] := Block[{e, mv = Complement[Last[p]+# & /@ mo, p]}, If[tg == 1, Length@mv, Sum[a[tg-1, Append[p, e]], {e, mv}]]];
a /@ Range[0, 10]
(* Robert FERREOL, Nov 28 2018; after the program of Giovanni Resta in A001411 *)

def add(L, x):
    M=[y for y in L]; M.append(x)
    return(M)
plus=lambda L, M : [x+y for x, y in zip(L, M)]
mo=[[2, 0], [-1, 1], [-1, -1]]
def a(n, P=[[0, 0]]):
    if n==0: return(1)
    mv1 = [plus(P[-1], x) for x in mo]
    mv2=[x for x in mv1 if x not in P]
    if n==1: return(len(mv2))
    else: return(sum(a(n-1, add(P, x)) for x in mv2))
print([a(n) for n in range(11)])
# Robert FERREOL, Nov 30 2018

A330079 Number of n-step self-avoiding walks starting at the origin that are restricted to the boundary walls of the first octant of the cubic lattice.

Original entry on oeis.org

1, 3, 9, 27, 75, 213, 585, 1623, 4425, 12123, 32883, 89415, 241557, 653649, 1760427, 4747005, 12754593, 34301463, 91990575, 246880023, 661075149, 1771199169, 4736741853, 12673587057, 33856816431, 90482953989, 241499070195, 644781165933, 1719559634451, 4587222964881, 12225165127887

Offset: 0

Francois Alcover, Nov 30 2019

These are walks in the first octant of the cubic lattice, never leaving the three walls forming the octant. The walls are the sets of points (x>=0, y>=0, z=0), (x>=0, y=0, z>=0), and (x=0, y>=0, z>=0) with (x,y,z) in Z^3.

Francois Alcover, 14-step walk
Francois Alcover, nodejs script

Cf. A001411, A001412.

The "snake in the box" problem (A000937, A099155) has a similar flavor. - N. J. A. Sloane, Dec 01 2019

a(18)-a(25) Scott R. Shannon, Aug 17 2020

a(26)-a(30) from Bert Dobbelaere, Oct 28 2023

A335307 The number of hanging vertically stable self-avoiding walks of length n on a 2D square lattice where only the nodes have mass.

Original entry on oeis.org

1, 1, 1, 1, 5, 13, 31, 63, 141, 293, 665, 1553, 3795, 9225, 22257, 53623, 132277, 321651, 786553, 1928565, 4806503, 11885969, 29498995, 73362933, 184210629, 460165983, 1151961103

Offset: 1

Scott R. Shannon, Sep 12 2020

This is a variation of A335780 where only the nodes have mass. See that sequence for further details of the allowed walks.

			a(1)-a(4) = 1 as the only stable walk is a walk straight down from the first node.
a(5) = 5. There are two stable walks with a first step to the right:
.
      X-----+
            |     +     X-----+
            |     |           |
+-----+-----+     |           |
|                 +-----+-----+
|
+
.
Assuming a node mass of p, both walks have a torque of 2p to the right and 2p to the left of the first node. These walks can be taken in 2 ways. Thus, with the straight down walk, the total number of stable walks is 2*2+1 = 5.

Cf. A335780 (rods and nodes have mass), A335596 (only rods have mass), A116903, A337761, A001411, A001412.

A335596 The number of hanging vertically stable self-avoiding walks of length n on a 2D square lattice where only the connecting rods have mass.

Original entry on oeis.org

1, 1, 1, 1, 3, 7, 17, 43, 91, 183, 371, 799, 1941, 4621, 11463, 27823, 68997, 167481, 414045, 1006091, 2496981, 6127053, 15304071, 37838777, 95041475, 236320611, 595206771

Offset: 1

Scott R. Shannon, Sep 13 2020

This is a variation of A335780 where only the rods between the nodes have mass. See that sequence for further details of the allowed walks.

			a(1)-a(4) = 1 as the only stable walk is a walk straight down from the first node.
a(5) = 3. There is one stable walk with a first step to the right:
.
            X-----+
                  |
                  |
+-----+-----+-----+
,
Assuming a rod mass of q, the total torque to the right of the first node is 2*q*(1/2) + 1*q*1 = 2q. The total torque to the left of the first node is 1*q*(1/2) + 1*q*(3/2) = 2q. This walk can be taken in 2 ways. Thus, with the straight down walk, the total number of stable walks is 2+1 = 3.

Cf. A335780 (rods and nodes have mass), A335307 (only nodes have mass), A116903, A337761, A001411, A001412.

A336769 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 h where the walk starts at the origin.

Original entry on oeis.org

3, 6, 3, 12, 7, 3, 20, 18, 7, 3, 36, 40, 19, 7, 3, 58, 86, 48, 19, 7, 3, 100, 170, 120, 49, 19, 7, 3, 160, 350, 274, 130, 49, 19, 7, 3, 268, 688, 620, 326, 131, 49, 19, 7, 3, 430, 1394, 1346, 810, 338, 131, 49, 19, 7, 3, 708, 2702, 2972, 1912, 884, 339, 131, 49, 19, 7, 3

Offset: 1

Scott R. Shannon, Aug 04 2020

			T(1,3) = 12. The six 3-step walks taking a first step to the right or a first step upward followed by a step to the right are:
.
                  +  +--+     +--+  +--+--+  +--+
                  |     |     |     |        |  |
+--+--+--+  +--+--+  +--+  +--+     +        +  +
.
The same steps can be taken to the left, giving a total of 2*6 = 12 walks.
.
The table begins:
.
3 6 12 20  36  58 100  160  268   430   708   1140   1860   3002    4876    7880...
3 7 18 40  86 170 350  688 1394  2702  5338  10278  20078  38578   74820  143496...
3 7 19 48 120 274 620 1346 2972  6402 13994  29870  64412 136308  291008  612920...
3 7 19 49 130 326 810 1912 4486 10262 23634  53642 122624 276524  627248 1405154...
3 7 19 49 131 338 884 2228 5560 13438 32320  76440 181202 425138 1001128 2336886...
3 7 19 49 131 339 898 2328 6050 15320 38478  94642 231798 560794 1357098 3258148...
3 7 19 49 131 339 899 2344 6180 16040 41572 105806 267560 666682 1655140 4070280...
3 7 19 49 131 339 899 2345 6198 16204 42586 110636 286682 733032 1865008 4693178...
3 7 19 49 131 339 899 2345 6199 16224 42788 112016 293908 764248 1982070 5089002...
3 7 19 49 131 339 899 2345 6199 16225 42810 112260 295734 774682 2030988 5286652...
3 7 19 49 131 339 899 2345 6199 16225 42811 112284 296024 777042 2045610 5360672...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296050 777382 2048600 5380646...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777410 2048994 5384370...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777411 2049024 5384822...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777411 2049025 5384854...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777411 2049025 5384855...
...

Cf. A116903 (h->infinity), A038577 (h=1), A302408 (h=2), A001411, A038373.

For n <= h, T(h,n) = A116903(n).
Row 1 = T(1,n) = A038577(n).
Row 2 = T(2,n) = A302408(n).

A336863 Table read by antidiagonals: T(b,n) is the number of n-step self avoiding walks on a 2D square grid confined inside an infinite well of width 2b where the walk starts at the middle of the well bottom.

Original entry on oeis.org

3, 5, 3, 11, 7, 3, 19, 17, 7, 3, 41, 39, 19, 7, 3, 79, 85, 47, 19, 7, 3, 163, 187, 119, 49, 19, 7, 3, 163, 187, 119, 49, 19, 7, 3, 305, 425, 273, 129, 49, 19, 7, 3, 603, 955, 657, 325, 131, 49, 19, 7, 3, 1143, 2169, 1517, 809, 337, 131, 49, 19, 7, 3

Offset: 1

Scott R. Shannon, Aug 07 2020

			The infinite well of width 2b is:
.                           .
.                           .
+                           +
|                           |
+                           +
|                           |
+---+-- ... --X-- ... --+---+
<------b----->
.
T(1,3) = 11. The five 3-step walks taking a first step to the right or upward steps followed by a step to the right are:
.
   +                    +   +--+
   |                    |   |
   +   +--+   +--+   +--+   +
   |      |   |  |   |      |
*--+   *--+   *  +   *      *
.
These walks can also take similar steps to the left. There is also one 3-step walk directly upward, given a total of 5*2+1 = 11 walks.
The table begins:
.
3 5 11 19  41  79 163  305  603  1143  2231   4257   8233  15721   30265   57871...
3 7 17 39  85 187 425  955 2169  4867 10961  24439  54583 121079  269073  595295...
3 7 19 47 119 273 657 1517 3645  8517 20435  48029 114961 270681  645759 1519165...
3 7 19 49 129 325 809 1979 4817 11703 28475  69255 168749 410905 1002425 2443189...
3 7 19 49 131 337 883 2227 5669 14017 35109  86465 215531 531041 1321687 3260577...
3 7 19 49 131 339 897 2327 6049 15485 39421  99651 251065 631073 1584165 3973513...
3 7 19 49 131 339 899 2343 6179 16039 41809 107261 276041 701555 1790849 4530571...
3 7 19 49 131 339 899 2345 6197 16203 42585 110963 288833 746717 1925057 4942513...
3 7 19 49 131 339 899 2345 6199 16223 42787 112015 294345 767319 2003283 5188119...
3 7 19 49 131 339 899 2345 6199 16225 42809 112259 295733 775251 2035247 5318433...
3 7 19 49 131 339 899 2345 6199 16225 42811 112283 296023 777041 2046335 5366435...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296049 777381 2048599 5381553...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777409 2048993 5384369...
...

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 and A. R. Conway, Self-Avoiding Walks and Polygons, Annals of Combinatorics 5 (2001) 319-345.

Cf. A116903 (b->infinity), A001411, A038373.

For n <= b, T(b,n) = A116903(n).

A336872 Table read by antidiagonals: T(b,n) is the number of n-step self avoiding walks on a 2D square grid confined inside a square box of dimension 2b X 2b where the walk starts at the middle of one of the box's edges.

Original entry on oeis.org

3, 5, 3, 10, 7, 3, 10, 17, 7, 3, 16, 39, 19, 7, 3, 10, 84, 47, 19, 7, 3, 14, 174, 119, 49, 19, 7, 3, 0, 336, 273, 129, 49, 19, 7, 3, 0, 634, 656, 325, 131, 49, 19, 7, 3, 0, 1072, 1500, 809, 337, 131, 49, 19, 7, 3, 0, 1856, 3496, 1979, 883, 339, 131, 49, 19, 7, 3

Offset: 1

Scott R. Shannon, Aug 06 2020

			T(1,3) = 10. The five 3-step walks taking a first step to the right or upward steps followed by a step to the right are:
.
   +                    +   +--+
   |                    |   |
   +   +--+   +--+   +--+   +
   |      |   |  |   |      |
*--+   *--+   *  +   *      *
.
This walk can also take similar steps to the left, given a total of 5*2 = 10 walks.
.
The table begins:
.
3 5 10 10  16  10  14    0    0     0     0      0      0      0       0       0...
3 7 17 39  84 174 336  634 1072  1856  2888   4598   6526   9198   11504   13758...
3 7 19 47 119 273 656 1500 3496  7612 16762  34214  71932 140664  286522  540490...
3 7 19 49 129 325 809 1979 4816 11682 28250  67606 159380 370530  842432 1902126...
3 7 19 49 131 337 883 2227 5669 14017 35108  86440 215214 528312 1303650 3162374...
3 7 19 49 131 339 897 2327 6049 15485 39421  99651 251064 631044 1583740 3969304...
3 7 19 49 131 339 899 2343 6179 16039 41809 107261 276041 701555 1790848 4530538...
3 7 19 49 131 339 899 2345 6197 16203 42585 110963 288833 746717 1925057 4942513...
3 7 19 49 131 339 899 2345 6199 16223 42787 112015 294345 767319 2003283 5188119...
3 7 19 49 131 339 899 2345 6199 16225 42809 112259 295733 775251 2035247 5318433...
3 7 19 49 131 339 899 2345 6199 16225 42811 112283 296023 777041 2046335 5366435...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296049 777381 2048599 5381553...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777409 2048993 5384369...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777411 2049023 5384821...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777411 2049025 5384853...
3 7 19 49 131 339 899 2345 6199 16225 42811 112285 296051 777411 2049025 5384855...
...

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 and A. R. Conway, Self-Avoiding Walks and Polygons, Annals of Combinatorics 5 (2001) 319-345.

Cf. A116903 (b->infinity), A336818 (start at middle of box), A001411, A038373.

For n <= b, T(b,n) = A116903(n).

For n >= b^2, T(b,n) = 0 as the walks have more steps than there are free grid points inside the box.

cp's OEIS Frontend

A078798 Sum of Manhattan distances over all self-avoiding n-step walks on square lattice. Numerator of mean Manhattan displacement s(n) = a(n)/A046661(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Fortran

Formula

Extensions

A140476 Number of self-avoiding walks on cubic lattice with no more than n steps.

Views

Author

Keywords

Comments

Examples

Crossrefs

A174517 Partial sums of A077482.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A272265 Number of n-step tri-directional self-avoiding walks on the hexagonal lattice.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

A330079 Number of n-step self-avoiding walks starting at the origin that are restricted to the boundary walls of the first octant of the cubic lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A335307 The number of hanging vertically stable self-avoiding walks of length n on a 2D square lattice where only the nodes have mass.

Views

Author

Keywords

Comments

Examples

Crossrefs

A335596 The number of hanging vertically stable self-avoiding walks of length n on a 2D square lattice where only the connecting rods have mass.

Views

Author

Keywords

Comments

Examples

Crossrefs

A336769 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 h where the walk starts at the origin.

Views

Author

Keywords

Examples

Crossrefs

Formula

A336863 Table read by antidiagonals: T(b,n) is the number of n-step self avoiding walks on a 2D square grid confined inside an infinite well of width 2b where the walk starts at the middle of the well bottom.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A336872 Table read by antidiagonals: T(b,n) is the number of n-step self avoiding walks on a 2D square grid confined inside a square box of dimension 2b X 2b where the walk starts at the middle of one of the box's edges.

Views