A191522 Number of valleys in all left factors of Dyck paths of length n. A valley is a (1,-1)-step followed by a (1,1)-step.

0, 0, 0, 1, 3, 8, 20, 45, 105, 224, 504, 1050, 2310, 4752, 10296, 21021, 45045, 91520, 194480, 393822, 831402, 1679600, 3527160, 7113106, 14872858, 29953728, 62403600, 125550100, 260757900, 524190240, 1085822640, 2181340125, 4508102925, 9051563520, 18668849760

Offset: 0

Author

Emeric Deutsch, Jun 05 2011

Keywords

• nonn

Comments

a(n+2) is also the sum of the maximum elements of each subset of [n]={1,...,n} with size floor((n+1)/2). For example for n=3 there are three subsets {1,2},{1,3},{2,3} and the sum of maximum values is 2+3+3=8. - Fabio Visonà, Aug 13 2023

Examples

			a(4)=3 because the total number of valleys in UDUD, UDUU, UUDD, UUDU, UUUD, and UUUU is 1+1+0+1+0+0=3; here U=(1,1), D=(1,-1).
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Mathematics Stack Exchange, Possible new formula for OEIS A191522

Crossrefs

Cf. A191521.

Programs

Maple

q := sqrt(1-4*z^2): g := (2*((1-z-3*z^2+z^3)*q-1+z+5*z^2-3*z^3-4*z^4))/(z*q*(1-2*z-q)^2): gser := series(g, z = 0, 36): seq(coeff(gser, z, n), n = 0 .. 33);

Mathematica

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

PARI

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

Formula

a(n) = Sum_{k>=0} k*A191521(n,k).

G.f.: 2*((1-z-3*z^2+z^3)*q-1+z+5*z^2-3*z^3-4*z^4)/(z*q*(1-2*z-q)^2), where q = sqrt(1-4*z^2).

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

D-finite with recurrence -2*(n+1)*(n-3)*a(n) +(-5*n^2+29*n-6)*a(n-1) +2*(4*n+5)*(n-2)*a(n-2) +20*(n-2)*(n-3)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

a(n) = floor((n-1)/2)*binomial(n-1,floor((n-1)/2)+1), n > 0. - Fabio Visonà, Aug 13 2023