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
Keywords
Links
- Robert Israel, Table of n, a(n) for n = 0..1492
Programs
-
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 -
PARI
a(n) = sum(k=0, n\3, binomial(n+k, k)*binomial(2*n-2*k, n-3*k));
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).