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

%I #27 Apr 15 2024 13:12:44

%S 0,0,0,0,1,7,35,155,650,2652,10660,42484,168454,665874,2627130,

%T 10353290,40775045,160534895,631970495,2487938015,9795810125,

%U 38576953505,151957215305,598732526105,2359771876175,9303298456451,36688955738099,144732209103699,571117191135799

%N a(n) is the sum of all symmetric valleys 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, pp. 16-17.

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

%F a(n) = (3*n - 2)*A000108(n-1) - A079309(n) for n > 0.

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

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

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

%e a(4) = 1 because there is 1 Catalan word of length 4 with one symmetric valley: 0101.

%e a(5) = 7 because there are 7 Catalan words of length 5 with one symmetric valley: 00101, 01001, 01010, 01011, 01012, 01101, and 01212 (see example at p. 16 in Baril et al.).

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

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

%p end:

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

%t CoefficientList[Series[(1-4x+2x^2-(1-2x)Sqrt[1-4x])/(2(1-x) Sqrt[1-4x]),{x,0,29}],x]

%o (Python)

%o from math import comb

%o def A371964(n): return sum(comb((n-i<<1)-4,n-i-4) for i in range(n-3)) # _Chai Wah Wu_, Apr 15 2024

%Y Cf. A371963, A371965.

%Y Cf. A000108, A002694, A079309.

%K nonn

%O 0,6

%A _Stefano Spezia_, Apr 14 2024