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
Keywords
Examples
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.).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- 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.
Programs
-
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] -
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
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.
Binomial transform of A275289. - Alois P. Heinz, Jun 20 2025