A077482 -id:A077482 - cp's OEIS frontend

A174517 Partial sums of A077482.

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

A078528 Number of unconstrained walks on square lattice trapped after n steps.

Original entry on oeis.org

1, 1, 2, 5, 15, 30, 76, 170, 422, 961, 2339, 5390, 12977, 30059, 71918, 167019, 397691, 924931, 2194478, 5107991, 12085695, 28143758, 66442935, 154759821, 364706675, 849562628

Offset: 7

Hugo Pfoertner, Nov 27 2002

See under A078527. In the probability sum in A077483 and A078526 the unconstrained walks are responsible for the occurrence of 3^(n-1) in the denominator of P(n).

			a(7)=1 because the unique shortest walk contains no constrained steps. a(10)=5: See illustration in "5 Unconstrained and 7 maximally 2-constrained walks of length 10" given at link.

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

Cf. A077482, A077483, A078526, A078527, A001411.

Fortran
```
c Program provided at given link
```

a(24)-a(32) from Sean A. Irvine, Jul 03 2025

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.

Original entry on oeis.org

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

Scott R. Shannon, May 13 2020

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.

			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.

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.

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

A323562 Number of rooted self-avoiding king's walks on an infinite chessboard trapped after n moves.

Original entry on oeis.org

8, 200, 2446, 21946, 169782, 1205428, 8119338, 52862872, 336465352, 2108185746

Offset: 8

Hugo Pfoertner, Jan 17 2019

The first step is either (0,0)->(1,0) or (0,0)->(1,1). Rotated paths are not counted separately.
The average number of moves of a self-avoiding random walk of a king on an infinite chessboard to self-trapping is 209.71. The corresponding number of moves for paths with forbidden crossing (A323141) is 69.865.
a(n)=0 for n<8.

			a(8) = 8, because the following 8 walks of 8 moves of a king starting at S with a first move (0,0)->(1,0) visit all neighbors of the trapping location T. The starting point itself is also blocked. There are no such shortest walks with first move (0,0)->(1,1).
.
  o <-- o <-- o   o     o <-- o   o --> o --> o   o <-- o <-- o
  |           ^   ^ \ /       ^   ^           |   |           ^
  v           |   | / \       |   |           v   v           |
  o --> T     o   o     T     o   o     T     o   o     T     o
              ^               ^     \    \    |   |   /       ^
              |               |       \    \  v   v /         |
  S --> o --> o   S --> o --> o   S --> o     o   o     S --> o
.
  S --> o --> o   S --> o --> o   S --> o     o   o     S --> o
              |               |       /    /  ^   ^ \         |
              v               v     /    /    |   |   \       v
  o --> T     o   o     T     o   o     T     o   o     T     o
  ^           |   | \ /       |   |           ^   ^           |
  |           v   v / \       v   v           |   |           v
  o <-- o <-- o   o     o <-- o   o --> o --> o   o <-- o <-- o
- _Hugo Pfoertner_, Jul 23 2020

Hugo Pfoertner, Probability density for the number of moves to self-trapping, (2019).

Cf. A077482, A322831, A323141, A323560, A323561.

A337353 Number of n-step self-avoiding walks on a square lattice where no step can be in the same direction as the previous step.

Original entry on oeis.org

1, 4, 8, 16, 24, 40, 64, 104, 168, 272, 440, 712, 1128, 1808, 2896, 4640, 7368, 11744, 18752, 29920, 47376, 75304, 119824, 190632, 301488, 478160, 759056, 1204848, 1903576, 3014272, 4776504, 7568688, 11947976, 18895760, 29901592, 47317080, 74643504, 117930520, 186413728, 294666160

Offset: 0

Scott R. Shannon, Aug 24 2020

			a(5) = 40. The five possible 5-step walks in the first quadrant are:
.
+--+   +--+         +--+        +--+
|         |            |        |
+--+      +--+      +--+     +--+       +--+
   |         |      |        |          |  |
x--+      x--+   x--+     x--+       x--+  +--+
.
Each of these can be taken in eight ways on the square lattice, giving 40 in total.

A. J. Guttmann and A. R. Conway, Self-Avoiding Walks and Polygons, Annals of Combinatorics 5 (2001) 319-345.

Cf. A001411, A077482, A173380, A334877, A336662.

a(n) = 4*A336662(n).

A323560 Number of self-avoiding knight's paths trapped after n moves on an infinite chessboard with first move specified.

Original entry on oeis.org

1728, 10368, 332660, 1952452

