A001411 -id:A001411 - cp's OEIS frontend

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.

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.

A046661 Number of n-step self-avoiding walks on the square lattice with first step specified.

Original entry on oeis.org

1, 3, 9, 25, 71, 195, 543, 1479, 4067, 11025, 30073, 81233, 220375, 593611, 1604149, 4311333, 11616669, 31164683, 83779155, 224424291, 602201507, 1611140121, 4316653453, 11536599329, 30870338727, 82428196555, 220329372907

Offset: 1

N. J. A. Sloane

Used as the denominator for the mean square displacement of all different self-avoiding n-step walks in A078797. - Hugo Pfoertner, Dec 09 2002

Number of ways a toy snake with n segments can be bent without flipping the snake upside down. Each segment must be perpendicular or parallel with each adjacent segment. A "slither" is a way of writing down the configuration of a snake; starting from the tail, write down which direction the next segment is pointing (R for right, S for straight, L for left). E.g., a snake with 10 segments may have the valid slither RLRRLLRRL, but not RSRRSSLSL.

Hugo Pfoertner, Table of n, a(n) for n = 1..79
G. T. Barkema and S. Flesia, Two-dimensional oriented self-avoiding walks with parallel contacts, J. Stat. Phys. 85 (1996) no 3/4, 363-381. [a(30) to a(34)]
D. Bennet-Wood, J. L. Cardy, S. Flesia, A. J. Guttmann et al., Oriented self-avoiding walks with orientation-dependent interactions, J. Phys. A: Math. Gen. 28 (1995) no 18, 5143-5163. [up to a(29)]
V. Hart, How to Snakes, Youtube Video (2011).

Cf. A001411, A002900, A078797.

(* b = A001411 *) mo = Tuples[{-1, 1}, 2]; b[0] = 1; b[tg_, p_:{{0, 0}}] := b[tg, p] = Block[{e, mv = Complement[Last[p] + #& /@ mo, p]}, If[tg == 1, Length[mv], Sum[b[tg - 1, Append[p, e]], {e, mv}]]];
a[n_] := b[n]/4;
Table[an = a[n]; Print[an]; an, {n, 1, 16}] (* Jean-François Alcover, Nov 02 2018, after Giovanni Resta in A001411 *)

a(n) = A001411(n)/4 = A002900(n)/2.

A272773 Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).

Original entry on oeis.org

1, 8, 56, 360, 2240, 13696, 82808, 496656, 2961136, 17573608, 103911424, 612577272, 3602222736, 21137815952, 123811421128, 724064474968, 4228582808424

Offset: 0

Giovanni Resta, May 06 2016

The path cannot return to a lattice point nor intersect with itself (which IS allowed in A272763).

The Moore neighborhood characterizes king tours. - Rainer Rosenthal, Jan 06 2019

Cf. A272763, A001411, A323140, A323141.

# For starting point stp and list Ldir of n directions (1..8)
# construct the points of the whole path and count them.
# In order to avoid crossings consider the n midpoints, too.
# If there are 2*n+1 then the path is self-avoiding and uncrossed.
isNice := proc(Ldir) local Delta, dir, ep, mp, path;
   Delta := [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]];
   ep := [0,0]; path := {ep};
   for dir in Ldir do
      mp := ep + Delta[dir];
      ep := mp + Delta[dir];
      path := {op(path), mp, ep};
   od;
   return evalb(nops(path)=2*nops(Ldir)+1);
end:
# Count only king tours which are nice, i.e. self-avoiding and uncrossed.
A272773 := proc(n) local count, T, p;
   count := 0:
   T := combinat[cartprod]([seq([$1..8], j=1..n)]):
   while not T[finished] do
      p := T[nextvalue]();
      if isNice(p) then count := count+1; fi;
   od:
   return count;
end: # Rainer Rosenthal, Jan 06 2019

mo = Most@Tuples[{-1, 1, 0}, 2]; a[0] = 1; a[tg_, p_: {{0, 0}}] := Block[{e, z = Last@p, w, mv = {}}, Do[w = {z+e, z+2*e}; If[Intersection[w, p] == {}, AppendTo[mv, w]], {e, mo}]; If[tg == 1, Length[mv], Sum[a[tg-1, Join[p, e]], {e, mv}]]]; a /@ Range[0, 7] (* Corrected following a suggestion by Rainer Rosenthal, Giovanni Resta, Jan 06 2019 *)

a(5)-a(7) corrected by Rainer Rosenthal, Jan 06 2019

a(8)-a(16) from Hugo Pfoertner, Jan 06 2019

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

A078797 Sum of square displacements over all self-avoiding n-step walks on a square lattice with the first step specified. Numerator of mean square displacement s(n)=a(n)/A046661(n).

Original entry on oeis.org

1, 8, 41, 176, 679, 2452, 8447, 28120, 91147, 289324, 902721, 2777112, 8441319, 25398500, 75744301, 224156984, 658855781, 1924932324, 5593580859, 16175728584, 46572304083, 133556779740, 381611332725, 1086759598120

Offset: 1

Hugo Pfoertner, Dec 05 2002

A comparison with the conjectured asymptotic behavior of the mean square displacement s(n) over all n-step self-avoiding walks given in E. Weisstein's MathWorld article is shown in the "Asymptotic Behavior of Mean Square Displacement" link. [I'm not sure this comment is correct. There may be some confusion with A176177. - N. J. A. Sloane, Aug 02 2015]

			Example: a(2)=8 because the A046661(2)=3 different self-avoiding 2-step walks end at (1,-1),(1,1)->d^2=2 and at (2,0)->d^2=4, so a(2) = 2*2 + 1*4 = 8 a(3)=41 because the end-points of the 9 different 3-step walks are: (0,-1),(0,1)->d^2=1, (1,-2),(1,2),(2,-1),(2,-1),(2,1),(2,1)->d^2=5, (3,0)->d^2=9. a(3) = 2*1 + 6*5 + 1*9 = 41 See also "Distribution of end point distance" at first link

