login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A191757 Number of n-step four-sided prudent self-avoiding walks ending on the top side of their box. 3
1, 3, 7, 19, 49, 129, 333, 865, 2233, 5763, 14825, 38087, 97641, 249961, 638861, 1630681, 4156737, 10583483, 26916167, 68383509, 173565889, 440133159, 1115145081, 2823128197, 7141682287, 18053470305, 45606579731, 115137581735, 290498368253 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

REFERENCES

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..100

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

EXAMPLE

a(3) = 19: EEE, EEN, ENE, ENN, ENW, NEE, NEN, NNE, NNN, NNW, NWN, NWW, WNE, WNN, WNW, WWN, WWW, SEN, SWN.

MAPLE

b:= proc(d, i, n, x, y, w, s)

      if w<x then b([3, 2, 1, 4][d], i, n, w, y, x, s)

    else b(d, i, n, x, y, w, s):=

         `if`(y>n, 0, `if`(n=0, `if`(y=0, 1, 0),

         `if`(d in [0, 1] or d<>3 and (x=0 or i),

              b(1, evalb(x=0), n-1, max(x-1, 0), y, w+1, s), 0) +

         `if`(d in [0, 2] or d<>4 and (y=0 or i),

              b(2, evalb(y=0), n-1, x, max(y-1, 0), w, s+1), 0) +

         `if`(d in [0, 3] or d<>1 and (w=0 or i),

              b(3, evalb(w=0), n-1, x+1, y, max(w-1, 0), s), 0) +

         `if`(d in [0, 4] or d<>2 and (s=0 or i),

              b(4, evalb(s=0), n-1, x, y+1, w, max(s-1, 0)), 0)))

      fi

    end:

a:= n-> b(0, false, n, 0, 0, 0, 0):

seq(a(n), n=0..30);

MATHEMATICA

b[d_, i_, n_, x_, y_, w_, s_] := b[d, i, n, x, y, w, s] = If[w < x,  b[{3, 2, 1, 4}[[d]], i, n, w, y, x, s], b[d, i, n, x, y, w, s] = If[y > n, 0, If[n == 0, If[y == 0, 1, 0], If[MemberQ[{0, 1}, d] || d != 3 && (x == 0 || i), b[1, x == 0, n - 1, Max[x - 1, 0], y, w + 1, s], 0] + If[MemberQ[{0, 2}, d] || d != 4 && (y == 0 || i), b[2, y == 0, n - 1, x, Max[y - 1, 0], w, s + 1], 0] + If[MemberQ[{0, 3}, d] || d != 1 && (w == 0 || i), b[3, w == 0, n - 1, x + 1, y, Max[w - 1, 0], s], 0] + If[MemberQ[{0, 4}, d] || d != 2 && (s == 0 || i), b[4, s == 0, n - 1, x, y + 1, w, Max[s - 1, 0]], 0]]]];

a[n_] :=  b[0, False, n, 0, 0, 0, 0];

Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 23 2017, translated from Maple *)

CROSSREFS

Cf. A191756, A191758.

Sequence in context: A073063 A007288 A191824 * A061646 A017926 A017927

Adjacent sequences:  A191754 A191755 A191756 * A191758 A191759 A191760

KEYWORD

nonn,walk

AUTHOR

Alois P. Heinz, Jun 15 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 November 20 02:34 EST 2019. Contains 329323 sequences. (Running on oeis4.)