A307465 Number of Catalan words of length n avoiding the pattern 110.

1, 1, 2, 5, 13, 33, 82, 201, 489, 1185, 2866, 6925, 16725, 40385, 97506, 235409, 568337, 1372097, 3312546, 7997205, 19306973, 46611169, 112529330, 271669849, 655869049, 1583407969, 3822685010, 9228778013, 22280241061, 53789260161, 129858761410

Offset: 0

Author

R. J. Mathar, Apr 09 2019

Keywords

• nonn
• easy

Links

• J.-L. Baril, S. Kirgizov, V. Vanjovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, Disc. Math. 341 (2018) 2608-2615, Table 2.
• Index entries for linear recurrences with constant coefficients, signature (4,-4,0,1).

Programs

Maple

(1-3*x+2*x^2+x^3)/(1-x)^2/(1-2*x-x^2) ;
taylor(%,x=0,30) ;
gfun[seriestolist](%) ;

Formula

2*a(n) = A000129(n+1)-n+1 .

a(n) = A048776(n-2)+1.

G.f.: (1-3*x+2*x^2+x^3)/((1-x)^2*(1-2*x-x^2)).