A192871 Number of n-step prudent self-avoiding walks on honeycomb lattice.

1, 3, 6, 12, 24, 48, 90, 168, 318, 594, 1092, 2004, 3678, 6720, 12210, 22128, 40074, 72372, 130380, 234432, 421128, 755208, 1352328, 2418246, 4320552, 7709898, 13744764, 24477618, 43560444, 77448330, 137602440, 244277016, 433399824, 768379830, 1361530134

Offset

0,2

Comments

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.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..110

Mireille Bousquet-Mélou, Families of prudent self-avoiding walks, DMTCS proc. AJ, 2008, 167-180.

Mireille Bousquet-Mélou, Families of prudent self-avoiding walks, arXiv:0804.4843 [math.CO], 2008-2009.

Enrica Duchi, On some classes of prudent walks, in: FPSAC'05, Taormina, Italy, 2005.

Example

This 8-step prudent self-avoiding walk on honeycomb lattice from (S) to (E) is not reversible:
.           o...o       o...o
.          .     .     .     .
.     o...o       4---3       o
.    .     .     /     \     .
.   o       6---5       2...o
.    .     /     .     /     .
.     o...7      (S)--1       o
.    .     \     .     .     .
.   o      (E)..o       o...o
.    .     .     .     .
.     o...o       o...0

Maple

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),
    `if`(min(y, z)<=0 or x=-1,
        b(n-1, d(y), d(z), u, i(v), i(w), x), 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<2, 1 +2*n, 6*b(n-2, -1, -1, 1, 2, 1, -1)):
seq(a(n), n=0..20);

Mathematica

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], If[Min[y, z] <= 0 || x == -1, b[n - 1, d[y], d[z], u, i[v], i[w], x], 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 < 2, 1 + 2 n, 6 b[n - 2, -1, -1, 1, 2, 1, -1]];
a /@ Range[0, 34] (* Jean-François Alcover, Sep 22 2019, after Alois P. Heinz *)

Crossrefs

Cf. A001668, A006851, A192208.

Sequence in context: A366277 A322676 A102255 * A002910 A001668 A080616

Adjacent sequences: A192868 A192869 A192870 * A192872 A192873 A192874

Keyword

nonn,walk

Author

Alois P. Heinz, Jul 11 2011

Status

approved