login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014314 Number of up steps in all length n left factors of Dyck paths. 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
LINKS
Toufik Mansour, Gokhan Yilidirim, Longest increasing subsequences in involutions avoiding patterns of length three, Turkish Journal of Mathematics (2019), Section 2.4
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)
EXAMPLE
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 + ...
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 *)
PROG
(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
CROSSREFS
Cf. A120730.
Sequence in context: A014395 A326520 A295146 * A221792 A354124 A089099
KEYWORD
nonn
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 12:26 EDT 2024. Contains 371254 sequences. (Running on oeis4.)