cp's OEIS Frontend

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.

%I A191522 #28 Sep 15 2023 04:23:55
%S A191522 0,0,0,1,3,8,20,45,105,224,504,1050,2310,4752,10296,21021,45045,91520,
%T A191522 194480,393822,831402,1679600,3527160,7113106,14872858,29953728,
%U A191522 62403600,125550100,260757900,524190240,1085822640,2181340125,4508102925,9051563520,18668849760
%N 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.
%C A191522 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
%H A191522 G. C. Greubel, <a href="/A191522/b191522.txt">Table of n, a(n) for n = 0..1000</a>
%H A191522 Mathematics Stack Exchange, <a href="https://math.stackexchange.com/a/4751513/573047">Possible new formula for OEIS A191522</a>
%F A191522 a(n) = Sum_{k>=0} k*A191521(n,k).
%F A191522 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).
%F A191522 a(n) ~ 2^(n-3/2)*sqrt(n)/sqrt(Pi). - _Vaclav Kotesovec_, Mar 21 2014
%F A191522 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
%F A191522 a(n) = floor((n-1)/2)*binomial(n-1,floor((n-1)/2)+1), n > 0. - _Fabio Visonà_, Aug 13 2023
%e A191522 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).
%p A191522 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);
%t A191522 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 *)
%o A191522 (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
%Y A191522 Cf. A191521.
%K A191522 nonn
%O A191522 0,5
%A A191522 _Emeric Deutsch_, Jun 05 2011