A191527 Number of turns in all left factors of Dyck paths of length n.

0, 0, 1, 3, 9, 20, 50, 105, 245, 504, 1134, 2310, 5082, 10296, 22308, 45045, 96525, 194480, 413270, 831402, 1755182, 3527160, 7407036, 14872858, 31097794, 62403600, 130007500, 260757900, 541574100, 1085822640, 2249204040, 4508102925, 9316746045

Offset

0,4

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Formula

a(n) = Sum_{k=0..n} k*binomial(floor((n-1)/2), floor(k/2))*binomial(ceiling((n-1)/2), ceiling(k/2)).

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

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

D-finite with recurrence (n+1)*a(n) + (-n-1)*a(n-1) + 2*(-4*n+5)*a(n-2) + 4*(n+1)*a(n-3) + 16*(n-3)*a(n-4) = 0. - R. J. Mathar, Jun 06 2014

Example

a(4)=9 because in UDUD, UDUU, UUDD, UUDU, UUUD, and UUUU we have a total of 3+2+1+2+1+0=9 turns (here U=(1,1) and D=(1,-1)).

Maple

g := 2*z^2*(1-4*z^2-4*z^3)/((1-2*z)*((1+z)*(1-4*z^2)*(1-2*z)+(1-z-4*z^2)*sqrt(1-4*z^2))): gser := series(g, z = 0, 35): seq(coeff(gser, z, n), n = 0 .. 32);
a := proc (n) options operator, arrow: sum(k*binomial(floor((1/2)*n-1/2), floor((1/2)*k))*binomial(ceil((1/2)*n-1/2), ceil((1/2)*k)), k = 0 .. n) end proc: seq(a(n), n = 0 .. 32);

Mathematica

CoefficientList[Series[2*x^2*(1-4*x^2-4*x^3)/((1-2*x)*((1+x)*(1-4*x^2)*(1-2*x)+(1-x-4*x^2)*Sqrt[1-4*x^2])), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 21 2014 *)

Prog

(PARI) x='x+O('x^50); concat([0, 0], Vec(2*x^2*(1-4*x^2-4*x^3)/((1-2*x)*((1+x)*(1-4*x^2)*(1-2*x)+(1-x-4*x^2)*sqrt(1-4*x^2))))) \\ G. C. Greubel, May 27 2017

Crossrefs

Cf. A088855.

Sequence in context: A147328 A364914 A220770 * A226106 A026566 A147356

Adjacent sequences: A191524 A191525 A191526 * A191528 A191529 A191530

Keyword

nonn

Author

Emeric Deutsch, Jun 06 2011

Status

approved