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
Keywords
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.
Programs
-
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 *) -
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
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