See under A001411

I. Jensen, Table of n, a(n) for n = 1..59 [from the Jensen link below]
A. J. Guttmann, On the critical behavior of self-avoiding walks, J. Phys. A 20 (1987), 1839-1854.
I. Jensen, Series Expansions for Self-Avoiding Walks
Hugo Pfoertner, Results for the 2D Self-Trapping Random Walk
Eric Weisstein's World of Mathematics, Self-Avoiding Walk Connective Constant

Cf. A001411, A046661, A176177.

See Hugo Pfoertner link for source code of "FORTRAN program for distance counting".

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

Name amended by Scott R. Shannon, Sep 15 2020

A272763 Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood).

Original entry on oeis.org

1, 8, 56, 368, 2336, 14576, 89928, 550504, 3349864, 20290360, 122445504, 736685008, 4421048016, 26475370088, 158257613848, 944493430152, 5628996811904

Offset: 0

Francois Alcover, May 05 2016

Moore neighborhood :
o o o
o x o
o o o
Von Neumann neighborhood (A001411):
  o
o x o
  o
Note that the path avoids already visited lattice points, but can intersect itself (two diagonal steps). A nonintersecting version is A272773.
The Moore neighborhood characterizes king tours. # Rainer Rosenthal, Jan 05 2019

Cf. A001411, A272773, A300665.

# For starting point stp and list Ldir of n directions (1..8)
# construct the points of the whole path and count them.
# If there are n+1 then the path is self-avoiding.
isSelfAvoiding := proc(Ldir) local Delta, dir, ep, path;
   Delta := [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]];
   ep := [0,0]; path := {ep};
   for dir in Ldir do
      ep := ep + Delta[dir];
      path := {op(path), ep};
   od;
   return evalb(nops(path)=nops(Ldir)+1);
