A038373 -id:A038373 - cp's OEIS frontend

A116903 Seaweeds(n): number of n-step self-avoiding walks on upper two quadrants grid starting at origin.

1, 3, 7, 19, 49, 131, 339, 899, 2345, 6199, 16225, 42811, 112285, 296051, 777411, 2049025, 5384855, 14190509, 37313977, 98324565, 258654441, 681552747, 1793492411, 4725856129, 12439233695, 32778031159, 86295460555, 227399388019, 598784536563, 1577923781445, 4155176578581

Offset: 0

Giovanni Resta, Feb 15 2006

nonn

These walks remind me of fluctuant seaweeds anchored to the sea bottom.

			The 19 seaweeds of length 3. X marks the origin = anchor point.
........................................................
O-O-O...O-O.. .O-O...O-O....O..O-O-O...O......O..O-O....
....|.....|.. .|.....|......|..|.......|......|....|....
....X...X-O....O.....O-X....O..X..O-O..O-O....O....O-X..
...............|............|.......|....|....|.........
O-O.....O-O....X....O.......O..O....O....X..X-O.......O.
|.|.....|...........|.......|..|....|.................|.
X.O...X-O.....O-O...O-O-X...X..O....X.....O.........O-O.
..............|.|..............|..........|.........|...
..X-O-O-O.....O.X...O-O-O-X....O-X....X-O-O.........X...
........................................................

M. N. Barber et al., Some tests of scaling theory for a self-avoiding walk attached to a surface, 1978 J. Phys. A: Math. Gen. 11 1833. [_Vladeta Jovovic_, Nov 26 2008]

Cf. A001411, A038373, A116903.

a(23)-a(30) from Scott R. Shannon, Jul 26 2020

A034010 Number of 2n-step self avoiding closed walks on square grid, restricted to a quadrant and passing through origin.

Original entry on oeis.org

0, 1, 2, 6, 20, 74, 300, 1302, 5944, 28266, 139010, 703102, 3641956, 19255106, 103630920, 566522778, 3140130354, 17620845976, 99977635264, 572935630884, 3313078283974

Offset: 1

Felice Russo

			When the number of steps is 8, one of the six closed paths is
0___.
| ._|
|_|

B. Hayes, How to avoid yourself, American Scientist, Vol. 86, Number 4, Jul-August 1998. p. 314-319.

A subset of the polyominoes with perimeter 2n (A006725), also a subset of A002931. Cf. A000105, A038373.

Corrected and extended by David W. Wilson
a(16)-a(18) from Alex Chernov, Jan 22 2012
a(19)-a(21) from Bert Dobbelaere, Jan 06 2019

A046170 Number of self-avoiding walks on a 2-D lattice of length n which start at the origin, take first step in the {+1,0} direction and whose vertices are always nonnegative in x and y.

Original entry on oeis.org

1, 2, 5, 12, 30, 73, 183, 456, 1151, 2900, 7361, 18684, 47652, 121584, 311259, 797311, 2047384, 5260692, 13542718, 34884239, 89991344, 232282110, 600281932, 1552096361, 4017128206, 10401997092, 26957667445, 69892976538, 181340757857, 470680630478, 1222433229262, 3175981845982

Offset: 1

Eric W. Weisstein

Siqi Wang, Table of n, a(n) for n = 1..40
Stephen A. Silver, C program
Siqi Wang, C++ program used to generate the sequence.
Eric Weisstein's World of Mathematics, Self-Avoiding Walk

Cf. A038373, A046171.

a(n) = A038373(n)/2. - Siqi Wang, Jul 15 2022

More terms from Stephen A. Silver

More terms from Siqi Wang, Jul 15 2022

A129700 Number of n-step self-avoiding paths on octant grid starting at octant origin.

Original entry on oeis.org

1, 1, 2, 3, 8, 14, 36, 70, 177, 372, 942, 2056, 5222, 11736, 29878, 68576, 175038, 408328, 1044533, 2468261, 6326688, 15107015, 38791865, 93432564, 240296399, 583001850, 1501520574, 3665682736, 9452895693, 23201772603, 59899677902

Offset: 1

Bill Blewett, Jun 01 2007

