A185132 Number of 4-Motzkin paths of length n with no level steps at height 0.

1, 0, 1, 4, 18, 84, 405, 2004, 10126, 52048, 271338, 1431400, 7627348, 40994652, 221984157, 1209902388, 6632482710, 36544255968, 202275553662, 1124212840440, 6271377279804, 35102535960360, 197081848211394, 1109621661515016, 6263608341803916

Offset

1,4

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.

Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Further Results on Paths in an n-Dimensional Cubic Lattice, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2.

Formula

G.f. (for offset 0): (1+4x-sqrt(1-8x+12x^2))/(2x^2+8x).

G.f. as continued fraction is 1/(1-0*x-x^2/(1-4*x-x^2/(1-4*x-x^2/(1-4*x-x^2/(.....

a(s) = Sum_{n=1..s}( Sum_{k=0..floor((s-2*n)/2)} 4^(s-2*n-2*k)*(n/(n+2*k))*binomial(n+2*k, k)*binomial(s-n-1, s-2*n-2*k) ) with s>=2.

D-finite with recurrence: 4*n*a(n) +(48-31n)*a(n-1) +4*(10n-33)*a(n-2) +12*(n-3)*a(n-3)=0. - R. J. Mathar, Jan 27 2012

a(n) ~ 3 * 6^(n-1/2) / (25*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jan 31 2014

a(n) = 1/(n+1)*Sum_{j=0..floor(n/2)} 4^(n-2*j)*C(n+1,j)*C(n-j-1,n-2*j). - Vladimir Kruchinin, Apr 04 2019

Maple

with(LREtools): with(FormalPowerSeries): # requires Maple 2022
ogf:= (1+4*x-sqrt(1-8*x+12*x^2))/(2*x^2+8*x):
init:= [1, 0, 1, 4, 18, 84, 405, 2004];
iseq:= seq(u(i-1)=init[i], i=1..nops(init)): req:= FindRE(ogf, x, u(n));
rmin:= subs(n=n-4, MinimalRecurrence(req, u(n), {iseq})[1]); # Mathar's recurrence
a:= gfun:-rectoproc({rmin, iseq}, u(n), remember):
seq(a(n), n=0..24); # Georg Fischer, Nov 03 2022

Mathematica

CoefficientList[Series[(1+4*x-Sqrt[1-8*x+12*x^2])/(2*x^2+8*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Jan 31 2014 *)

Prog

(PARI) x='x+O('x^50); Vec((1+4*x-sqrt(1-8*x+12*x^2))/(2*x^2+8*x)) \\ G. C. Greubel, Jun 23 2017

Crossrefs

Cf. A117641, A000957, A001006, A005043.

Sequence in context: A293490 A010849 A007859 * A085923 A110166 A046885

Adjacent sequences: A185129 A185130 A185131 * A185133 A185134 A185135

Keyword

nonn

Author

José Luis Ramírez Ramírez, Jan 26 2012

Status

approved