OFFSET
0,5
COMMENTS
Number of lattice paths from (0,0) to (n,0) that stay weakly in the first quadrant and such that each step is either H=(1,0), U=(2,1) or D=(2,-1), where the steps H and D can be marked H*, D*, so that (in the canonical decomposition) a marked step H* cannot be followed by the empty path or by H. For instance, a(5)=9 because we have HHHHH, HUD, HUD*, H*UD, H*UD*, UDH, UD*H, UHD and UHD*.
FORMULA
G.f: A(t) = ((1-t)^2-sqrt(1-4*t+6*t^2-4*t^3-7*t^4+8*t^5))/(4*t^4).
G.f. A(x) satisfies: A(t) = 1+t*A(t)+t*(A(t)-1-t)*A(t))+2t^4*A(t)^2, or 2*t^4*A(t)^2-(1-t)^2*A(t)+1-t=0.
a(n) = Sum_{k=0..floor(n/4)} binomial(n-k,3*k)*2^k*Catalan(k).
Recurrence: a(n+4) = 2*a(n+3) - a(n+2) + 2*Sum_{k=0..n} a(k)*a(n-k).
D-finite with recurrence: (n+9)*a(n+5) -2*(2*n+15)*a(n+4) +6*(n+6)*a(n+3) -2*(2*n+9)*a(n+2) -7*(n+3)*a(n+1) +4*(2*n+3)*a(n)=0.
a(n) ~ (1/2)*sqrt((4-X)/(2*Pi))*X^(-n-2)/n^(3/2),
where X = 0.40355658567370456... is the unique positive real root of 8*x^3-7*x^2+4*x-1.
MATHEMATICA
CoefficientList[Series[((1-t)^2-Sqrt[1-4t+6t^2-4t^3-7t^4+8t^5])/(4t^4), {t, 0, 100}], t]
Table[Sum[Binomial[n-k, 3k] 2^k CatalanNumber[k], {k, 0, n/4}], {n, 0, 100}]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Emanuele Munarini, Jul 12 2024
STATUS
approved