permutation pattern
A permutation pattern is simply a permutation
viewed as its representation in one-line notation. Let be a permutation pattern on symbols. Then for any permutation , we say that contains if there is a (not necessarily contiguous) subword of of length that is order-isomorphic to . More formally,for any subset of cardinality , write
There is a isomorphism (http://planetmath.org/GroupHomomorphism) . We say that contains if there is some of cardinality such that under the isomorphism.
If a permutation does not contain , then we say that avoids the pattern .
For example, let . Then the permutation avoids , since is strictly increasing but has a descent. On the other hand, contains twice, once as the subword and once as the subword .
Knuth showed that a permutation is stack-sortable if and only if it avoids the permutation pattern .