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 proc ...

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 pe ...

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. Each equivalence relation ...

permutation class In the study of permutations and permutation patterns, 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 of permutations, or a ...

es. 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 way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...

s. The equivalence classes for Wilf equivalence 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 isomorphis ...

es 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 , arxiv = 1506.06673 , title = Permutation patterns: basic definitions and notation , year = 2015, bibcode = 2015arXiv150606673B {{citation , last = Steingrímsson , first = Einar , 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)