Content deleted Content added
Vince Vatter (talk | contribs) m →Closed classes: terminology |
|||
| (6 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|Subpermutation of a longer permutation}}
In [[combinatorics|combinatorial mathematics]] and [[theoretical computer science]], a (classical) '''permutation pattern''' is a sub-permutation of a longer [[permutation]]. Any permutation may be written in [[Permutation#One-line_notation|one-line notation]] as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way (these variable names are standard for permutations and are unrelated to the number [[pi]]), then π is said to ''contain'' σ as a ''pattern'' if some [[subsequence]] of the entries of π has the same relative order as all of the entries of σ.
Line 6 ⟶ 7:
If a permutation π does not contain a pattern σ, then π is said to ''avoid'' σ. The permutation 51342 avoids 213; it has ten subsequences of three entries, but none of these ten subsequences has the same ordering as 213.
An international conference dedicated to permutation patterns and related topics has been held annually since 2003, called ''[[Permutation Patterns (conference) | Permutation Patterns]]''.
== Early results ==
Line 53 ⟶ 56:
}}.</ref> Since their paper, many other bijections have been given, see {{harvtxt|Claesson|Kitaev|2008}} for a survey.<ref>{{Citation| last1=Claesson | first1=Anders| last2=Kitaev | first2=Sergey| author2-link = Sergey Kitaev| arxiv = 0805.1325| title=Classification of bijections between 321- and 132-avoiding permutations| year=2008| journal=[[Séminaire Lotharingien de Combinatoire]]| url = https://www.mat.univie.ac.at/~slc/wpapers/s60claekit.html| volume=60| pages=B60d, 30pp| mr = 2465405}}.</ref>
In general, if |Av''<sub>n</sub>''(''β'')| = |Av''<sub>n</sub>''(''σ'')| for all ''n'', then ''β'' and ''σ'' are said to be [[Wilf equivalence|''Wilf-equivalent'']]. Many Wilf-equivalences stem from the trivial fact that |Av''<sub>n</sub>''(''β'')| = |Av''<sub>n</sub>''(''β''<sup>−1</sup>)| = |Av''<sub>n</sub>''(''β''<sup>rev</sup>)| for all ''n'', where ''β''<sup>−1</sup> denotes the [[Permutation#Product and inverse|inverse]] of ''β'' and ''β''<sup>rev</sup> denotes the reverse of ''β''. (These two operations generate the [[Examples of groups#The symmetry group of a square - dihedral group of order 8|Dihedral group D<sub>8</sub>]] with a natural action on [[permutation matrices]].) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between
* {{harvtxt|Stankova|1994}} proved that the permutations 1342 and 2413 are Wilf-equivalent.<ref>{{Citation | last1=Stankova | first1=Zvezdelina | title=Forbidden subsequences | mr = 1297387 | year=1994 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] | volume=132 | issue=1–3 | pages=291–316 | doi = 10.1016/0012-365X(94)90242-9| doi-access=free }}.</ref>
* {{harvtxt|Stankova|West|2002}} proved that for any permutation ''β'', the permutations 231 ⊕ ''β'' and 312 ⊕ ''β'' are Wilf-equivalent, where ⊕ denotes the [[direct sum of permutations|direct sum]] operation.<ref>{{Citation | last1=Stankova | first1=Zvezdelina | last2=West | first2=Julian | title=A New class of Wilf-Equivalent Permutations | mr = 1900628 | year=2002 | journal=[[Journal of Algebraic Combinatorics]] | volume=15 | issue=3 | pages=271–290 | doi = 10.1023/A:1015016625432| arxiv=math/0103152 | s2cid=13921676 }}.</ref>
* {{harvtxt|Backelin|West|Xin|2007}} proved that for any permutation ''β'' and any positive integer ''m'', the permutations 12...''m'' ⊕ ''β'' and ''m''...21 ⊕ ''β'' are Wilf-equivalent.<ref>{{citation | last1=Backelin | first1=Jörgen | last2=West | first2=Julian | last3=Xin | first3=Guoce | title=Wilf-equivalence for singleton classes
| mr = 2290807 | year=2007 | journal=[[Advances in Applied Mathematics]] | volume=38 | issue=2 | pages=133–149 | doi = 10.1016/j.aam.2004.11.006| doi-access=free }}.</ref>
Line 82 ⟶ 85:
As the set of permutations under the containment order forms a [[Partially ordered set|poset]] it is natural to ask about its [[incidence algebra#Special elements|Möbius function]], a goal first explicitly presented by {{harvtxt|Wilf|2002}}.<ref>{{citation | last1=Wilf | first1=Herbert | authorlink = Herbert Wilf |title=Patterns of permutations | mr = 1935750 | year=2002 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]| volume=257 | issue=2 | pages=575–583 | doi = 10.1016/S0012-365X(02)00515-0| doi-access=free }}.</ref>
The goal in such investigations is to find a formula for the Möbius function of an interval [σ, π] in the permutation pattern poset which is more efficient than the naïve recursive definition. The first such result was established by {{harvtxt|Sagan|Vatter|2006}}, who gave a formula for the Möbius function of an interval of [[layered permutation]]s.<ref>{{Citation | last1=Sagan | first1=Bruce | author1-link=Bruce Sagan | last2=Vatter | first2= Vince | title=The Möbius function of a composition poset | mr = 2259013 | year=2006 | journal=[[Journal of Algebraic Combinatorics]] | volume=24 | issue=2 | pages=117–136 | doi=10.1007/s10801-006-0017-4| arxiv=math/0507485 | s2cid=11283347 }}.</ref>
Later, {{harvtxt|Burstein|Jelinek|Jelinkova|Steingrimsson|2011}} generalized this result to intervals of [[separable permutation]]s.<ref>{{Citation | last1=Burstein | first1=Alexander | last2=Jelinek | first2= Vit | last3=Jelinkova | first3=Eva | last4=Steingrimsson | first4= Einar |author4-link=Einar Steingrímsson|title=The Möbius function of separable and decomposable permutations | mr = 2834180 | year=2011 | journal=[[Journal of Combinatorial Theory]]|series=Series A | volume=118 | issue=1 | pages=2346–2364 | doi=10.1016/j.jcta.2011.06.002| s2cid=13978488 | doi-access=free }}.</ref>
It is known that, asymptotically, at least 39.95% of all permutations π of length ''n'' satisfy μ(1, π)=0 (that is, the principal Möbius function is equal to zero),<ref>{{citation |last1=Brignall |first1=Robert |last2=Jelínek |first2=Vit |last3=Kynčl |first3=Jan |last4=Marchant |first4=David |title=Zeros of the Möbius function of permutations | year=2019 | journal=[[Mathematika]] |volume=65 |issue=4 |pages=1074–1092 | mr=3992365 | doi=10.1112/S0025579319000251|s2cid=53366318 |url=http://oro.open.ac.uk/66369/1/181012-Marchant-v101.pdf |arxiv=1810.05449 }}</ref> but for each ''n'' there exist permutations π such that μ(1, π) is an exponential function of ''n''.<ref>{{citation |last1=Marchant |first1=David |title=2413-balloon permutations and the growth of the Möbius function |journal=[[Electronic Journal of Combinatorics]] |date=2020 |volume=27 |issue=1 |page=Article P1.7, 18 pp |doi=10.37236/8554|doi-access=free |arxiv=1812.05064 }}</ref>
Line 118 ⟶ 121:
| 1243 || {{math|1={{sfrac|3|8}} = 0.375}} || {{harvtxt|Albert|Atkinson|Handley|Holton|2002}}<ref>{{Citation
| last1=Albert | first1=Michael H. | author1-link=Michael H. Albert
| last2=Atkinson | first2=M. D. | author2-link=Michael D. Atkinson
| last3=Handley | first3=C. C.
| last4=Holton | first4=D. A.
Line 206 ⟶ 209:
| last1=Babson | first1=Erik
| last2= Steingrímsson | first2=Einar
| author2-link = Einar Steingrímsson
| title=Generalized permutation patterns and a classification of the Mahonian statistics
| year=2000
Line 230 ⟶ 234:
==External links==
{{Commonscat|Permutation patterns}}
* [https://www.cs.otago.ac.nz/staffpriv/malbert/permlab.php PermLab: software for permutation patterns], maintained by [[Michael H. Albert|Michael Albert]].
* [http://math.depaul.edu/~bridget/patterns.html Database of Permutation Pattern Avoidance], maintained by [[Bridget Tenner]].
| |||