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

Author

Emeric Deutsch, Jun 06 2011

Keywords

• nonn

Examples

			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)).
		

Links

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

Crossrefs

Cf. A088855.

Programs

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 *)

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

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