Permutations avoiding a nonconsecutive instance of a 2- or 3-letter pattern

Original · EN

We count permutations avoiding a nonconsecutive instance of a two- or three-letter pattern, that is, the pattern may occur but only as consecutive entries in the permutation. Two-letter patterns give rise to the Fibonacci numbers. The counting sequences for the two representative three-letter patterns, 321 and 132, have respective generating functions (1+x²)(C(x)-1)/(1+x+x²-x C(x)) and C(x+x³) where C(x) is the generating function for the Catalan numbers.