Content deleted Content added
Vince Vatter (talk | contribs) m wikified Atkinson as he now has a page |
|||
| (4 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 55 ⟶ 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 84 ⟶ 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 208 ⟶ 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
| |||