Jump to content

Wilf equivalence

From Wikipedia, the free encyclopedia
(Redirected from Wilf class)

In the study of permutations and permutation patterns, Wilf equivalence is an equivalence relation 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 functions.[1] The equivalence classes for Wilf equivalence are called Wilf classes;[2] 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.[1]

References

[edit]
  1. ^ a b Bevan, David (2015), Permutation patterns: basic definitions and notation, arXiv:1506.06673, Bibcode:2015arXiv150606673B
  2. ^ Steingrímsson, Einar (2013), "Some open problems on permutation patterns", Surveys in combinatorics 2013, London Math. Soc. Lecture Note Ser., vol. 409, Cambridge Univ. Press, Cambridge, pp. 239–263, MR 3156932