A307464 Number of Catalan words of length n avoiding the pattern 000.

1, 1, 2, 4, 9, 19, 42, 90, 197, 425, 926, 2004, 4357, 9443, 20510, 44482, 96569, 209505, 454730, 986676, 2141361, 4646659, 10084066, 21882682, 47488221, 103052201, 223634182, 485302564, 1053152909, 2285426419, 4959582582, 10762708930, 23356030257, 50684574465

Offset

0,3

Links

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

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 (1,3,-1).

Formula

a(n) = A125691(n)-2*A125691(n-2).

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

Maple

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

Mathematica

LinearRecurrence[{1, 3, -1}, {1, 1, 2}, 40] (* Harvey P. Dale, Aug 06 2019 *)

Crossrefs

Cf. A000108, A125691, A356697, A356698.

Sequence in context: A036622 A001384 A089941 * A127681 A192923 A192673

Adjacent sequences: A307461 A307462 A307463 * A307465 A307466 A307467

Keyword

nonn,easy

Author

R. J. Mathar, Apr 09 2019

Status

approved