A014314 Number of up steps in all length n left factors of Dyck paths.

0, 1, 3, 7, 17, 36, 82, 169, 373, 760, 1646, 3334, 7130, 14392, 30500, 61429, 129293, 260016, 544342, 1093546, 2279470, 4575736, 9504188, 19067162, 39486402, 79180816, 163561932, 327866764, 675791828, 1354258096, 2786074952, 5581844749, 11464229693, 22963817056, 47094437222, 94318519234, 193174606118

Offset: 0

Author

Emeric Deutsch

Keywords

• nonn

Examples

			a(4)=17 because in UDUD, UDUU, UUDD, UUDU, UUUD, and UUUU we have a total of 2+3+2+3+3+4=17 up steps (U = (1,1), D=(1,-1)).
G.f. = x + 3*x^2 + 7*x^3 + 17*x^4 + 36*x^5 + 82*x^6 + 169*x^7 + 373*x^8 + ...
		

Links

• Fung Lam, Table of n, a(n) for n = 0..3300
• Toufik Mansour, Gokhan Yilidirim, Longest increasing subsequences in involutions avoiding patterns of length three, Turkish Journal of Mathematics (2019), Section 2.4

Crossrefs

Cf. A120730.

Programs

Maple

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

Mathematica

CoefficientList[Series[(1-Sqrt[1-4*x^2])*(x+Sqrt[1-4*x^2])/(2*x*Sqrt[1-4*x^2]*(1-2*x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)
Flatten[{0, Table[2^(n-1) + (n-1)*If[EvenQ[n], Binomial[n-1, n/2], Binomial[n, (n-1)/2]/2], {n, 1, 40}]}] (* Vaclav Kotesovec, Nov 04 2017 *)

PARI

z='z+O('z^66); q = sqrt(1-4*z^2); concat([0], Vec((1-q)*(z+q)/(2*z*q*(1-2*z))) ) \\ Joerg Arndt, Sep 16 2014

Formula

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

a(n) = sum(k>=0, k*A120730(n,k)).

D-finite with recurrence: (n+1)*a(n) = 4096*(11-n)*a(n-12) + 3072*(2*n-21)*a(n-11) + 256*(7*n-44)*a(n-10) + 128*(445-56*n)*a(n-9) + 128*(16*n-137)*a(n-8) + 32*(84*n-453)*a(n-7) + 32*(267-51*n)*a(n-6) + 8*(53-28*n)*a(n-5) + 24*(16*n-45)*a(n-4) + 2*(79-32*n)*a(n-3) + (14-25*n)*a(n-2) + (10*n+1)*a(n-1), n>=12. - Fung Lam, Mar 09 2014

0 = a(n)*32*(n+1) + a(n+1)*8*(-n+1) + a(n+2)*(-20*n-68) + a(n+3)*(6*n+20) + a(n+4)*(3*n+16) + a(n+5)*(-n-6) if n>=0. - Michael Somos, Mar 10 2014

0 = a(n)*8*(n+1)*(n^2+6*n+4) + a(n+1)*-4*(n^3+7*n^2+14*n+14) + a(n+2)*-2*(n^3+8*n^2+11*n-14) + a(n+3)*(n+4)*(n^2+4*n-1) if n>=0. - Michael Somos, Mar 10 2014

0 = a(n) * (+64*a(n+1) -48*a(n+2) -8*a(n+3) +8*a(n+4)) + a(n+1) * (-48*a(n+1) +28*a(n+2) +14*a(n+3) -6*a(n+4)) + a(n+2) * (+6*a(n+2) -5*a(n+3) -a(n+4)) + a(n+3) * (-a(n+3) +a(n+4)) if n>=0. - Michael Somos, Mar 10 2014

D-finite Recurrence (of order 3): (n+1)*(n^2 - 2*n - 4)*a(n) = 2*(n^3 - n^2 - 10*n - 2)*a(n-1) + 4*(n^3 - 2*n^2 - n + 8)*a(n-2) - 8*(n-2)*(n^2-5)*a(n-3). - Vaclav Kotesovec, Mar 20 2014

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

G.f.: (1 - x - (1 - x - 4*x^2) / sqrt(1 - 4*x^2)) / (2 * x * (1 - 2*x)). - Michael Somos, Mar 23 2014

From Vaclav Kotesovec, Nov 04 2017: (Start)

For n > 0, a(n) = 2^(n-1) + (n-1)* binomial(n-1, n/2) if n is even,

a(n) = 2^(n-1) + (n-1)* binomial(n, (n-1)/2)/2 if n is odd. (End)