Wilf equivalence

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
  1. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.