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

Abstract

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^2)(C(x)-1)/(1+x+x^2-x C(x)) and C(x+x^3) where C(x) is the generating function for the Catalan numbers.

Acknowledgment of priority