In the study of

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...

s and

permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the ...

s, a permutation class is a set

C

of permutations for which every pattern within a permutation in

C

is also in

C

. In other words, a permutation class is a

hereditary property In mathematics, a hereditary property is a property of an object that is inherited by all of its subobjects, where the meaning of ''subobject'' depends on the context. These properties are particularly considered in topology and graph theory, but al ...

of permutations, or a

downset Downset may refer to: * Downset lattice * Down set *Downset., an American rap metal band *''downset. Downset (usually stylized as downset.) is an American rap metal band from Los Angeles, California. Originally called Social Justice, the band ...

in the permutation pattern order. A permutation class may also be known as a pattern class, closed class, or simply class of permutations. Every permutation class can be defined by the minimal permutations which do not lie inside it, its ''basis''., Definition 8.1.3, p. 318. A principal permutation class is a class whose basis consists of only a single permutation. Thus, for instance, the

stack-sortable permutation In mathematics and computer science, a stack-sortable permutation (also called a tree permutation) is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable ...

s form a principal permutation class, defined by the forbidden pattern 231. However, some other permutation classes have bases with more than one pattern or even with infinitely many patterns. A permutation class that does not include all permutations is called proper. In the late 1980s, Richard Stanley and

Herbert Wilf Herbert Saul Wilf (June 13, 1931 – January 7, 2012) was a mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professor of Mathematics in Combinatorial Analysis and Computing at the University of Pennsylv ...

conjectured that for every proper permutation class

C

, there is some constant

K

such that the number

, C_n,

of length-

n

permutations in the class is

upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an elem ...

ed by

K^n

. This was known as the

Stanley–Wilf conjecture The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is singly exponential. It was proved by and is no longer a conjectur ...

until it was proved by Adam Marcus and

Gábor Tardos Gábor Tardos (born 11 July 1964) is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science. He is ...

. However although the limit :

\lim_ , C_n, ^

(a tight bound on the base of the exponential growth rate) exists for all principal permutation classes, it is open whether it exists for all other permutation classes. Two permutation classes are called Wilf equivalent if, for every

n

, both have the same number of permutations of length

n

. Wilf equivalence is an

equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...

and its equivalence classes are called Wilf classes. They are the

combinatorial class In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size. Counting sequences and isomorphi ...

es of permutation classes. The counting functions and Wilf equivalences among many specific permutation classes are known.

References

{{reflist, refs= {{citation , last = Kitaev , first = Sergey , doi = 10.1007/978-3-642-17333-2 , isbn = 978-3-642-17332-5 , location = Heidelberg , mr = 3012380 , page = 59 , publisher = Springer , series = Monographs in Theoretical Computer Science , title = Patterns in permutations and words , url = https://books.google.com/books?id=JgQHtgR5N60C&pg=PA59 , year = 2011 {{citation , last = Albert , first = Michael , contribution = An introduction to structural methods in permutation patterns , doi = 10.1017/CBO9780511902499.008 , mr = 2732828 , pages = 153–170 , publisher = Cambridge Univ. Press, Cambridge , series = London Math. Soc. Lecture Note Ser. , title = Permutation patterns , volume = 376 , year = 2010 {{Citation , last1=Marcus , first1=Adam , last2=Tardos , first2= Gábor , author2-link=Gábor Tardos , title=Excluded permutation matrices and the Stanley-Wilf conjecture , mr = 2063960 , year=2004 , journal=

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, series=Series A , volume=107 , issue=1 , pages=153–160 , doi=10.1016/j.jcta.2004.04.002, doi-access=free . Permutation patterns