A167636 Number of peaks at odd level in all Dyck paths of semilength n that have no ascents and no descents of length 1.
0, 0, 0, 1, 0, 5, 4, 23, 36, 123, 252, 720, 1664, 4427, 10804, 27971, 69972, 179469, 454300, 1162529, 2961056, 7579620, 19376728, 49659406, 127263208, 326610827, 838550920, 2154985059, 5540935616, 14257159799, 36703613556, 94544579575
Offset: 0
Keywords
Examples
a(5)=5 because UUDDUU(UD)DD, UU(UD)DDUUDD, UU(UD)DU(UD)DD, and UUUU(UD)DDDD have 1 + 1 + 2 + 1 = 5 odd-level peaks (shown between parentheses).
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
Programs
-
Maple
G := (1/2)*z*(1-z^2-2*z^3+z^4-(1+z-z^2)*sqrt((1+z+z^2)*(1-3*z+z^2)))/((1+z-z^2)*sqrt((1+z+z^2)*(1-3*z+z^2))): Gser := series(G, z = 0, 35): seq(coeff(Gser, z, n), n = 0 .. 32);
-
Mathematica
CoefficientList[Series[1/2*x*(1-x^2-2*x^3+x^4-(1+x-x^2)*Sqrt[(1+x+x^2)*(1-3*x+x^2)])/((1+x-x^2)*Sqrt[(1+x+x^2)*(1-3*x+x^2)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *) -
PARI
x='x+O('x^50); concat([0,0,0], Vec(1/2*x*(1-x^2-2*x^3+x^4-(1+x-x^2)*sqrt((1+x+x^2)*(1-3*x+x^2)))/((1+x-x^2)*sqrt((1+x+x^2)*(1-3*x+x^2))))) \\ G. C. Greubel, Feb 12 2017
Formula
a(n) = Sum_{k=0..n} k*A167634(n,k).
G.f.: G(z) = z(1 - z^2 - 2z^3 + z^4 - (1 + z - z^2)*sqrt((1 + z + z^2)(1 - 3z + z^2)))/(2(1 + z - z^2)sqrt((1 + z + z^2)(1 - 3z + z^2))).
a(n) ~ sqrt(3/sqrt(5)-1) * (3+sqrt(5))^n / (sqrt(Pi*n) * 2^(n+5/2)). - Vaclav Kotesovec, Mar 20 2014
Equivalently, a(n) ~ phi^(2*n - 1) / (4 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021
D-finite with recurrence +(n-1)*(38*n-213)*a(n) +38*(n-2)*(n-4)*a(n-1) +4*(-84*n^2+680*n-1185)*a(n-2) -26*(9*n-19)*(n-4)*a(n-3) +(n-5)*(356*n-1879)*a(n-4) +2*(111*n-491)*(n-6)*a(n-5) +2*(95*n-137)*(n-7)*a(n-6) -50*(8*n-23)*(n-8)*a(n-7) +3*(36*n-97)*(n-9)*a(n-8)=0. - R. J. Mathar, Jul 26 2022