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

0, 0, 0, 0, 1, 8, 44, 209, 924, 3927, 16303, 66691, 270181, 1087371, 4356131, 17394026, 69289961, 275543036, 1094352236, 4342295396, 17218070066, 68239187876, 270351828476, 1070824260326, 4240695090452, 16792454677874, 66492351226050, 263285419856250, 1042540731845950

Offset

0,6

Links

Table of n, a(n) for n=0..28.

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

Cf. A371964, A371965.

Cf. A003516.

Sequence in context: A003220 A270318 A270330 * A265613 A271813 A270678

Adjacent sequences: A371960 A371961 A371962 * A371964 A371965 A371966

Keyword

nonn

Author

Stefano Spezia, Apr 14 2024

Status

approved