Consider two permutations on symbols and on symbols where is greater than . In the study of permutation patterns we say that is contained (or involved) in if there is some subsequence of which is in the same relative order as the symbols in and is written as
For example, since the subsequence (or equivalently ) is in the same relative order as (ie. strictly increasing)
If is not contained in , then we say that avoids .
A Permutation Class is the set of all permutations closed downwards under the containment order i.e. if is a member of and then is also a member of
The most common Permutation Class in the study of Permutation Patterns in the the Avoidance Class of all permutations on or less symbols which avoid .
For example is the set of strictly decreasing permutations, i.e. 21, 321, 4321,
A widely studied feature of Permutation classes is how the size of the class increases with . We can write for the size of the class as a function of n, if two different classes have the same growth rate then they are Wilf-equivalent.
In probably the first result in the field. MacMahon showed that the permutations that can be split into two decreasing sequences i.e. the 123-avoiding permutations, are counted by the Catalan numbers.
A theorem due to Erdos and Szekeres can be interpreted in terms of permutation patterns, as every permutation of length at least must contain either or .
In The Art of Computer Programming, Don Knuth considers which permutations can be sorted by stacks, he showed that this is equivalent to the permutations that avoid and showed that these permutations are also counted by the Catalan numbers, and hence and are Wilf-equivalent.
Richard Stanley and Herb Wilf independently conjectured that all proper pattern avoidance classes have a growth rate which is at most exponential, that is for all permutations there exists some constant such that . This conjecture is in some sense surprising as the growth rate of permutations in general is which is faster than exponential.
This conjecture was proved by Adam Marcus and Gabor Tardos in 2004 and is hence a theory rather than a conjecture. Doron Zeilberger (who rarely disappoints) has a lovely talk "How Adam Marcus and Gabor Tardos Divided and Conquered the Stanley-Wilf Conjecture (An Etude in Paramathematics)" which is also an example of what he calls Para-mathematics which is the fusion of story-telling and mathematics.
Another good survery article which is available on Arxiv is Vince Vatter's Permutation Classes