Permutation class

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

A permutation class is a set C of permutations such that every pattern of any permutation in C is also in C. In other words, it’s a hereditary property with respect to pattern containment. It’s also called a pattern class or closed class. Each class can be described by its basis—the minimal permutations that are not in C. If the basis has just one element, the class is principal. For example, the stack-sortable permutations form a principal class defined by forbidding the pattern 231. Some classes have multiple, or even infinitely many, forbidden patterns. A class that doesn’t contain all permutations is called proper.

In the 1980s, Stanley and Wilf conjectured that every proper class C has at most exponential growth: there exists a constant K with |C_n| ≤ K^n for all n. This was proved by Marcus and Tardos. For principal classes, the exact exponential growth rate exists, but it is still open whether such a limit exists for all other classes. Two classes are Wilf equivalent if, for every n, they contain the same number |C_n| of permutations of length n; these equivalence classes are called Wilf classes. Many counting results and Wilf equivalences are known for various permutation classes.