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