login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A192871 Number of n-step prudent self-avoiding walks on honeycomb lattice. 2
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 (list; graph; refs; listen; history; text; internal format)
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.

REFERENCES

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

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

LINKS

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

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: A115807 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 02:56 EDT 2021. Contains 345415 sequences. (Running on oeis4.)