|
|
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
|
|
|
FORMULA
|
G.f.: g(z)=(1-q)*(z+q)/(2*z*q*(1-2*z)), where q = sqrt(1-4*z^2).
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
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|