A166294 Number of peaks at even 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, 4, 12, 34, 92, 242, 628, 1616, 4138, 10570, 26970, 68798, 175545, 448176, 1145058, 2927924, 7493021, 19191836, 49195806, 126205062, 324000494, 832371414, 2139802870, 5504256592, 14166936063, 36483006046, 94000206216

Offset

1,3

Links

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

Formula

a(n) = Sum_{k=0..n-1} k*A166293(n,k).

G.f.: G=z[z - 1 + (1 - z + z^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

Example

a(3)=4 because the paths UDUDUD, UDU(UD)D, U(UD)DUD, and U(UD)(UD)D have 0 + 1 + 1 + 2 = 4 peaks at even 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*(z-1+(1-z+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 = 1 .. 30);

Mathematica

Rest[CoefficientList[Series[x*(x-1+(1-x+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, A166292, A166293.

Sequence in context: A107069 A191823 A110335 * A307305 A176753 A248873

Adjacent sequences: A166291 A166292 A166293 * A166295 A166296 A166297

Keyword

nonn

Author

Emeric Deutsch, Oct 12 2009

Status

approved