%I #40 Dec 19 2022 10:31:57
%S 0,1,3,7,17,36,82,169,373,760,1646,3334,7130,14392,30500,61429,129293,
%T 260016,544342,1093546,2279470,4575736,9504188,19067162,39486402,
%U 79180816,163561932,327866764,675791828,1354258096,2786074952,5581844749,11464229693,22963817056,47094437222,94318519234,193174606118
%N Number of up steps in all length n left factors of Dyck paths.
%H Fung Lam, <a href="/A014314/b014314.txt">Table of n, a(n) for n = 0..3300</a>
%H Toufik Mansour, Gokhan Yilidirim, <a href="https://www.doi.org/10.3906/mat-1901-86">Longest increasing subsequences in involutions avoiding patterns of length three</a>, Turkish Journal of Mathematics (2019), Section 2.4
%F G.f.: g(z)=(1-q)*(z+q)/(2*z*q*(1-2*z)), where q = sqrt(1-4*z^2).
%F a(n) = sum(k>=0, k*A120730(n,k)).
%F 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
%F 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
%F 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
%F 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
%F 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
%F a(n) ~ 2^(n-1/2)*sqrt(n)/sqrt(Pi) * (1 + sqrt(Pi)/sqrt(2*n)). - _Vaclav Kotesovec_, Mar 20 2014
%F G.f.: (1 - x - (1 - x - 4*x^2) / sqrt(1 - 4*x^2)) / (2 * x * (1 - 2*x)). - _Michael Somos_, Mar 23 2014
%F From _Vaclav Kotesovec_, Nov 04 2017: (Start)
%F For n > 0, a(n) = 2^(n-1) + (n-1)* binomial(n-1, n/2) if n is even,
%F a(n) = 2^(n-1) + (n-1)* binomial(n, (n-1)/2)/2 if n is odd. (End)
%e 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)).
%e G.f. = x + 3*x^2 + 7*x^3 + 17*x^4 + 36*x^5 + 82*x^6 + 169*x^7 + 373*x^8 + ...
%p 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);
%t 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 *)
%t 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 *)
%o (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
%Y Cf. A120730.
%K nonn
%O 0,3
%A _Emeric Deutsch_