Similar to A038373 but with octant grid instead of quadrant. An octant grid is either half of a quadrant grid when divided on the diagonal and including the diagonal grid squares. Its shape is that of a right triangle with a stair step edge on the hypotenuse. Coordinates of squares satisfy x>=0 and y>=0 and x>=y.

Guttmann-Torrie series coefficients c_n^2 for square lattice, with wedge angle Pi/4. - N. J. A. Sloane, Jul 06 2015

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.
Sean A. Irvine, Java program (github)

Cf. A038373.

#include 
#include 
#define GRIDSIZE 20
void Recur(int level, int maxlevel, int rgBd[][GRIDSIZE], int i, int j, int rgCt[]) {
  if (i < 0 || j < 0 || i >= GRIDSIZE || j >= GRIDSIZE || level >= maxlevel || j > i || rgBd[i][j] != 0) return;
  rgCt[level] += 1;
  rgBd[i][j] = 1;
  Recur(level + 1, maxlevel, rgBd, i + 1, j, rgCt);
  Recur(level + 1, maxlevel, rgBd, i - 1, j, rgCt);
  Recur(level + 1, maxlevel, rgBd, i, j + 1, rgCt);
  Recur(level + 1, maxlevel, rgBd, i, j - 1, rgCt);
  rgBd[i][j] = 0;
}
int main(int argc, char **argv) {
  int rgBd[GRIDSIZE][GRIDSIZE] = {0};
  int rgCt[GRIDSIZE] = {0};
  int maxlevel = GRIDSIZE;
  if (argc > 1) {
    maxlevel = atoi(argv[1]);
    if (maxlevel < 0 || maxlevel > GRIDSIZE) {
      printf("Bad argument");
      return 0;
    }
  }
  Recur(0, maxlevel, rgBd, 0, 0, rgCt);
  for (int i = 0; i < maxlevel; i++) printf("%2d ", rgCt[i]);
  return 0;
}

a(28)-a(31) from Sean A. Irvine, Jul 03 2021

A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.

Original entry on oeis.org

1, 3, 15, 75, 391, 2065, 11091, 60215, 330003, 1820869, 10103153, 56313047, 315071801, 1768489771, 9953853677, 56158682949, 317505199769, 1798402412539

Offset: 0

Ricardo Bittencourt, Mar 10 2018

All terms are odd.

			For n=2, the a(2)=15 paths are:
.
.    0 . .     0 . .     0 . .     0 2 .     0 . .
.    |         |         |         |/         \
.    1 . .     1 . .     1-2 .     1 . .     2-1 .
.    |          \
.    2 . .     . 2 .     . . .     . . .     . . .
.
.    0 . .     0 . .     0 . .     0 . .     0 . 2
.     \         \         \         \         \ /
.    . 1 .     . 1 .     . 1 .     . 1-2     . 1 .
.     /          |          \
.    2 . .     . 2 .     . . 2     . . .     . . .
.
.    0 2 .     0-1 .     0-1 .     0-1 .     0-1-2
.     \|        /          |          \
.    . 1 .     2 . .     . 2 .     . . 2     . . .
.
.    . . .     . . .     . . .     . . .     . . .

Ricardo Bittencourt, C++ code, GitHubGist.
Ricardo Bittencourt, Go code, GitHubGist.
OEIS Wiki: Self-avoiding walks

A038373 is the same process, but using only horizontal and vertical moves.

Cf. A005773, A272469, A272763, A272773.

Go
```
(see GitHubGist link)
```

