A379462 a(n) is the total number of paths starting at (0, 0), ending at (n, 0), consisting of steps (1, 1), (1, 0), (1, -2), and staying on or above y = -3.

1, 1, 1, 4, 13, 31, 75, 204, 561, 1499, 4001, 10814, 29364, 79704, 216672, 590764, 1614421, 4419049, 12116139, 33277722, 91546143, 252209535, 695803659, 1922166420, 5316714156, 14723570406, 40820144106, 113293243636, 314759548879, 875342190283, 2436582442381

Offset

0,4

Links

Table of n, a(n) for n=0..30.

Formula

a(n) = Sum_{k=0..floor(n/3)} 2*binomial(n, k*3)*(binomial(3*k+3, k)/(k+2) - binomial(3*k, k-1)/(k+1)). - Thomas Scheuerle, Jan 07 2025

a(n) ~ 23 * (1 + 3/2^(2/3))^(n + 3/2) / (4 * sqrt(3*Pi) * n^(3/2)). - Vaclav Kotesovec, Jan 15 2025

Example

For n = 3, the a(3)=4 paths are DUU, HHH, UDU, UUD, where U=(1,1), D=(1,-2) and H=(1,0). An example of a path with these steps, but not staying on or above y = -3, is for n=6: DDUUUU.

Prog

(PARI) lista(nn) = my(v=vector(nn+5), w); print1(v[4]=1); for(n=1, nn, w=v; for(i=1, n+3, w[i]+=v[i+2]; w[i+1]+=v[i]); v=w; print1(", ", v[4])); \\ Jinyuan Wang, Jan 07 2025

Crossrefs

Cf. A071879, A116411, A378849, A378850.

Sequence in context: A307304 A097122 A378850 * A116411 A333047 A376804

Adjacent sequences: A379459 A379460 A379461 * A379463 A379464 A379465

Keyword

nonn,new

Author

Emely Hanna Li Lobnig, Dec 23 2024

Extensions

More terms from Jinyuan Wang, Jan 07 2025

Status

approved