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
Keywords
Examples
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).
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
Programs
-
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 *)
Formula
a(n) = Sum_{k=0..n} k*A166291(n,k).
G.f.: G=(z^2 + 3*z - 2 + (z^4 + z^3 - z^2 - 4*z + 2)*g(z))/((1 - z - z^2)*(1 - z - z^2 - 2*z^3*g(z))), where g=g(z) satisfies g = 1 + z*g + 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