A379464 a(n) is the total number of paths starting at (0, 0), ending at (n, 0), consisting of steps (1, 1), (1, 0), (1, -3), and staying on or above y = -2.
1, 1, 1, 1, 4, 16, 46, 106, 226, 514, 1306, 3466, 9002, 22634, 56330, 142026, 364743, 945303, 2448511, 6323695, 16336885, 42363693, 110340297, 288229377, 753920796, 1973799396, 5174280216, 13588243696, 35748326836, 94188788164, 248464963876, 656148369796
Offset: 0
Keywords
Examples
For n = 4, the a(4)=4 paths are HHHH, UDUU, UUDU, UUUD, where U=(1,1), D=(1,-3) and H=(1,0).
Links
- Robert Israel, Table of n, a(n) for n = 0..2271
Programs
-
Maple
f:= proc(n,y) option remember; if n = 0 then if y = 0 then return 1 else return 0 fi fi; if y > n then return 0 fi; if y >= -1 then procname(n-1,y-1) + procname(n-1,y) + procname(n-1,y+3) else procname(n-1,y) + procname(n-1,y+3) fi; end proc: map(f, [$0..40],0); # Robert Israel, Jan 23 2025 -
PARI
a(n) = sum(k=0, floor(n/4), 3*binomial(n, k*4)*binomial(4*k+3, k)/(4*k+3)) \\ Thomas Scheuerle, Jan 07 2025
Formula
a(n) ~ 2^(5/2) * (1 + 4/3^(3/4))^(n + 3/2) / (3^(11/8) * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jan 15 2025
Conjecture D-finite with recurrence +3*(n+4)*(3*n+4)*(3*n+8)*a(n) +3*(-63*n^3-297*n^2-349*n-60)*a(n-1) +3*(189*n^3+270*n^2-229*n-140)*a(n-2) +15*(-63*n^3+117*n^2+44*n-64)*a(n-3) +(689*n^3-5372*n^2+6946*n-1288)*a(n-4) +(n-4)*(201*n^2+2767*n-3011)*a(n-5) -(n-5)*(579*n+257)*(n-4)*a(n-6) +229*(n-5)*(n-6)*(n-4)*a(n-7)=0. - R. J. Mathar, Jan 29 2025
Extensions
More terms from Jinyuan Wang, Jan 07 2025