cp's OEIS Frontend

A371963 a(n) is the sum of all valleys in the set of Catalan words of length n.

%I A371963 #27 Apr 15 2024 13:12:54
%S A371963 0,0,0,0,1,8,44,209,924,3927,16303,66691,270181,1087371,4356131,
%T A371963 17394026,69289961,275543036,1094352236,4342295396,17218070066,
%U A371963 68239187876,270351828476,1070824260326,4240695090452,16792454677874,66492351226050,263285419856250,1042540731845950
%N A371963 a(n) is the sum of all valleys in the set of Catalan words of length n.
%H A371963 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 A371963 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 A371963 a(n) = Sum_{i=1..n-1} binomial(2*(n-i)-1,n-i-3).
%F A371963 a(n) ~ 2^(2*n)/(6*sqrt(Pi*n)).
%F A371963 a(n) - a(n-1) = A003516(n-2).
%e A371963 a(4) = 1 because there is 1 Catalan word of length 4 with one valley: 0101.
%e A371963 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 A371963 a:= proc(n) option remember; `if`(n<4, 0,
%p A371963       a(n-1)+binomial(2*n-3, n-4))
%p A371963     end:
%p A371963 seq(a(n), n=0..28);  # _Alois P. Heinz_, Apr 15 2024
%t A371963 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 A371963 (Python)
%o A371963 from math import comb
%o A371963 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 A371963 Cf. A371964, A371965.
%Y A371963 Cf. A003516.
%K A371963 nonn
%O A371963 0,6
%A A371963 _Stefano Spezia_, Apr 14 2024