end:
# Count only king tours which are self-avoiding
A272763 := proc(n) local count, T, p;
   count := 0:
   T := combinat[cartprod]([seq([$1..8], j=1..n)]):
   while not T[finished] do
      p := T[nextvalue]();
      if isSelfAvoiding(p) then count := count+1; fi;
   od:
   return count;
end: # Rainer Rosenthal, Jan 05 2019

mo=Most@Tuples[{-1,1,0},2]; 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, 7] (* Giovanni Resta, May 06 2016 *)

a(13)-a(16) from Giovanni Resta, May 06 2016

A117633 Number of self-avoiding walks of n steps on a Manhattan square lattice.

Original entry on oeis.org

1, 2, 4, 8, 14, 26, 48, 88, 154, 278, 500, 900, 1576, 2806, 4996, 8894, 15564, 27538, 48726, 86212, 150792, 265730, 468342, 825462, 1442866, 2535802, 4457332, 7835308, 13687192, 24008300, 42118956, 73895808, 129012260, 225966856, 395842772, 693470658, 1210093142, 2117089488, 3704400974

Offset: 0

R. J. Mathar, Apr 08 2006

It is proved that a(n)^(1/n) has a limit mu called the "connective constant" of the Manhattan lattice; approximate value of mu: 1.733735. It is only conjectured that a(n + 1) ~ mu * a(n). - Robert FERREOL, Dec 08 2018

			On each crossing, the first step may follow a street or an avenue. So a(1)=2.
On the next crossing, each of these 2 paths faces again two choices, giving a(2)=4. At n=4, a(4) becomes less than 16 considering the 2 cases of having moved around a block.

M. N. Barber, Asymptotic results for self-avoiding walks on a Manhattan lattice, Physica, Volume 48, Issue 2, (1970), page 240.
Robert FERREOL, The a(4)=14 walks in Manhattan lattice
Keh-Ying Lin and Yee-Mou Kao, Universal amplitude combinations for self-avoiding walks and polygons on directed lattices, J. Phys. A: Math. Gen. 32 (1999), page 6929.
A. Malakis, Self-avoiding walks on oriented square lattices, J. Phys. A: Math. Gen. 8 (1975), no 12, 1885-1898.
Wikipedia, Connective constant

Cf. A006744, A001411 (square lattice), A322419 (L-lattice).

# This program explicitly gives the a(n) walks.
walks:=proc(n)
   option remember;
   local i, father, End, X, walkN, dir, u, x, y;
   if n=1 then [[[0, 0]]] else
        father:=walks(n-1):
        walkN:=NULL:
        for i to nops(father) do
           u:=father[i]:End:=u[n-1]:x:=End[1] mod 2; y:=End[2] mod 2;
             dir:=[[(-1)**y, 0], [0, (-1)**x]]:
           for X in dir do
            if not(member(End+X, u)) then walkN:=walkN, [op(u), End+X]: fi;
            od od:
        [walkN] fi end:
walks(5); # Robert FERREOL, Dec 08 2018

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=[[1, 0], [0, 1], [-1, 0], [0, -1]]
def a(n, P=[[0, 0]]):
    if n==0: return 1
    X=P[-1]; x=X[0]%2; y=X[1]%2; mo=[[(-1)**y, 0], [0, (-1)**x]]
    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)
[a(n) for n in range(21)]
# Robert FERREOL, Dec 08 2018

a(n) = 2*A006744(n) for n >= 1. - Robert FERREOL, Dec 08 2018

Terms from a(29) on by Robert FERREOL, Dec 08 2018

A323559 Number of rooted self-avoiding knight's paths of length n on an infinite chessboard with first move specified.

Original entry on oeis.org

1, 7, 49, 337, 2323, 15805, 107737, 727619, 4921655, 33056939, 222323989, 1487064391, 9957971965, 66391431607, 443085643919, 2946553003837, 19611967535129, 130149475953673

