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

0, 0, 0, 0, 1, 2, 7, 14, 37, 74, 176, 352, 794, 1588, 3473, 6946, 14893, 29786, 63004, 126008, 263950, 527900, 1097790, 2195580, 4540386, 9080772, 18696432, 37392864, 76717268, 153434536, 313889477, 627778954, 1281220733, 2562441466, 5219170052, 10438340104

Offset

0,6

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) = Sum_{k=0..n} k*A191387(n,k).

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

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

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

Example

a(5)=2 because in HHHHH, HHHUD, HHUDH, HUDHH, HUUDD, UDHHH, UDHUD, UUDDH, HUDUD, and UDUDH only the last 2 paths have 1 valley at level 0; here U=(1,1), D=(1,-1), H=(1,0).

Maple

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

Mathematica

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

Prog

(PARI) z='z+O('z^50); concat([0, 0, 0, 0], Vec(2*(1-2*z^2 -sqrt(1-4*z^2)) /(1 - 2*z + sqrt(1-4*z^2))^2)) \\ G. C. Greubel, Feb 12 2017

Crossrefs

Cf. A191387. Convolution square of A037952 (shifted 2 places right).

Sequence in context: A256272 A320651 A167762 * A191319 A018497 A178748

Adjacent sequences: A191386 A191387 A191388 * A191390 A191391 A191392

Keyword

nonn

Author

Emeric Deutsch, Jun 02 2011

Status

approved