A364439 - OEIS

%I #41 Oct 27 2023 13:05:21

%S 1,1,4,33,367,4844,71597,1147653,19559062,349766457,6502419671,

%T 124822220086,2461515013103,49668479230825,1022258042480874,

%U 21406231023989503,455112508356168561,9807294681518154334,213897254891041613995,4715809234441541498539

%N 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).

%C 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.

%H Alois P. Heinz, <a href="/A364439/b364439.txt">Table of n, a(n) for n = 0..707</a>

%H Marshall Hamon, <a href="/A364439/a364439.c.txt">A364439.c</a>

%F From _Alois P. Heinz_, Jul 29 2023: (Start)

%F INVERTi transform of A005789.

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

%e Let A represent the (1,1) step, B represent the (1,-1) step, and C represent the (-2,0) step.

%e For n = 1, the only valid path is ABC.

%e For n = 2, the 4 valid paths are AABBCC, AABCBC, ABABCC, ABACBC.

%p b:= proc(n, l) option remember; `if`(n<1, 1, add((h->

%p       `if`(h[2]>h[1] or h[1]>=n or min(h)<0 or n>1 and h=[0$2],

%p            0, b(n-1, h)))(l-w), w=[[1, 1], [1, -1], [-2, 0]]))

%p     end:

%p a:= n-> b(3*n-1, [2, 0]):

%p seq(a(n), n=0..25);  # _Alois P. Heinz_, Jul 28 2023

%p # second Maple program:

%p f:= proc(n) option remember; (3*n)!*mul(i!/(n+i)!, i=0..2) end:	

%p a:= proc(n) option remember; `if`(n=0, 1,

%p       f(n)-add(f(n-i)*a(i), i=1..n-1))

%p     end:

%p seq(a(n), n=0..25);  # _Alois P. Heinz_, Jul 29 2023

%t f[n_] := f[n] = (3n)!*Product[i!/(n+i)!, {i, 0, 2}];

%t a[n_] := a[n] = If[n == 0, 1, f[n] - Sum[f[n-i]*a[i], {i, 1, n-1}]];

%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Oct 27 2023, after _Alois P. Heinz_ *)

%o (C) /* See Hamon Link */

%Y Cf. A005789, A011655.

%K nonn,walk

%O 0,3

%A _Marshall Hamon_, Jul 24 2023

%E More terms from _Alois P. Heinz_, Jul 27 2023