Offset: 1

Hugo Pfoertner, Jan 17 2019

Cf. A001411, A212715, A323131, A272773, A323140, A323560.

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

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 7, 15, 37, 65, 115, 223, 503, 1127, 2761, 6225, 15393, 34915, 84399, 193489, 477727, 1113059, 2753799, 6486011, 16181965, 38447093, 95995579

Offset: 1

Scott R. Shannon, Sep 13 2020

Consider a self-avoiding walk on a 2D square lattice where each visited node is given a fixed mass and each node is connected by a rod of another fixed mass. Hang the resulting lattice structure from a string at the first node. This sequence gives the number of walks of length n such that the structure will hang perfectly vertically, and will return to this position if perturbed.
For a walk to be stable requires the torque around the first node to be zero for both the node and rod masses, and that the overall center of mass of the structure is lower than the first node. As n increases the number of walks satisfying these conditions decreases rapidly. For example the total number of 2D self-avoiding walks on a square lattice in the lower two quadrants for n=27 is A116903(27) = 227399388019. The total number of hanging stable walks for n=27 is 95995579, indicating only one in about 2370 walks is stable.
For all stable walks it is found that the final node is always directly underneath the starting node. This is not the case if only the node or rod masses are considered.
See A337761 for the equalivalent sequence on a 3D cubic lattice.

			a(1)-a(5) = 1 as the only stable walk is a walk straight down from the first node.
a(6) = 3. There is one stable walk with a first step to the right:
.
      X-----+
            |
            |
+-----+-----+
|
|
+-----+
.
where 'X' represents the hanging point first node at (0,0).
Assuming a mass of p for the nodes, q for the rods, and a length l for the rods, the total torque from the nodes to the right of the first node is 2*p*l, which equals that from the nodes to the left. The total torque for the rods to the right of the first node is 2*q*(1/2)*l + 1*q*1*l = 2ql, which equals that from the rods to the left. The center of mass is at coordinate (0,-1). This walk can be taken in 2 ways thus, with the straight down walk, the total number of stable walks is 2+1 = 3.
a(20) = 193489. An example of a 20-step stable walk is:
.
            X---+
                |
    +---+       +---+---+
    |   |               |
    +   +---+---+       +
    |           |       |
+---+           +---+---+
|
+---+---+---+
.
The total torque from the nodes to the right of the first node is 4*p*1*l + 2*p*2*l + 3*p*3*l = 17pl. The torque from the left nodes is 3*p*1*l + 4*p*2*l + 2*p*3*l = 17pl. The total torque from the rods to the right of the first node is 2*q*(l/2)*l + 2*q*1*l + 2*q*(3/2)*l + 2*q*(5/2)*l + 2*q*3*l = 17ql. The torque from the rods on the left is 2*q*(l/2)*l + 1*q*1*l + 2*q*(3/2)*l + 2*q*2*l + 2*q*(5/2)*l + 1*q*3*l = 17ql. This shows the configuration does not have to be symmetrical to be balanced.
See the linked text file for the step directions for the stable walks for n=6 to n=15.

Scott R. Shannon, Stable walks for n=6 to n=15.

Cf. A116903, A337761, A001411, A001412.

A337761 The number of hanging vertically stable self-avoiding walks of length n on a 3D cubic lattice where both the nodes and connecting rods have mass.

Original entry on oeis.org

1, 1, 1, 1, 1, 5, 13, 29, 73, 193, 581, 1717, 7029, 21981, 79625, 248697, 981353, 3275085, 13235333

Offset: 1

Scott R. Shannon, Sep 19 2020

