A191388 Number of dispersed Dyck paths of length n (i.e., Motzkin paths of length n with no (1,0) steps at positive heights) with no valleys at level 0.

1, 1, 2, 3, 5, 8, 14, 23, 41, 69, 125, 214, 393, 682, 1267, 2223, 4171, 7385, 13976, 24935, 47544, 85377, 163863, 295900, 571216, 1036471, 2011130, 3664548, 7143068, 13063637, 25568085, 46912433, 92152906, 169570215, 334194418, 616530391, 1218694221, 2253451666, 4466410838

Offset: 0

Author

Emeric Deutsch, Jun 02 2011

Keywords

• nonn

Examples

			a(4)=5 because we have HHHH, HHUD, HUDH, UDHH, and UUDD, where U=(1,1), H=(1,0), and D=(1,-1) (UDUD does not qualify).
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Helmut Prodinger, Dispersed Dyck paths revisited, arXiv:2402.13026 [math.CO], 2024.

Crossrefs

Cf. A191387.

Programs

Maple

g := (3-sqrt(1-4*z^2))/(2-3*z+z*sqrt(1-4*z^2)): gser := series(g, z = 0, 42): seq(coeff(gser, z, n), n = 0 .. 38);

Mathematica

CoefficientList[Series[(3-Sqrt[1-4*x^2])/(2-3*x+x*Sqrt[1-4*x^2]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 21 2014 *)

Maxima

a(n):=1+sum(sum((k+1)*binomial(2*i-k,i-k)*binomial(n-2*i-1,k+1),k,0,i)/(i+1),i,0,(n-1)/2); /* Vladimir Kruchinin, Mar 27 2016 */

PARI

x='x+O('x^99); Vec((3-sqrt(1-4*x^2))/(2-3*x+x*sqrt(1-4*x^2))) \\ Altug Alkan, Mar 27 2016

Formula

a(n) = A191387(n,0).

G.f.: (3-sqrt(1-4*z^2))/(2-3*z+z*sqrt(1-4*z^2)).

a(n) ~ 2^(n+5/2) * (1+(-1)^n/49) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 21 2014

a(n) = 1+Sum_{i=0..(n-1)/2}(Sum_{k=0..i}((k+1)*binomial(2*i-k,i-k)*binomial(n-2*i-1,k+1))/(i+1)). - Vladimir Kruchinin, Mar 27 2016

D-finite with recurrence -n*a(n) +3*n*a(n-1) +2*(n-6)*a(n-2) +12*(-n+3)*a(n-3) +(7*n-24)*a(n-4) +4*(n-3)*a(n-6)=0. - R. J. Mathar, Sep 24 2021