A306813 Number of 2n-step paths from (0,0) to (0,n) that stay in the first quadrant (but may touch the axes) consisting of steps (-1,0), (0,1), (0,-1) and (1,-1).

1, 0, 3, 10, 20, 237, 770, 3944, 28635, 112360, 744084, 4381083, 21579779, 143815322, 801165187, 4578481584, 29176623983, 165772480380, 1013147794546, 6259309820475, 36974951346176, 230752749518819, 1413352914731005, 8618746801792237, 53986291171211635

Offset: 0

Author

Alois P. Heinz, Mar 11 2019

Keywords

• nonn
• walk

Examples

			a(0) = 1: [(0,0)].
a(2) = 3:
  [(0,0), (0,1), (0,0), (0,1), (0,2)],
  [(0,0), (0,1), (0,2), (0,1), (0,2)],
  [(0,0), (0,1), (0,2), (0,3), (0,2)].
a(3) = 10:
  [(0,0), (0,1), (1,0), (1,1), (1,2), (1,3), (0,3)],
  [(0,0), (0,1), (0,2), (1,1), (1,2), (1,3), (0,3)],
  [(0,0), (0,1), (0,2), (0,3), (1,2), (1,3), (0,3)],
  [(0,0), (0,1), (0,2), (0,3), (0,4), (1,3), (0,3)],
  [(0,0), (0,1), (1,0), (1,1), (1,2), (0,2), (0,3)],
  [(0,0), (0,1), (0,2), (1,1), (1,2), (0,2), (0,3)],
  [(0,0), (0,1), (0,2), (0,3), (1,2), (0,2), (0,3)],
  [(0,0), (0,1), (1,0), (1,1), (0,1), (0,2), (0,3)],
  [(0,0), (0,1), (0,2), (1,1), (0,1), (0,2), (0,3)],
  [(0,0), (0,1), (1,0), (0,0), (0,1), (0,2), (0,3)].
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..1116 (terms 0..500 from Alois P. Heinz)

Crossrefs

Cf. A000108, A126596, A174687, A306814, A317782.

Programs

Maple

b:= proc(n, x, y) option remember; `if`(min(n, x, y, n-x-y)<0, 0,
      `if`(n=0, 1, add(b(n-1, x-d[1], y-d[2]),
       d=[[-1, 0], [0, 1], [0, -1], [1, -1]])))
    end:
a:= n-> b(2*n, 0, n):
seq(a(n), n=0..30);

Mathematica

b[n_, x_, y_] := b[n, x, y] = If[Min[n, x, y, n - x - y] < 0, 0, If[n == 0, 1, Sum[b[n - 1, x - d[[1]], y - d[[2]]], {d, {{-1, 0}, {0, 1}, {0, -1}, {1, -1}}}]]];
a[n_] := b[2n, 0, n];
a /@ Range[0, 30] (* Jean-François Alcover, May 13 2020, after Maple *)

Formula

a(n) = A306814(2n,n).

a(n) ~ c * d^n / n^2, where d = 6.7004802541941947450873... and c = 0.5171899701803656646... - Vaclav Kotesovec, Apr 13 2019