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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A190586 Number of two-sided n-step prudent walks ending on the top side of their box, avoiding two or more consecutive west steps and south steps. 2
1, 3, 6, 15, 35, 83, 195, 460, 1085, 2560, 6039, 14247, 33613, 79306, 187114, 441477, 1041626, 2457630, 5798569, 13681202, 32279488, 76160166, 179691649, 423961718, 1000285928, 2360046161, 5568211498, 13137414580, 30995819288, 73129978187, 172538870438 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

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

Shanzhen Gao, Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.

FORMULA

Recurrence: (n+1)*(7*n^2 - 194*n + 926)*a(n) = n*(42*n^2 - 1143*n + 5320)*a(n-1) - (84*n^3 - 2349*n^2 + 13043*n - 13734)*a(n-2) + (77*n^3 - 2267*n^2 + 15130*n - 27824)*a(n-3) - (63*n^3 - 1893*n^2 + 13180*n - 24672)*a(n-4) - (7*n^3 - 313*n^2 + 3298*n - 8548)*a(n-5) + (77*n^3 - 2309*n^2 + 16800*n - 34964)*a(n-6) + 2*(14*n^3 - 563*n^2 + 6962*n - 24347)*a(n-7) + (49*n^3 - 1456*n^2 + 10086*n - 21316)*a(n-8) - (7*n^3 - 208*n^2 + 1687*n - 2950)*a(n-9) - 6*(7*n^3 - 236*n^2 + 2187*n - 5968)*a(n-10) - 2*(7*n^3 - 250*n^2 + 2526*n - 7744)*a(n-11) + 2*(n-10)*(7*n^2 - 180*n + 739)*a(n-12). - Vaclav Kotesovec, Sep 03 2014

G.f.: 1/(2*t*(1-2*t-t^2+t^3)*(1-2*t-2*t^3))*((1-2*t)*(1-t)*sqrt((1-t-t^3)^2-4*t^4)-(1+t)*(1-7*t+14*t^2-11*t^3+10*t^4-4*t^5)), see sequence 11 in link. - Michel Marcus, May 06 2015

EXAMPLE

a(2) = 6 since there are 6 such walks: WN, NW, EN, NE, EE, NN.

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=0 or d=2 and i, b(3, false, n-1, x+1, y), 0) +

         `if`(d=0 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);  # Alois P. Heinz, Jun 09 2011

MATHEMATICA

CoefficientList[Series[1/(2 x (1-2 x - x^2 + x^3) (1 - 2 x - 2 x^3)) ((1 - 2 x) (1 - x) Sqrt[(1 - x - x^3)^2 - 4 x^4] - (1 + x) (1 - 7 x + 14 x^2 - 11 x^3 + 10 x^4 - 4 x^5)), {x, 0, 50}], x] (* Vincenzo Librandi, May 07 2015 *)

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 == 2 && i, b[3, False, n-1, x+1, y], 0] + If[d == 0 || 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, Oct 24 2016, after Alois P. Heinz *)

CROSSREFS

Sequence in context: A027600 A024416 A076375 * A113225 A298539 A209450

Adjacent sequences:  A190583 A190584 A190585 * A190587 A190588 A190589

KEYWORD

nonn,walk

AUTHOR

Shanzhen Gao, May 13 2011

EXTENSIONS

More terms from Alois P. Heinz, Jun 09 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 17:09 EST 2019. Contains 329337 sequences. (Running on oeis4.)