OFFSET
0,1
COMMENTS
If n>0, number of Catalan words of length n avoiding the pattern 1234. The unrestricted Catalan words of length n are enumerated by A000108(n-1).
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..1000
Toufik Mansour and Mark Shattuck, Avoidance of classical patterns by Catalan sequences, Filomat 31, No. 3, 543-558 (2017). Corollary 2.5.
Index entries for linear recurrences with constant coefficients, signature (8,-25,39,-32,13,-2).
FORMULA
G.f.: ( 2-15*x+43*x^2-59*x^3+39*x^4-9*x^5 ) / ( (2*x-1)*(x^2-3*x+1)*(x-1)^3 ).
MATHEMATICA
LinearRecurrence[{8, -25, 39, -32, 13, -2}, {2, 1, 1, 2, 5, 14}, 50] (* or *)
A356696[n_] := Fibonacci[2*n - 1] - 2^n + Binomial[n, 2] + 2;
Array[A356696, 50, 0] (* Paolo Xausa, Aug 29 2024 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
R. J. Mathar, Aug 23 2022
STATUS
approved