|
%I #27 Apr 15 2024 13:12:54
%S 0,0,0,0,1,8,44,209,924,3927,16303,66691,270181,1087371,4356131,
%T 17394026,69289961,275543036,1094352236,4342295396,17218070066,
%U 68239187876,270351828476,1070824260326,4240695090452,16792454677874,66492351226050,263285419856250,1042540731845950
%N a(n) is the sum of all valleys in the set of Catalan words of length n.
%H Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, <a href="https://arxiv.org/abs/2404.05672">Enumerating runs, valleys, and peaks in Catalan words</a>, arXiv:2404.05672 [math.CO], 2024. See Corollary 4.5, p. 15.
%F G.f.: (1-5*x+5*x^2-(1-3*x+x^2)*sqrt(1-4*x))/(2*(1-x)*x*sqrt(1-4*x)).
%F a(n) = Sum_{i=1..n-1} binomial(2*(n-i)-1,n-i-3).
%F a(n) ~ 2^(2*n)/(6*sqrt(Pi*n)).
%F a(n) - a(n-1) = A003516(n-2).
%e a(4) = 1 because there is 1 Catalan word of length 4 with one valley: 0101.
%e a(5) = 8 because there are 8 Catalan words of length 5 with one valley: 00101, 01010, 01011, 01012, 01101, 01201, and 01212 (see Figure 9 at p. 14 in Baril et al.).
%p a:= proc(n) option remember; `if`(n<4, 0,
%p a(n-1)+binomial(2*n-3, n-4))
%p end:
%p seq(a(n), n=0..28); # _Alois P. Heinz_, Apr 15 2024
%t CoefficientList[Series[(1 - 5x+5x^2-(1-3x+x^2)Sqrt[1-4x])/(2(1-x)x Sqrt[1-4x]),{x,0,28}],x]
%o (Python)
%o from math import comb
%o def A371963(n): return sum(comb((n-i<<1)-3,n-i-4) for i in range(n-3)) # _Chai Wah Wu_, Apr 15 2024
%Y Cf. A371964, A371965.
%Y Cf. A003516.
%K nonn
%O 0,6
%A _Stefano Spezia_, Apr 14 2024
|
