A001334 -id:A001334 - cp's OEIS frontend

A192208 Number of n-step prudent self-avoiding walks on hexagonal [= triangular] lattice.

1, 6, 30, 138, 606, 2610, 11070, 46386, 192606, 793938, 3253038, 13261746, 53832462, 217707762, 877594086, 3527521794, 14142930774, 56574143754, 225841103190, 899866007610, 3579435531846, 14215941861138, 56378805654510, 223297285830858, 883326046736814

Offset: 0

Alois P. Heinz, Jul 05 2011

The hexagonal lattice is the familiar 2-dimensional lattice in which each point has 6 neighbors. This is sometimes called the triangular lattice.

A prudent walk never takes a step pointing towards a vertex it has already visited. Prudent walks are self-avoiding but not reversible in general.

			Two 5-step self-avoiding walks on hexagonal lattice from (S) to (E), the walk at left is prudent while the walk at right is not prudent:
.     o---o...o...o...o---o
.    . \ . \ . . . . . \ . \
.   o..(S)..o...o...o..(E)..o
.    . . . / . . . . . . . /
.    (E)--o...o...o..(S)--o

Alois P. Heinz, Table of n, a(n) for n = 0..61
Mireille Bousquet-Mélou, Families of prudent self-avoiding walks, arXiv:0804.4843. J. Combin. Theory Ser. A 117 no. 3 (2010) 313-344.
Enrica Duchi, On some classes of prudent walks, in: FPSAC'05, Taormina, Italy, 2005.
Wikipedia, Self-avoiding walk

Cf. A001334, A192871.

i:= n-> max(n, 0)+1: d:= n-> max(n-1, -1):
b:= proc(n, x, y, z, u, v, w) option remember;
    `if`(n=0, 1, `if`(x>y, b(n, y, x, w, v, u, z),
        b(n-1, d(x), d(y), z, i(u), i(v), w)+
    `if`(min(y, z)<=0 or x=-1,
        b(n-1, d(y), d(z), u, i(v), i(w), x), 0)+
    `if`(min(z, u)<=0 or y=-1,
        b(n-1, d(z), d(u), v, i(w), i(x), y), 0)+
    `if`(min(v, w)<=0 or x=-1,
        b(n-1, d(v), d(w), x, i(y), i(z), u), 0)+
    `if`(min(w, x)<=0 or y=-1,
        b(n-1, d(w), d(x), y, i(z), i(u), v), 0)))
    end:
a:= n-> `if`(n=0, 1, 6*b(n-1, -1$2, 0, 1$2, 0)):
seq(a(n), n=0..20);

i[n_]:= Max[n, 0]+1; d[n_]:= Max[n-1, -1];
b[n_, x_, y_, z_, u_, v_, w_] := b[n, x, y, z, u, v, w] = If[n==0, 1, If[x>y, b[n, y, x, w, v, u, z], b[n-1, d[x], d[y], z, i[u], i[v], w]+ If[Min[y, z]<=0 || x==-1, b[n-1, d[y], d[z], u, i[v], i[w], x], 0]+ If[Min[z, u]<=0 || y==-1, b[n-1, d[z], d[u], v, i[w], i[x], y], 0]+ If[Min[v, w]<=0 || x==-1, b[n-1, d[v], d[w], x, i[y], i[z], u], 0]+ If[Min[w, x]<=0 || y==-1, b[n-1, d[w], d[x], y, i[z], i[u], v], 0]]];
a[n_]:= If[n==0, 1, 6*b[n-1, -1,-1, 0, 1,1, 0]];
Table[a[n],{n,0,20}] (* Jean-François Alcover, Aug 10 2017, translated from Maple *)

A006816 Related to self-avoiding walks on square lattice.

Original entry on oeis.org

1, 6, 29, 108, 393, 1298, 4271, 13312, 41469, 125042, 376747, 1111144, 3274475, 9505054, 27573041, 79086964, 226727667, 644301026, 1830188555, 5162408200, 14556754485, 40811281170

Offset: 1

N. J. A. Sloane

After constructing a self-avoiding walk, bridge together all adjacent neighboring sites on the walk. This sequence is sum of the total number of links after adding bridges across all walks of length n. - Sean A. Irvine, Aug 09 2017

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

A. J. Guttmann and J. Wang, The extension of self-avoiding random walk series in 2 dimensions, Preprint. (Annotated scanned copy)
B. D. Hughes, Random Walks and Random Environments, vol. 1, Oxford 1995, Tables and references for self-avoiding walks counts [Annotated scanned copy of several pages of a preprint or a draft of chapter 7 "The self-avoiding walk"]
S. S. Manna, A. J. Guttmann and A. K. Roy, Diffusion on self-avoiding walk networks, J. Phys. A 22 (1989), 3621-3627.

Cf. A001411, A006814, A006815.

a(19)-a(22) from Sean A. Irvine, Aug 09 2017

