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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A191652 Number of n-step two-sided prudent self-avoiding walks ending on the top side of their box. 3
1, 3, 7, 18, 45, 113, 283, 709, 1775, 4442, 11111, 27781, 69433, 173468, 433229, 1081609, 2699521, 6735586, 16801355, 41898736, 104460505, 260378007, 648878481, 1616720044, 4027390409, 10030782405, 24978849433, 62192878443, 154825778335 (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..1000

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

FORMULA

a(n) = (A191605(n) + A191625(n)) / 2.

EXAMPLE

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

MAPLE

b:= proc(d, i, n, x, y) option remember;

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

         `if`(d<>3, b(1, x=0, n-1, max(x-1, 0), y), 0) +

         `if`(d<>4, b(2, y=0, n-1, x, max(y-1, 0)), 0) +

         `if`(d in [0, 3] or d=2 and i, b(3, false, n-1, x+1, y), 0) +

         `if`(d in [0, 4] or d=1 and i, b(4, false, n-1, x, y+1), 0))

    end:

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

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

MATHEMATICA

b[d_, i_, n_, x_, y_] := b[d, i, n, x, y] = If [n == 0, If [y == 0, 1, 0], If[d != 3, b[1, x == 0, n - 1, Max[x - 1, 0], y], 0] + If[d != 4, b[2, y == 0, n - 1, x, Max[y - 1, 0]], 0] + If[d == 0 || d == 3 || d == 2 && i, b[3, False, n - 1, x + 1, y], 0] + If[d == 0 || d == 4 || d == 1 && i, b[4, False, n - 1, x, y + 1], 0]];

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

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

CROSSREFS

Cf. A191605, A191625.

Sequence in context: A291229 A036883 A247296 * A191826 A114713 A078058

Adjacent sequences:  A191649 A191650 A191651 * A191653 A191654 A191655

KEYWORD

nonn,walk

AUTHOR

Alois P. Heinz, Jun 10 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 18:54 EST 2018. Contains 299586 sequences. (Running on oeis4.)