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

%I #36 Jun 16 2024 06:35:06

%S 0,0,0,1,6,27,111,441,1728,6733,26181,101763,395693,1539759,5997159,

%T 23381019,91244934,356427459,1393585779,5453514729,21358883439,

%U 83718027429,328380697629,1288947615849,5062603365999,19896501060225,78239857877649,307831771279549,1211767933187601

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

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

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

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

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

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

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

%F From _Mélika Tebni_, Jun 15 2024: (Start)

%F 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.

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

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

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

%e a(3) = 1 because there is 1 Catalan word of length 3 with one peak: 010.

%e 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.).

%p a:= proc(n) option remember; `if`(n<3, 0,

%p a(n-1)+binomial(2*n-3, n-3))

%p end:

%p seq(a(n), n=0..28); # _Alois P. Heinz_, Apr 15 2024

%p # Second Maple program:

%p A371965 := series((exp(2*x)*BesselI(0,2*x)-1)/2-exp(x)*(int(BesselI(0,2*x)*exp(x), x)), x = 0, 29):

%p seq(n!*coeff(A371965, x, n), n = 0 .. 28); # _Mélika Tebni_, Jun 15 2024

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

%o (Python)

%o from math import comb

%o 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

%Y Cf. A371963, A371964.

%Y Cf. A002054.

%K nonn

%O 0,5

%A _Stefano Spezia_, Apr 14 2024