A191789 Number of length n left factors of Dyck paths having no base pyramids.

1, 1, 1, 2, 3, 6, 11, 21, 40, 76, 146, 279, 539, 1036, 2011, 3883, 7566, 14662, 28654, 55692, 109098, 212564, 417210, 814568, 1601366, 3132078, 6165732, 12077905, 23803827, 46691096, 92113651, 180893091, 357183430, 702169718, 1387539542, 2730236900, 5398831722, 10632066436

Offset

0,4

Comments

A base pyramid is a factor of the form U^j D^j (j>0), starting at the horizontal axis (here U=(1,1) and D=(1,-1)).

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Formula

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

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

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

D-finite with recurrence -94*(n+1)*(n-15)*a(n) +2*(-47*n^2+734*n-2115)*a(n-1) +8*(88*n^2-1311*n+1307)*a(n-2) +2*(235*n^2-3904*n+13597)*a(n-3) +(-1593*n^2+25078*n-72033)*a(n-4) +(-423*n^2+7074*n-25079)*a(n-5) +(1241*n^2-19834*n+66805)*a(n-6) +2*(94*n^2-1585*n+5741)*a(n-7) -4*(n-7)*(117*n-1087)*a(n-8)=0. - R. J. Mathar, Jul 24 2022

Example

a(4)=3 because we have UUDU, UUUD, and UUUU; each of the paths (UD)(UD), (UD)UU, and (UUDD) has at least one base pyramid (shown between parentheses).

Maple

c := ((1-sqrt(1-4*z^2))*1/2)/z^2: G := (1-z^2)*c/((1-z*c)*(1+z^4*c^2)): Gser := series(G, z = 0, 40): seq(coeff(Gser, z, n), n = 0 .. 37);

Mathematica

With[{c=(1-Sqrt[1-4x^2])/(2x^2)}, CoefficientList[Series[(1-x^2)c/ ((1-x c ) (1+x^4 c^2)), {x, 0, 40}], x]] (* Harvey P. Dale, Jun 19 2011 *)

Prog

(PARI) x='x+O('x^50); Vec( 2*(1-x^2)*(1-sqrt(1-4*x^2))/(x*(2*x-1+sqrt(1-4*x^2))*(3-2*x^2-sqrt(1-4*x^2))) ) \\ G. C. Greubel, Mar 27 2017

Crossrefs

Cf. A191788.

Sequence in context: A316796 A079116 A109222 * A371790 A306575 A006861

Adjacent sequences: A191786 A191787 A191788 * A191790 A191791 A191792

Keyword

nonn

Author

Emeric Deutsch, Jun 18 2011

Status

approved