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.

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

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