login
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.
4
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,5
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
LINKS
Mathematics Stack Exchange, Possible new formula for OEIS A191522
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
EXAMPLE
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).
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 *)
PROG
(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
CROSSREFS
Cf. A191521.
Sequence in context: A014628 A134393 A034504 * A140481 A027928 A026624
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jun 05 2011
STATUS
approved