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

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

Crossrefs

Cf. A000108, A125691, A356697, A356698.

Programs

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

Formula

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

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