A191387 -id:A191387 - cp's OEIS frontend

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

Emeric Deutsch, Jun 02 2011

nonn

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

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

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

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

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

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

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

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.

Original entry on oeis.org

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

Emeric Deutsch, Jun 02 2011

nonn

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

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

Cf. A191387.

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

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

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

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula