In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements.
Contents
Classes avoiding one pattern of length 3
There are two symmetry classes and a single Wilf class for single permutations of length three.
Classes avoiding one pattern of length 4
There are seven symmetry classes and three Wilf classes for single permutations of length four.
No non-recursive formula counting 1324-avoiding permutations is known. A recursive formula was given by Marinov & Radoičić (2003). A more efficient algorithm using functional equations was given by Johansson & Nakamura (2014), which was enhanced by Conway & Guttmann (2015). Bevan (2015) has provided a lower bound and Bóna (2015) an upper bound for the growth of this class.
Classes avoiding two patterns of length 3
There are five symmetry classes and three Wilf classes, all of which were enumerated in Simion & Schmidt (1985).
Classes avoiding one pattern of length 3 and one of length 4
There are eighteen symmetry classes and nine Wilf classes, all of which have been enumerated. For these results, see Atkinson (1999) or West (1996).
Classes avoiding two patterns of length 4
There are 56 symmetry classes and 38 Wilf equivalence classes. Only 8 of these remain unenumerated, and the generating functions for 3 of those 8 classes are conjectured not to satisfy any algebraic differential equation (ADE) by Albert et al. (preprint); in particular, their conjecture would imply that the generating functions are not D-finite.