In the study of

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

s and

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

s, 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. A simpler example is equ ...

on permutation classes. Two permutation classes are Wilf equivalent when they have the same numbers of permutations of each possible length, or equivalently if they have the same

generating function In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...

s. The equivalence classes for Wilf equivalence are called Wilf classes; they are the combinatorial classes of permutation classes. The counting functions and Wilf equivalences among many specific permutation classes are known. Wilf equivalence may also be described for individual permutations rather than permutation classes. In this context, two permutations are said to be Wilf equivalent if the principal permutation classes formed by forbidding them are Wilf equivalent.

References

{{reflist, refs= {{citation , last = Bevan , first = David , author-link=David Bevan (mathematician) , arxiv = 1506.06673 , title = Permutation patterns: basic definitions and notation , year = 2015, bibcode = 2015arXiv150606673B {{citation , last = Steingrímsson , first = Einar , author-link = Einar Steingrímsson , contribution = Some open problems on permutation patterns , mr = 3156932 , pages = 239–263 , publisher = Cambridge Univ. Press, Cambridge , series = London Math. Soc. Lecture Note Ser. , title = Surveys in combinatorics 2013 , volume = 409 , year = 2013 Enumerative combinatorics Permutation patterns Equivalence (mathematics)