A374585 A family of marked Motzkin-like paths.

1, 1, 1, 1, 3, 9, 21, 41, 79, 169, 393, 913, 2051, 4537, 10165, 23257, 53759, 124153, 286009, 660161, 1531875, 3571753, 8348981, 19539209, 45792719, 107546633, 253153609, 597034609, 1410131683, 3334984025, 7897992213, 18730123449, 44476842431, 105740699609, 251664629689

Offset: 0

Author

Emanuele Munarini, Jul 12 2024

Keywords

• nonn
• easy

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*.

Crossrefs

Cf. A023426.

Programs

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}]

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))+2*t^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.