A371965 a(n) is the sum of all peaks in the set of Catalan words of length n.

0, 0, 0, 1, 6, 27, 111, 441, 1728, 6733, 26181, 101763, 395693, 1539759, 5997159, 23381019, 91244934, 356427459, 1393585779, 5453514729, 21358883439, 83718027429, 328380697629, 1288947615849, 5062603365999, 19896501060225, 78239857877649, 307831771279549, 1211767933187601

Offset

0,5

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.7, p. 19.

Formula

G.f.: (1 - 3*x - (1 - x)*sqrt(1 - 4*x))/(2*(1 - x)*sqrt(1 - 4*x)).

a(n) = Sum_{i=1..n-1} binomial(2*(n-i)-1,n-i-2).

a(n) ~ 2^(2*n)/(6*sqrt(Pi*n)).

a(n)/A371963(n) ~ 1.

a(n) - a(n-1) = A002054(n-2).

From Mélika Tebni, Jun 15 2024: (Start)

E.g.f.: (exp(2*x)*BesselI(0,2*x)-1)/2 - exp(x)*Integral_{x=-oo..oo} BesselI(0,2*x)*exp(x) dx.

a(n) = binomial(2*n,n)*(1/2 + hypergeom([1,n+1/2],[n+1],4)) + i/sqrt(3) - 0^n/2.

a(n) = (3*A106191(n) + A006134(n) + 4*0^n) / 8.

a(n) = A281593(n) - (A000984(n) + 0^n) / 2. (End)

Example

a(3) = 1 because there is 1 Catalan word of length 3 with one peak: 010.
a(4) = 6 because there are 6 Catalan words of length 4 with one peak: 0010, 0100, 0101, 0110, 0120, and 0121 (see Figure 10 at p. 19 in Baril et al.).

Maple

a:= proc(n) option remember; `if`(n<3, 0,
      a(n-1)+binomial(2*n-3, n-3))
    end:
seq(a(n), n=0..28);  # Alois P. Heinz, Apr 15 2024
# Second Maple program:
A371965 := series((exp(2*x)*BesselI(0, 2*x)-1)/2-exp(x)*(int(BesselI(0, 2*x)*exp(x), x)), x = 0, 29):
seq(n!*coeff(A371965, x, n), n = 0 .. 28); # Mélika Tebni, Jun 15 2024

Mathematica

CoefficientList[Series[(1-3x-(1-x)Sqrt[1-4x])/(2(1-x) Sqrt[1-4x]), {x, 0, 28}], x]

Prog

(Python)
from math import comb
def A371965(n): return sum(comb((n-i<<1)-3, n-i-3) for i in range(n-2)) # Chai Wah Wu, Apr 15 2024

Crossrefs

Cf. A371963, A371964.

Cf. A002054.

Sequence in context: A003517 A108958 A005284 * A198694 A220101 A014825

Adjacent sequences: A371962 A371963 A371964 * A371966 A371967 A371968

Keyword

nonn

Author

Stefano Spezia, Apr 14 2024

Status

approved