OFFSET
0,6
LINKS
Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See Corollary 4.5, p. 15.
FORMULA
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)).
a(n) = Sum_{i=1..n-1} binomial(2*(n-i)-1,n-i-3).
a(n) ~ 2^(2*n)/(6*sqrt(Pi*n)).
a(n) - a(n-1) = A003516(n-2).
EXAMPLE
a(4) = 1 because there is 1 Catalan word of length 4 with one valley: 0101.
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.).
MAPLE
a:= proc(n) option remember; `if`(n<4, 0,
a(n-1)+binomial(2*n-3, n-4))
end:
seq(a(n), n=0..28); # Alois P. Heinz, Apr 15 2024
MATHEMATICA
CoefficientList[Series[(1 - 5x+5x^2-(1-3x+x^2)Sqrt[1-4x])/(2(1-x)x Sqrt[1-4x]), {x, 0, 28}], x]
PROG
(Python)
from math import comb
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Stefano Spezia, Apr 14 2024
STATUS
approved