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,3

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.

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

Example

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

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

Prog

(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

Crossrefs

Cf. A191387.

Sequence in context: A246360 A005627 A191794 * A194850 A062692 A182024

Adjacent sequences: A191385 A191386 A191387 * A191389 A191390 A191391

Keyword

nonn

Author

Emeric Deutsch, Jun 02 2011

Status

approved