next[x_]:=Map[x + #&, Tuples[{-1, 0, 1}, 2]]
valid[s_]:=Select[next[s[[-1]]], 0<=#[[1]] && 0<=#[[2]] && FreeQ[s,#] &]
nextpath[p_]:=Outer[Append,{p},valid[p],1]
iterate[p_]:=Flatten[Map[nextpath, p], 2]
Table[Length[Nest[iterate, {{{0,0}}}, n-1]], {n,1,7}]

a(n) = A272469(n) + 2*A005773(n+1) - 1 for n > 0. - Andrey Zabolotskiy, Mar 12 2018

A336818 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 size 2b X 2b where the walk starts at the middle of the box.

Original entry on oeis.org

4, 8, 4, 8, 12, 4, 8, 32, 12, 4, 8, 64, 36, 12, 4, 8, 104, 96, 36, 12, 4, 8, 176, 240, 100, 36, 12, 4, 8, 296, 520, 280, 100, 36, 12, 4, 0, 496, 1048, 728, 284, 100, 36, 12, 4, 0, 848, 2104, 1816, 776, 184, 100, 36, 12, 4, 0, 1392, 4168, 4176, 2112, 780, 284, 100, 36, 12, 4

Offset: 1

Scott R. Shannon, Aug 06 2020

			T(1,3) = 8. The one 3-step walk taking a first step to the right followed by a step upward is:
.
+--+
   |
*--+
.
This walk can take a downward second step, and also have a first step in the four possible directions, given a total of 1*2*4 = 8 total walks.
.
The table begins:
.
4  8  8   8   8   8    8    8     0     0      0      0      0       0       0...
4 12 32  64 104 176  296  496   848  1392   2280   3624   5472    8200   10920...
4 12 36  96 240 520 1048 2104  4168  8288  16488  32536  64680  126560  248328...
4 12 36 100 280 728 1816 4176  9304 20400  44216  95680 206104  442984  953720...
4 12 36 100 284 776 2112 5448 13704 32824  77232 178552 409144  932152 2113736...
4 12 36 100 284 780 2168 5848 15672 40472 102816 252992 615328 1472808 3501200...
4 12 36 100 284 780 2172 5912 16192 43360 115328 298856 765864 1919328 4770784...
4 12 36 100 284 780 2172 5916 16264 44016 119392 318328 843848 2194920 5664648...
4 12 36 100 284 780 2172 5916 16268 44096 120200 323856 872920 2321600 6146400...
4 12 36 100 284 780 2172 5916 16268 44100 120288 324832 880232 2363520 6344240...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324928 881392 2372968 6402928...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324932 881496 2374328 6414896...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324932 881500 2374440 6416472...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324932 881500 2374444 6416592...
4 12 36 100 284 780 2172 5916 16268 44100 120292 324932 881500 2374444 6416596...
...

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. A001411 (b->infinity), A336872 (start on edge of box), A116903, A038373.

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

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

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.

A348009 Number of n-step self-avoiding walks on one quadrant of a 2D square lattice where the walk cannot step to the smaller square ring of numbers than the ring it is currently on.

Original entry on oeis.org

1, 2, 4, 10, 22, 52, 118, 282, 646, 1544, 3576, 8546, 19924, 47612, 111536, 266488, 626520, 1496670, 3528470, 8427952, 19913078, 47559756, 112572916, 268857568, 637327742, 1522153378, 3612811784, 8629110414, 20503211908, 48975965026, 116478744692

Offset: 0

Scott R. Shannon, Sep 24 2021

This is a variation of A347990. The same walk rules apply except that the walk is confined to one quadrant of the 2D square lattice. See A347990 for further details.

			a(0..3) are the same as the standard SAW on one quadrant of a square lattice, see A038373, as the walk cannot step to a smaller ring in the first three steps.
a(4) = 22. If we restrict the first one or more steps to the right followed by an upward step then there is one walk which steps to a smaller ring and is thus forbidden. That is the walk (0,0) -> (1,0) -> (2,0) -> (2,1) -> (1,1). As this can be walked in two different ways in one quadrant the number of 4-step walks becomes A038373(4) - 2 = 24 - 2 = 22.

Cf. A347990 (four quadrants), A348008 (two quadrants), A038373, A001411, A337353.

cp's OEIS Frontend

A116903 Seaweeds(n): number of n-step self-avoiding walks on upper two quadrants grid starting at origin.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A034010 Number of 2n-step self avoiding closed walks on square grid, restricted to a quadrant and passing through origin.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A046170 Number of self-avoiding walks on a 2-D lattice of length n which start at the origin, take first step in the {+1,0} direction and whose vertices are always nonnegative in x and y.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A129700 Number of n-step self-avoiding paths on octant grid starting at octant origin.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Extensions

A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Go

Mathematica

Formula

A336818 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 size 2b X 2b where the walk starts at the middle of the box.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Author

Keywords

Examples

Links

Crossrefs

Formula

A348009 Number of n-step self-avoiding walks on one quadrant of a 2D square lattice where the walk cannot step to the smaller square ring of numbers than the ring it is currently on.