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

Author

Alois P. Heinz, Jul 11 2011

Keywords

• nonn
• walk

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.

Examples

			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
		

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.

Crossrefs

Cf. A001668, A006851, A192208.

Programs

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