Permutations avoiding two patterns of length three
Electronic Journal of Combinatorics 9 (2) (2003), #R6, 19 pp.
We study permutations that avoid two distinct patterns of length three and any additional set of patterns. We begin by showing how to enumerate these permutations using generating trees, generalizing the work of Mansour. We then find sufficient conditions for when the number of such permutations is given by a polynomial and answer a question of Egge. Afterwards, we show how to use these computations to count permutations that avoid two distinct patterns of length three and contain other patterns a prescribed number of times.
Download the paper:
Related link:
- The paper ends “For a start, it would be nice to know if all the pattern-avoidance trees with bounded degrees are isomorphic to finitely labeled generating trees.” I proved this in Finitely-labeled generating trees and restricted permutations.