A166292 Number of peaks at odd level in all Dyck paths of semilength n with no UUU's and no DDD's, (U=(1,1), D=(1,-1)). These Dyck paths are counted by the secondary structure numbers (A004148).

0, 1, 2, 5, 12, 29, 72, 181, 460, 1178, 3030, 7815, 20188, 52193, 134992, 349205, 903398, 2337135, 6046310, 15642402, 40469824, 104708914, 270937964, 701129755, 1814581514, 4696886211, 12159165336, 31481922733, 81523933604, 211143257951

Offset

0,3

Links

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

Formula

a(n) = Sum_{k=0,..,n} k*A166291(n,k).

G.f.: G=[z^2 + 3z - 2 + (z^4 + z^3 - z^2 - 4z + 2)g(z)]/[(1 - z - z^2)(1 - z - z^2 - 2z^3*g(z)], where g=g(z) satisfies g = 1 + zg + z^2*g + z^3*g^2.

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

Equivalently, a(n) ~ phi^(2*n + 5) / (4 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021

D-finite with recurrence -(n+3)*(12263959*n-453745718)*a(n) +(-12263959*n^2-1898630196*n-3269930920)*a(n-1) +2*(201299201*n^2-33603137*n-693679841)*a(n-2) +4*(-226348358*n^2+2057096353*n-415271997)*a(n-3) +(282398701*n^2-4452810911*n+4125507350)*a(n-4) +(46943591*n^2-3487699726*n+8812781352)*a(n-5) +4*(214523727*n^2-2147935054*n+5837738425)*a(n-6) +2*(-101430217*n^2+3147700949*n-14145800266)*a(n-7) -5*(76453537*n-336152052)*(n-7)*a(n-8) +(n-8)*(126836791*n-1033250150)*a(n-9)=0. - R. J. Mathar, Jul 26 2022

Example

a(3)=5 because the paths (UD)(UD)(UD), (UD)UUDD, UUDD(UD), and UUDUDD have 3 + 1 + 1 + 0 peaks at odd level (shown between parentheses).

Maple

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

Mathematica

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

Crossrefs

Cf. A004148, A166291, A166293, A166294

Sequence in context: A227237 A005593 A122745 * A010374 A307788 A025273

Adjacent sequences: A166289 A166290 A166291 * A166293 A166294 A166295

Keyword

nonn

Author

Emeric Deutsch, Oct 12 2009

Status

approved