A224876 On an hexagonal lattice, repeatedly: mark the current point and then move forward to the nearest unmarked point and then rotate 120 degrees clockwise. a(n) gives the number of steps between the n-th and (n+1)-th marks.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 3, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 6, 1, 3, 1, 3, 4, 3, 4, 3, 5, 1, 3, 1, 6, 3, 6, 3, 7, 1, 6, 1, 8, 1, 6, 1, 7, 3, 8, 3, 8, 1, 8, 1, 9, 1, 9, 1, 10, 1, 2, 1, 3, 10, 3, 10, 3, 1, 2, 1, 12, 1, 3, 1, 5, 1, 2, 1, 12, 1, 3, 1, 5, 9, 4, 11, 1, 2, 1

Offset: 1

Paul Tek, Jul 23 2013

Apparently, every lattice point will be marked.

			This diagram depicts the first 9 marks:
  \ / \ / \ /
--4---5---.--
  / \ / \ / \
-7---1---2---8-
  \ / \ / \ / \
--6---3---9--
  / \ / \ / \
a(1) = number of steps between 1st and 2nd marks = 1;
a(2) = number of steps between 2nd and 3rd marks = 1;
a(3) = number of steps between 3rd and 4th marks = 2;
a(4) = number of steps between 4th and 5th marks = 1;
a(5) = number of steps between 5th and 6th marks = 2;
a(6) = number of steps between 6th and 7th marks = 1;
a(7) = number of steps between 7th and 8th marks = 3;
a(8) = number of steps between 8th and 9th marks = 1.

Cf. A001334, A125852.

Perl
```
See Links section.
```

A249565 Number of self-avoiding walks on the truncated square tiling with n steps.

Original entry on oeis.org

1, 3, 6, 12, 22, 42, 80, 152, 284, 536, 988, 1848, 3412, 6352, 11724, 21718, 39952, 73808, 135668, 250188, 459172, 844888, 1548608, 2845186, 5211548, 9563768, 17501272, 32079524, 58660712, 107425356, 196320596, 359232144, 656099656, 1199676412, 2189995764

Offset: 0

Mike Zabrocki, Nov 01 2014

A self-avoiding walk is a sequence of adjacent points in a lattice that are all distinct. The truncated square tiling is a semiregular tiling by regular polygons of the Euclidean plane with one square and two octagons on each vertex. The edge lattice is also referred to as (4,8^2) lattice. It is also the Cayley graph of the Coxeter group generated by three generators {s_0, s_1, s_2} with the relations s_i^2 = 1, s_0 s_2 = s_2 s_0, (s_i s_{i+1})^4 = 1 for i=0,1.

It is conjectured that a(n) is approximately mu^n*n^{11/32} for large n where mu is the connective constant and mu is approximately 1.80883001(6).

			There are 6 paths of length 2 in the truncated square lattice corresponding to the reduced words in the Coxeter group s_0 s_2, s_0 s_1, s_1 s_2, s_1 s_0, s_2 s_0, s_2 s_1.

Andrey Zabolotskiy, Table of n, a(n) for n = 0..47 (from Alm, 2005)
Sven Erick Alm, Upper and lower bounds for the connective constants of self-avoiding walks on the Archimedean and Laves lattices, J. Phys. A.: Math. Gen., 38 (2005), 2055-2080. Also technical report of the same name, 2004. See Table 2, column (4.8^2).
I. Jensen, and A. J. Guttmann, Self-avoiding walks, neighbour-avoiding walks and trails on semi-regular lattices, J. Phys. A., 31, (1998), 8137-45.
Keh Ying Lin and Chi Chen Chang, Self-avoiding walks on the 4-8 lattice, International Journal of Modern Physics B, 16 (2002), 1241-1246.
Wikipedia, Truncated square tiling
Wikipedia, Connective constant
M. Zabrocki, SAWs and SAPs on the Cayley graph of a group, notes 2014.

Cf. A001411, A001334.

a(20)-a(21) from Mike Zabrocki, Nov 08 2014

a(19)-a(21) corrected based on Alm (2005) and Lin & Chang (2002), more terms added by Andrey Zabolotskiy, Oct 18 2024

A007274 Walks on hexagonal lattice using each point at most twice.

Original entry on oeis.org

1, 6, 36, 216, 1260, 7206, 40650, 227256, 1262832, 6983730, 38470224, 211220814, 1156489782, 6317095284, 34435495872, 187380150468, 1018035642054

Offset: 0

Simon Plouffe

The hexagonal lattice is the familiar 2-dimensional lattice in which each point has 6 neighbors. This is sometimes called the triangular lattice.

Guttmann et al. has incorrect a(10) = 38470220, a(11) = 211220800, a(12) = 1156490000. - Sean A. Irvine, Dec 02 2017

A. J. Guttmann, C. Byrnes and N. E. Frankel, A generalized self-avoiding walk, J. Phys. A 17 (1984), L457-L461.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. Nebe and N. J. A. Sloane, Home page for hexagonal (or triangular) lattice A2

Cf. A001334, A007275.

