The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #22 Apr 13 2025 19:30:37
%S 1,1,1,1,3,9,21,41,79,169,393,913,2051,4537,10165,23257,53759,124153,
%T 286009,660161,1531875,3571753,8348981,19539209,45792719,107546633,
%U 253153609,597034609,1410131683,3334984025,7897992213,18730123449,44476842431,105740699609,251664629689
%N A family of marked Motzkin-like paths.
%C 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*.
%F 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).
%F G.f. A(x) satisfies: A(t) = 1+t*A(t)+t*(A(t)-1-t*A(t))+2*t^4*A(t)^2, or 2*t^4*A(t)^2-(1-t)^2*A(t)+1-t = 0.
%F a(n) = Sum_{k=0..floor(n/4)} binomial(n-k,3*k)*2^k*Catalan(k).
%F Recurrence: a(n+4) = 2*a(n+3) - a(n+2) + 2*Sum_{k=0..n} a(k)*a(n-k).
%F 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.
%F a(n) ~ (1/2)*sqrt((4-X)/(2*Pi))*X^(-n-2)/n^(3/2),
%F where X = 0.40355658567370456... is the unique positive real root of 8*x^3-7*x^2+4*x-1.
%t CoefficientList[Series[((1-t)^2-Sqrt[1-4t+6t^2-4t^3-7t^4+8t^5])/(4t^4),{t,0,100}],t]
%t Table[Sum[Binomial[n-k,3k] 2^k CatalanNumber[k], {k,0,n/4}], {n,0,100}]
%Y Cf. A023426.
%K nonn,easy
%O 0,5
%A _Emanuele Munarini_, Jul 12 2024