Consider a self-avoiding walk on a 3D cubic lattice where each visited node is given a fixed mass and each node is connected by a rod of another fixed mass. Hang the resulting lattice structure from a string at the first node. This sequence gives the number of walks of length n such that the structure will hang perfectly vertically, and will return to this position if perturbed.
For a walk to be stable requires the torque around the first node to be zero along both the x and y axial directions for both the node and rod masses, and that the overall center of mass of the structure is lower than the first node. As n increases the number of walks satisfying these conditions decreases rapidly. For example the total number of 3D self-avoiding walks on a cubic lattice in the lower four quadrants for n=18 is A116904(18) = 719101961769. The total number of hanging stable walks for n=18 is 3275085, indicating only one in about 220 thousand walks is stable.
The stable walks are the same as in the 2D case, see A335780, up until n=9; the same stable single-plane walks occur but in both the x-z and y-z plane so the total of these walks is twice A335780. From n=10 stable walks can occur which use all three dimensions. For all stable walks it is found that the final node is always directly underneath the starting node. This is not the case if only the node or rod masses are considered.
See A335780 for the equalivalent sequence on a 2D square lattice.

			a(1)-a(5) = 1 as the only stable walk is a walk straight down from the first node.
a(6) = 5. There is one stable walk confined to a single plane:
.
      X-----+
            |
            |
+-----+-----+
|
|
+-----+
.
where 'X' represents the hanging point first node at (0,0,0).
Assuming a mass of p for the nodes, q for the rods, and a length l for the rods, the total torque from the nodes to the right of the first node is 2*p*l, which equals that from the nodes to the left. The total torque for the rods to the right of the first node is 2*q*(1/2)*l + 1*q*1*l = 2ql, which equals that from the rods to the left. The center of mass is at coordinate (0,0,-1). This walk can be taken in 4 ways thus, with the straight down walk, the total number of stable walks is 4+1 = 5.
a(10) = 193. Other than the straight and single plane walks those using three dimensions now occur. An example of such a walk is:
.
        +--------+      z    y
       /        /        \  /
      /   X-------+       \/
     /        /    \       +-----x
    /        /      \
   +        +        +
    \      /        /
     \    /        /
      +--/----+   /
        /        /
       +--------+
.
The total rotational torque around the y-axis from the nodes with x>0 is 3*p*l, which equals that from the nodes with x<0. The total rotational torque around the x-axis from the nodes with y>0 is 2*p*l, which equals that from the nodes with y<0. The total rotational torque around the y-axis from the rods with x>0 is 2*q*(1/2)*l + 2*q*1*l = 3ql, which equals that from the rods with x<0.  The total rotational torque around the x-axis from the rods with y>0 is 2*q*(1/2)*l + 1*q*1*l = 2ql, which equals that from the rods with x<0. The center of mass is at coordinate (0,0,-1).
a(11) = 581. An example of an 11 step stable walk where the final node is above the first node:
.
                   +              +
                  /              /|       z
                 /              / |       |  y
                /              /  |       | /
               +              /   |       |/
        +      |   X---------+    |       +-----x
       /|      |       +----------+
      / |      |      /
     /  |      |     /
    /   |      |    /
   +-----------+   /
        +---------+
.
This particular walk would be counted twice as it is also stable if hung from the final node.
See the linked text file for the step directions for the stable walks for n=6 to n=12.

Scott R. Shannon, Stable walks for n=6 to n=12.

Cf. A335780, A001412, A116904, A001411.

cp's OEIS Frontend

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

A046661 Number of n-step self-avoiding walks on the square lattice with first step specified.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A272773 Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Extensions

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

A078797 Sum of square displacements over all self-avoiding n-step walks on a square lattice with the first step specified. Numerator of mean square displacement s(n)=a(n)/A046661(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

FORTRAN

Formula

Extensions

A272763 Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Extensions

A117633 Number of self-avoiding walks of n steps on a Manhattan square lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

Extensions

A323559 Number of rooted self-avoiding knight's paths of length n on an infinite chessboard with first move specified.

Views

Author

Keywords

Crossrefs

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

Views