A317782 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, 1, 5, 51, 474, 4329, 43406, 469565, 5228459, 59259957, 686003702, 8097484169, 97005128492, 1175916181703, 14404685872773, 178105648065109, 2220134252592683, 27872257776993240, 352143374331177766, 4474477933645201621, 57147423819800882972

Offset

0,3

Links

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

Formula

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

a(n) ~ c * d^n / n^2, where d = (2 + 4/3^(3/4))^2 = 14.0982628380912972017512943055944... and c = 0.25546328221900708410379626465... - Vaclav Kotesovec, Mar 13 2019, updated Mar 17 2024

Example

a(2) = 5: [(0,1),(0,-1),(0,1),(0,1)], [(0,1),(0,1),(0,-1),(0,1)], [(0,1),(0,1),(0,1),(0,-1)], [(1,0),(-1,1),(1,0),(-1,1)], [(1,0),(1,0),(-1,1),(-1,1)].

Maple

b:= proc(n, x, y) option remember; `if`(min(args, 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..25);

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, 25] (* Jean-François Alcover, May 13 2020, after Maple *)

Crossrefs

Cf. A199915, A306813.

Sequence in context: A362516 A369295 A145641 * A342407 A195211 A106415

Adjacent sequences: A317779 A317780 A317781 * A317783 A317784 A317785

Keyword

nonn,walk

Author

Alois P. Heinz, Sep 24 2018

Status

approved