Title improved, a(10)-a(12) corrected, and a(15)-a(16) added by Sean A. Irvine, Dec 02 2017

A007275 Walks on hexagonal lattice using each point at most three times.

Original entry on oeis.org

1, 6, 36, 216, 1296, 7776, 46440, 276054, 1633848, 9633366, 56616132, 331847118, 1940715960, 11327957196, 66010769382, 384094025382, 2231978658906

Offset: 0

Simon Plouffe

The hexagonal lattice is the familiar 2-dimensional lattice in which each point has 6 neighbors. This is sometimes called the triangular lattice.

Guttmann et al. has incorrect a(10) = 56616140, a(11) = 331847200, and a(12) = 1940717000. - Sean A. Irvine, Dec 03 2017

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

A. J. Guttmann, C. Byrnes and N. E. Frankel, A generalized self-avoiding walk, J. Phys. A 17 (1984), L457-L461.
G. Nebe and N. J. A. Sloane, Home page for hexagonal (or triangular) lattice A2

Cf. A001334, A007274.

Title improved, a(10)-a(12) corrected, and a(15)-a(16) added by Sean A. Irvine, Dec 03 2017

A121791 Series expansion for end-to-end distance of self-avoiding walks on the triangular lattice.

Original entry on oeis.org

1, 12, 97, 654, 3977, 22624, 122821, 644082, 3288739, 16440648, 80783857, 391310240, 1872763387, 8870963422, 41647686501, 194014270964, 897639074623, 4127904278590, 18879838654237, 85930246593928

Offset: 1

N. J. A. Sloane, Aug 30 2006

nonn

I. Jensen, Table of n, a(n) for n = 1..40 [from the Jensen link below]
I. Jensen, Series Expansions for Self-Avoiding Walks

Cf. A001334 corresponding number of self-avoiding walks, A078797 series expansion for end-to-end distances of self-avoiding walks on the square lattice.

Name corrected by Hugo Pfoertner, Aug 11 2014

A261834 Number of n-step adjacent expansions on the hexagonal (honeycomb) lattice. Holes allowed.

Original entry on oeis.org

1, 6, 48, 468, 5328, 68928, 994464, 15781920, 272594160, 5081825664

Offset: 0

Francois Alcover, Mar 24 2016

Initially only one cell C[0] is occupied on the lattice.
Then, for each i of (1..n), C[i] is chosen among the free cells adjacent to at least one of (C[0],...,C[i-1]).
a(n) is the number of distinct (C[1],...,C[n]).

			a(1) = 6 because a point has 6 neighbors on the hexagonal grid.
a(2) = 48 = a(1) * 8 because a two-cell group has 8 free neighbors.

Francois Alcover, tree.

Cf. A007846 (same principle but on the rectangular lattice).

Cf. A001334.

More terms from Francois Alcover, Apr 29 2016
Rephrasing and culling comments from Francois Alcover, Apr 29 2016
Added crossref to A007846 from Francois Alcover, May 01 2016

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

A177238 Number of n-step self-avoiding walks on square lattice plus number of n-step self-avoiding walks on hexagonal [ =triangular ] lattice.

Original entry on oeis.org

2, 10, 42, 174, 718, 3014, 12726, 54054, 230046, 980402, 4177266, 17789230, 75680138, 321616186, 1365165694, 5788182178, 24514575654, 103720434558, 438421398326, 1851566492994, 7813337317842, 32946701361962, 138832416613530

Offset: 0

Jonathan Vos Post, Dec 11 2010

a(0) = 2 is the only prime in the sequence. (By symmetry in both lattices, we are adding two sequences with even terms if n>0.) a(n) is semiprime for a(1) = 10 = 2 * 5, a(4) = 718 = 2 * 359, a(9) = 980402 = 2 * 490201. The Jensen table linked from A001334 should allow extension through a(40).

			n\Triangle | Square | Sum
0          1     1     2
1          6     4     10
2          30    12    42
3          138   36    174
4          618   100   718
5          2730  284   3014
6          11946 780   12726

Cf. A001334, A001411.

a(n) = A001334(n) + A001411(n).

cp's OEIS Frontend

A192208 Number of n-step prudent self-avoiding walks on hexagonal [= triangular] lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A006816 Related to self-avoiding walks on square lattice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A224876 On an hexagonal lattice, repeatedly: mark the current point and then move forward to the nearest unmarked point and then rotate 120 degrees clockwise. a(n) gives the number of steps between the n-th and (n+1)-th marks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Perl

A249565 Number of self-avoiding walks on the truncated square tiling with n steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A007274 Walks on hexagonal lattice using each point at most twice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A007275 Walks on hexagonal lattice using each point at most three times.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A121791 Series expansion for end-to-end distance of self-avoiding walks on the triangular lattice.

Views

Author

Keywords

Links

Crossrefs

Extensions

A261834 Number of n-step adjacent expansions on the hexagonal (honeycomb) lattice. Holes allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Crossrefs