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,3

Links

Table of n, a(n) for n=0..30.

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

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

Maple

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

Crossrefs

Sequence in context: A210496 A067676 A292507 * A116703 A007443 A120925

Adjacent sequences: A307462 A307463 A307464 * A307466 A307467 A307468

Keyword

nonn,easy

Author

R. J. Mathar, Apr 09 2019

Status

approved