A364439 a(n) is the number of paths with length 3*n that begin at (0,0), end at (0,0), and do not reach (0,0) at any point in between while 0 <= y <= x at every step, where a path is a sequence of steps in the form (1,1), (1,-1), and (-2,0).

1, 1, 4, 33, 367, 4844, 71597, 1147653, 19559062, 349766457, 6502419671, 124822220086, 2461515013103, 49668479230825, 1022258042480874, 21406231023989503, 455112508356168561, 9807294681518154334, 213897254891041613995, 4715809234441541498539

Offset

0,3

Comments

If the constraint is removed that the sequence does not reach (0,0) at any point other than the beginning and end of the sequence, this sequence becomes A005789.

Links

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

Marshall Hamon, A364439.c

Formula

From Alois P. Heinz, Jul 29 2023: (Start)

INVERTi transform of A005789.

a(n) mod 2 = A011655(n+1). (End)

Example

Let A represent the (1,1) step, B represent the (1,-1) step, and C represent the (-2,0) step.
For n = 1, the only valid path is ABC.
For n = 2, the 4 valid paths are AABBCC, AABCBC, ABABCC, ABACBC.

Maple

b:= proc(n, l) option remember; `if`(n<1, 1, add((h->
      `if`(h[2]>h[1] or h[1]>=n or min(h)<0 or n>1 and h=[0$2],
           0, b(n-1, h)))(l-w), w=[[1, 1], [1, -1], [-2, 0]]))
    end:
a:= n-> b(3*n-1, [2, 0]):
seq(a(n), n=0..25);  # Alois P. Heinz, Jul 28 2023
# second Maple program:
f:= proc(n) option remember; (3*n)!*mul(i!/(n+i)!, i=0..2) end:	
a:= proc(n) option remember; `if`(n=0, 1,
      f(n)-add(f(n-i)*a(i), i=1..n-1))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jul 29 2023

Mathematica

f[n_] := f[n] = (3n)!*Product[i!/(n+i)!, {i, 0, 2}];
a[n_] := a[n] = If[n == 0, 1, f[n] - Sum[f[n-i]*a[i], {i, 1, n-1}]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 27 2023, after Alois P. Heinz *)

Prog

(C) /* See Hamon Link */

Crossrefs

Cf. A005789, A011655.

Sequence in context: A362604 A075132 A303919 * A208961 A113170 A187738

Adjacent sequences: A364436 A364437 A364438 * A364440 A364441 A364442

Keyword

nonn,walk

Author

Marshall Hamon, Jul 24 2023

Extensions

More terms from Alois P. Heinz, Jul 27 2023

Status

approved