Offset: 15

Hugo Pfoertner, Jan 18 2019

The average number of moves of a self-avoiding random walk of a knight on an infinite chessboard to self-trapping is 3210. The corresponding number of moves for paths with forbidden crossing (A323131) is 45.

a(n)=0 for n<15.

			There are two (of a(15)=1728) paths of 15 moves of minimum extension 5 X 5:
  (N) b1 d2 e4 c5 a4 b2 d1 e3 d5 b4 a2 c1 e2 d4 b5 c3, and
  (N) a4 c5 e4 d2 b1 a3 b5 d4 e2 c1 a2 b4 d5 e3 d1 c3.

Hugo Pfoertner, Illustrations of the 1728 trapped paths of length 15, (2019).
Hugo Pfoertner, Probability density for the number of moves to self-trapping, (2019).

Cf. A077482, A323141, A323559, A323562.

A077483 Numerator of the probability P(n) of the occurrence of a 2D self-trapping walk of length n.

Original entry on oeis.org

2, 5, 31, 173, 1521, 1056, 16709, 184183, 1370009, 474809, 13478513, 150399317, 1034714947, 2897704261

Offset: 7

Hugo Pfoertner, Nov 08 2002

A comparison of the exact probabilities with simulation results obtained for 1.2*10^10 random walks is given under "Results of simulation, comparison with exact probabilities" in the first link. The behavior of P(n) for larger values of n is illustrated in "Probability density for the number of steps before trapping occurs" at the same location. P(n) has a maximum for n=31 (P(31)~=1/85.01) and drops exponentially for large n (P(800)~=1/10^9). The average walk length determined by the numerical simulation is sum n=7..infinity (n*P(n))=70.7598+-0.001

			A077483(10)=173 and A077484(10)=1 because there are 4 different probabilities for the 50 (=2*A077482(10)) walks: 4 walks with probability p1=1/6561, 14 walks with p2=1/8748, 22 walks with p3=1/13122, 10 walks with p4=1/19683. The sum of all probabilities is P(10) = 4*p1+14*p2+22*p3+10*p4 = (12*4+9*14+6*22+4*10)/78732 = 346/78732 = 173 / (3^9 * 2^1)

Alexander Renner, Self avoiding walks and lattice polymers, Diplomarbeit University of Vienna, December 1994
More references are given in the sci.math NG posting in the second link

Hugo Pfoertner, Results for the 2D Self-Trapping Random Walk
Hugo Pfoertner, Self-trapping random walks on square lattice in 2-D (cubic in 3-D).Posting in NG sci.math dated March 4, 2002

Cf. A077484, A077482, A001411.

Fortran
```
c See Hugo Pfoertner link.
```

P(n) = A077483(n) / ( 3^(n-1) * 2^A077484(n) )

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.

Original entry on oeis.org

71, 71, 40, 77, 45, 51, 42, 56, 49, 51, 48, 54

Offset: 3

Hugo Pfoertner, Dec 27 2018

The cases n = 3, 4, and 6 correspond to the usual self-avoiding random walks on the honeycomb net, the square lattice, and the hexagonal lattice, respectively. The other cases n = 5, 7, ... are a generalization using self-avoiding rooted walks similar to those defined in A306175, A306177, ..., A306182. The walk is trapped if it cannot be continued without either hitting an already visited (lattice) point or crossing or touching any straight line connecting successively visited points on the path up to the current point.
The result 71 for n=4 was established in 1984 by Hemmer & Hemmer.
The sequence data are based on the following results of at least 10^9 simulated random walks for each n <= 12, with an uncertainty of +- 0.004 for the average walk length:
   n  length
71.132
70.760 (+-0.001)
40.375
77.150
45.297
51.150
42.049
56.189
48.523
51.486
47.9   (+-0.2)
53.9   (+-0.2)

S. Hemmer, P. C. Hemmer, An average self-avoiding random walk on the square lattice lasts 71 steps, J. Chem. Phys. 81, 584 (1984)
Hugo Pfoertner, Examples of self-trapping random walks.
Hugo Pfoertner, Probability density for the number of steps before trapping occurs, 2018.
Hugo Pfoertner, Results for the 2D Self-Trapping Random Walk.
Alexander Renner, Self avoiding walks and lattice polymers, Diplomarbeit, Universität Wien, December 1994.

Cf. A001668, A001411, A001334, A077482, A306175, A306177, A306178, A306179, A306180, A306181, A306182.

