A260154 Number of square lattice walks of length 2n starting and ending at (0,0) and avoiding the West quadrant {(i,j): i < -|j|}.

1, 3, 22, 209, 2256, 26296, 322696, 4109131, 53802868, 719967204, 9804170810, 135438150718, 1893565055948, 26744778067560, 381061505993160, 5470780479977505, 79066952734823832, 1149467155656304276, 16798622641884084940, 246654934301978877376

Offset

0,2

Links

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

M. Bousquet-Mélou, Plane lattice walks avoiding a quadrant, arXiv:1511.02111 [math.CO], 2015.

Formula

a(2n) = 16^n/9 * ( 3* (1/2)_n^2/ (2)_n^2 + 8 *(1/2)_n* (7/6)_n/ (2)_n/ (4/3)_n - 2 *(1/2)_n*(5/6)_n/ (2)_n/ (5/3)_n), where (a)_n is the ascending factorial (proved).

D-finite with recurrence n*(n-1)*(3*n+2)*(4*n-5)*(3*n+1)*(4*n-7)*(n+1)^2*a(n) -4*n*(n-1)*(4*n-1)*(2*n-1)*(4*n-7)*(54*n^3-45*n^2-49*n-10)*a(n-1) +16*(n-1)*(4*n-5)*(2*n-1)*(2*n-3)*(4*n+1)*(108*n^3-396*n^2+361*n+5)*a(n-2) -64*(6*n-11)*(4*n-1)*(6*n-13)*(2*n-1)*(2*n-3)*(4*n+1)*(-5+2*n)^2*a(n-3)=0. Alois P. Heinz, Nov 10 2015

D-finite with recurrence n*(n-1)*(3*n+2)*(3*n+1)*(n+1)^2*a(n) -4*n*(n-1)*(180*n^4-360*n^3+287*n^2-71*n+2)*a(n-1) +16*(n-1)*(1440*n^5-10080*n^4+29024*n^3-42768*n^2+31867*n-9465)*a(n-2) -64*(2*n-5)*(2880*n^5-30240*n^4+128608*n^3-277008*n^2+301706*n-132501)*a(n-3) +2048*(2*n-5)*(2*n-7)*(360*n^4-4320*n^3+19474*n^2-39156*n+29691)*a(n-4) -16384*(6*n-23)*(6*n-25)*(2*n-5)*(2*n-7)*(2*n-9)^2*a(n-5)=0. - R. J. Mathar, Apr 11 2022

Example

When n=1, only the walks NS, EW, SN contribute.

Maple

a:= proc(n) option remember; `if`(n<3, [1, 3, 22][n+1],
     (4*n*(n-1)*(4*n-1)*(54*n^3-45*n^2-49*n-10)*(2*n-1)*
      (4*n-7)*a(n-1) -(16*(n-1))*(4*n-5)*(2*n-1)*(2*n-3)*
      (4*n+1)*(108*n^3-396*n^2+361*n+5)*a(n-2) +(64*(6*n-11))*
      (4*n-1)*(6*n-13)*(2*n-1)*(2*n-3)*(4*n+1)*(-5+2*n)^2*a(n-3))
      /((3*n+2)*(4*n-5)*(3*n+1)*(4*n-7)*n*(n-1)*(n+1)^2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 10 2015

Mathematica

a[n_] := a[n] = If[n<3, {1, 3, 22}[[n+1]], (4(54n^3 - 45n^2 - 49n - 10)(4n - 7)(n-1)(2n - 1)(4n - 1) n a[n-1] - (16(n-1)(4n - 5)(2n - 1)(2n - 3)(4n + 1)(108n^3 - 396n^2 + 361n + 5) a[n-2]) + (6n - 13)(64(6n - 11))(2n - 3) (2n - 1)(4n - 1)(4n + 1)(2n - 5)^2 a[n-3])/((3n + 2)(4n - 5)(3n + 1)(4n - 7) n(n-1)(n+1)^2)]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 04 2016 after Alois P. Heinz *)

Crossrefs

Cf. A260153.

Sequence in context: A006783 A330668 A001409 * A340474 A079489 A190526

Adjacent sequences: A260151 A260152 A260153 * A260155 A260156 A260157

Keyword

nonn,easy,walk

Author

Mireille Bousquet-Mélou, Nov 09 2015

Status

approved