cp's OEIS Frontend

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

%I A192871 #28 Feb 23 2022 11:23:48
%S A192871 1,3,6,12,24,48,90,168,318,594,1092,2004,3678,6720,12210,22128,40074,
%T A192871 72372,130380,234432,421128,755208,1352328,2418246,4320552,7709898,
%U A192871 13744764,24477618,43560444,77448330,137602440,244277016,433399824,768379830,1361530134
%N A192871 Number of n-step prudent self-avoiding walks on honeycomb lattice.
%C A192871 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.
%H A192871 Alois P. Heinz, <a href="/A192871/b192871.txt">Table of n, a(n) for n = 0..110</a>
%H A192871 Mireille Bousquet-Mélou, <a href="https://dmtcs.episciences.org/3627">Families of prudent self-avoiding walks</a>, DMTCS proc. AJ, 2008, 167-180.
%H A192871 Mireille Bousquet-Mélou, <a href="https://arxiv.org/abs/0804.4843">Families of prudent self-avoiding walks</a>, arXiv:0804.4843 [math.CO], 2008-2009.
%H A192871 Enrica Duchi, <a href="https://hal.archives-ouvertes.fr/hal-00159320">On some classes of prudent walks</a>, in: FPSAC'05, Taormina, Italy, 2005.
%e A192871 This 8-step prudent self-avoiding walk on honeycomb lattice from (S) to (E) is not reversible:
%e A192871 .           o...o       o...o
%e A192871 .          .     .     .     .
%e A192871 .     o...o       4---3       o
%e A192871 .    .     .     /     \     .
%e A192871 .   o       6---5       2...o
%e A192871 .    .     /     .     /     .
%e A192871 .     o...7      (S)--1       o
%e A192871 .    .     \     .     .     .
%e A192871 .   o      (E)..o       o...o
%e A192871 .    .     .     .     .
%e A192871 .     o...o       o...0
%p A192871 i:= n-> max(n, 0)+1: d:= n-> max(n-1, -1):
%p A192871 b:= proc(n, x, y, z, u, v, w) option remember;
%p A192871     `if`(n=0, 1, `if`(x>y, b(n, y, x, w, v, u, z),
%p A192871     `if`(min(y, z)<=0 or x=-1,
%p A192871         b(n-1, d(y), d(z), u, i(v), i(w), x), 0)+
%p A192871     `if`(min(w, x)<=0 or y=-1,
%p A192871         b(n-1, d(w), d(x), y, i(z), i(u), v), 0)))
%p A192871     end:
%p A192871 a:= n-> `if`(n<2, 1 +2*n, 6*b(n-2, -1, -1, 1, 2, 1, -1)):
%p A192871 seq(a(n), n=0..20);
%t A192871 i[n_] := Max[n, 0] + 1; d[n_] := Max[n - 1, -1];
%t A192871 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]]];
%t A192871 a[n_] := If[n < 2, 1 + 2 n, 6 b[n - 2, -1, -1, 1, 2, 1, -1]];
%t A192871 a /@ Range[0, 34] (* _Jean-François Alcover_, Sep 22 2019, after _Alois P. Heinz_ *)
%Y A192871 Cf. A001668, A006851, A192208.
%K A192871 nonn,walk
%O A192871 0,2
%A A192871 _Alois P. Heinz_, Jul 11 2011