Cf. A122223, A122224, A122226, A127399, A127400, A127401, A300665, A323141, A323560, A323562, A323699.

A323141 Number of self-trapped uncrossed king's paths on an infinite board after n steps, reduced for symmetry.

Original entry on oeis.org

0, 0, 0, 0, 2, 19, 150, 1043, 6843, 43192, 266529, 1619983, 9746883, 58220994, 345919915

Offset: 1

Hugo Pfoertner, Jan 05 2019

The average number of moves of a self-avoiding uncrossed random walk of a king on an infinite chessboard to self-trapping is 69.865+-0.008. - Hugo Pfoertner, Oct 22 2024

			a(5) = 2: There are 2 walks where the king is blocked after 5 steps, because for the diagonal moves it would have to cross its previous path.
.
  o       2       o       o       3        o
        /   \                   /   \
      /       \               /        \
    /           \           /            \
  3       5       1       4 - - - 5        2
  |     /       /                        /
  |   /       /                        /
  | /       /                        /
  4       S       o       S - - -  1       o

Hugo Pfoertner, Probability density for the number of moves to self-trapping, (2019).

Cf. A003192, A077482, A272773, A323140, A323562.

A334602 Number of self-avoiding walks on a 2-dimensional square lattice where the walk consists of steps of length 1 to n which can be taken in any order.

Original entry on oeis.org

1, 4, 24, 216, 2544, 36832, 632736, 12566016, 283849872, 7179191888, 200946557168, 6165203252096

Offset: 0

Scott R. Shannon, May 07 2020

This sequence gives the number of self-avoiding walks on a 2-dimensional square lattice where the walk consists of steps of length 1 to n which can be taken in any order. Walks which visit the same lattice coordinates but are done so by taking steps of the same length in different order are considered to be different walks. For example a walk consisting of steps with length 1 and 2 to the right is counted as a different walk to one with step lengths 2 and 1 to the right.

The first time a collision with a previous step can occur is for n = 4. If we only consider the first step being taken to the right then there are six ways this can occur. These are 2R->3U->1L->4D, 3R->1U->2L->4D, 3R->2U->1L->4D, 4R->1U->2L->3D, 4R->1U->3L->2D, 4R->2U->1L->3D, where the number is the step length and R,L,U,D are directions right,left,up and down from the origin.

			a(1) = 4. These are the four directions one can step 1 unit away from the origin on a 2D square lattice.
a(2) = 24. These consist of the following four walks:
.
    *
    |             *        1     2            2     1
    . 2           | 1    *---*---.---*    *---.---*---*
    |     *---.---*
*---*         2
  1
.
The first two can be walked in eight different ways on a 2D lattice, the last two in four different ways, giving a total of 2*8+2*4 = 24.
a(3) = 216. Restricting the first step to the right then the different ways a walk can take three steps on a 2D lattice within the first quadrant are RUL, RUU, RUR, RRU, RRR. Each of these can be taken in 6 ways, the arrangements of 1,2,3. The first four walks can also be taken in eight ways on the 2D lattice, the last in four ways, giving a total of 4*8*3!+1*4*3! = 216.
a(4) = 2544. Restricting the first step to the right then the different ways a walk can take four steps on a 2D lattice within the first quadrant are RULD, RULL, RULU, RUUL, RUUU, RUUR, RURU, RURR, RURD, RRUL, RRUU, RRUR, RRRU, RRRR. Each of these can be taken in 24 ways, the arrangements of 1,2,3,4. However six of these walks are forbidden due to the collisions given in the comments. The first thirteen walks can also be taken in eight ways on the 2D lattice, the fourteenth in four ways. This gives a total number of walks of 13*8*4! - 6*8 + 4*4! = 2544.

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.

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

cp's OEIS Frontend

A174517 Partial sums of A077482.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A078528 Number of unconstrained walks on square lattice trapped after n steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Fortran

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A323562 Number of rooted self-avoiding king's walks on an infinite chessboard trapped after n moves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A337353 Number of n-step self-avoiding walks on a square lattice where no step can be in the same direction as the previous step.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A323560 Number of self-avoiding knight's paths trapped after n moves on an infinite chessboard with first move specified.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A077483 Numerator of the probability P(n) of the occurrence of a 2D self-trapping walk of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Fortran

Formula

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi*(2*k/n - 1), k = 1..n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

A323141 Number of self-trapped uncrossed king's paths on an infinite board after n steps, reduced for symmetry.

Views

Author

Keywords

Comments

Examples

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.