A383479 Number of lattice paths from (0,0) to (n,n) using steps (1,0),(3,0),(0,1).

1, 2, 6, 24, 100, 420, 1792, 7752, 33858, 148940, 658944, 2929056, 13070876, 58521344, 262754040, 1182619280, 5334172518, 24104916504, 109111142376, 494630028200, 2245300152480, 10204575481320, 46429481139000, 211460450151600, 963971663881200, 4398118872144192

Offset

0,2

Links

Robert Israel, Table of n, a(n) for n = 0..1492

Formula

a(n) = [x^n] 1/(1 - x - x^3)^(n+1).

a(n) = (n+1) * A049140(n+1).

a(n) = Sum_{k=0..floor(n/3)} binomial(n+k,k) * binomial(2*n-2*k,n-3*k).

Maple

f:= proc(x, y) option remember;
     local t;
     t:= 0;
     if x >= 1 then t:= t + procname(x-1, y) fi;
     if x >= 3 then t:= t + procname(x-3, y) fi;
     if y >= 1 then t:= t + procname(x, y-1) fi;
     t
end proc:
f(0, 0):= 1:
seq(f(n, n), n=0..25); # Robert Israel, May 28 2025

Prog

(PARI) a(n) = sum(k=0, n\3, binomial(n+k, k)*binomial(2*n-2*k, n-3*k));

Crossrefs

Cf. A038112, A383480.

Cf. A049140, A144401, A370624.

Sequence in context: A150299 A094012 A141253 * A306672 A324063 A378190

Adjacent sequences: A383476 A383477 A383478 * A383480 A383481 A383482

Keyword

nonn

Author

Seiichi Manyama, Apr 28 2025

Status

approved