Content deleted Content added
Citation bot (talk | contribs) Add: s2cid, doi. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 581/1134 |
|||
| (42 intermediate revisions by 16 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
For instance, permutation π contains the pattern 213 whenever π has three
The permutation 32415 on five elements contains 213 as a pattern in several different ways: 3··15, ··415, 32··5, 324··, and ·2·15 all form triples of If a permutation π does not contain a pattern σ, then π is said to ''avoid'' σ. The permutation 51342 avoids 213; it has 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 12 ⟶ 19:
| place=London
| year=1915
| at = [https://archive.org/details/combinatoryanal01macmuoft/page/124 Volume I, Section III, Chapter V]
}}.</ref> In particular MacMahon shows that the permutations which can be divided into two decreasing subsequences (i.e., the 123-avoiding permutations) are counted by the [[Catalan number]]s.<ref>{{harvtxt|MacMahon|1915}}, Items 97 and 98.</ref>
Line 28 ⟶ 35:
| isbn=0-201-89683-4
| oclc=155842391
| mr= 0286317}}
In his paper, Pratt remarked that this permutation pattern order “seems to be the only partial order on permutation that arises in a simple and natural way” and concludes by noting that “from an abstract point of view”, the permutation pattern order “is even more interesting than the networks we were characterizing”.<ref name="pratt73"/>
Line 34 ⟶ 41:
== Enumerative origins ==
{{main article|Enumerations of specific permutation classes}}
A prominent goal in the study of permutation patterns is in the enumeration of permutations avoiding a fixed (and typically short) permutation or set of permutations. Let Av''
{{harvtxt|Simion|Schmidt|1985}} was the first paper to focus solely on enumeration. Among other results, Simion and Schmidt counted [[Parity of a permutation|even and odd permutations]] avoiding a pattern of length three, counted permutations avoiding [[Enumerations of specific permutation classes#Classes avoiding two patterns of length 3|two patterns of length three]], and gave the first bijective proof that 123- and 231-avoiding permutations are equinumerous.<ref>{{Citation
Line 47 ⟶ 54:
| doi=10.1016/s0195-6698(85)80052-4
| doi-access=free
}}.</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 =
In general, if |Av''
* {{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>
From these two Wilf-equivalences and the inverse and reverse symmetries, it follows that there are three different sequences |Av''
{| class="wikitable" style="text-align:center;" border="1"
|-
! ''β'' !! sequence enumerating Av''
|-
| 1342 || 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ... || {{OEIS link|id=A022558}} || {{harvtxt|Bóna|1997}}<ref>{{citation | last1=Bóna | first1=Miklós | authorlink = Miklós Bóna |title=Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps | mr = 1485138 | year=1997 | journal=[[Journal of Combinatorial Theory]]|series= Series A | volume=80 | issue=2 | pages=257–272 | doi = 10.1006/jcta.1997.2800| arxiv=math/9702223
|-
| 1234 || 1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ... || {{OEIS link|id=A005802}} || {{harvtxt|Gessel|1990}}<ref name="gessel90">{{Citation | last1=Gessel | first1=Ira M. | title=Symmetric functions and ''P''-recursiveness | mr = 1041448 | year=1990 | journal=[[Journal of Combinatorial Theory]]|series= Series A | volume=53 | issue=2 | pages=257–285 | doi = 10.1016/0097-3165(90)90060-A| doi-access=free }}.</ref>
Line 69 ⟶ 76:
|}
In the late 1980s, [[Richard P. Stanley|Richard Stanley]] and [[Herbert Wilf]] conjectured that for every permutation ''β'', there is some constant ''K'' such that |Av''
==
{{main|Permutation class}}
A ''
== Möbius function ==
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>
== Computational complexity ==
Given a permutation <math>\tau</math> (called the ''text'') of length <math>n</math> and another permutation <math>\pi</math> of length <math>k</math> (called the ''pattern''), the ''permutation pattern matching (PPM)'' problem asks whether <math>\pi</math> is contained in <math>\tau</math>. When both <math>n</math> and <math>k</math> are regarded as variables, the problem is known to be [[NP-complete]], and the problem of counting the number of such matches is [[Sharp-P-complete|#P-complete]].<ref name="BBL 1998">{{citation|last1=Bose|first1=Prosenjit|author1-link=Jit Bose|last2=Buss|first2=Jonathan F.|last3=Lubiw|first3=Anna|author3-link=Anna Lubiw|title=Pattern matching for permutations|journal=[[Information Processing Letters]]|date=March 1998|volume=65|issue=5|pages=277–283|doi=10.1016/S0020-0190(97)00209-3}}</ref> However, PPM can be solved in [[linear time]] when ''k'' is a constant. Indeed, Guillemot and Marx<ref>{{cite journal|last=Guillemot|first=Sylvain|author2=Marx, Daniel|title=Finding small patterns in permutations in linear time|journal=Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms|year=2014|page=20|doi=10.1137/1.9781611973402.7|arxiv=1307.3073|isbn=978-1-61197-338-9|s2cid=1846959}}</ref> showed that PPM can be solved in time <math>2^{O(k^2\log k)} \cdot n</math>, meaning that it is [[fixed-parameter tractable]] with respect to <math>k</math>.
There are several variants on the PPM problem, as surveyed by Bruner and Lackner.<ref>{{citation|title=The computational landscape of permutation patterns|first1=Marie-Louise|last1=Bruner|first2=Martin|last2=Lackner|year=2013|journal=Pure Mathematics and Applications|volume=24|issue=2|pages=83–101
Another variant is when both the pattern and text are restricted to a proper permutation class <math>\mathcal{C}</math>, in which case the problem is called <math>\mathcal{C}</math>-PPM. For example, Guillemot and Vialette<ref>{{citation|last1=Guillemot|first1=Sylvain|last2=Vialette|first2=Stéphane|contribution=Pattern matching for 321-avoiding permutations|title=Algorithms and Computation|year=2009|volume=5878|series=Lecture Notes in Computer Science|pages=1064–1073|doi=10.1007/978-3-642-10631-6_107|arxiv=1511.01770|isbn=978-3-642-10630-9 }}</ref> showed that <math>\mbox{Av}(321)</math>-PPM could be solved in <math>O(k^2n^6)</math> time. [[Michael H. Albert|Albert]], Lackner, Lackner, and Vatter<ref>{{citation|last1=Albert|first1=Michael | author1-link=Michael H. Albert |last2=Lackner|first2=Marie-Louise|last3=Lackner|first3=Martin|last4=Vatter|first4=Vincent|year=2016|volume=18|issue=2|journal=Discrete Mathematics & Theoretical Computer Science|title=The complexity of pattern matching for 321-avoiding and skew-merged permutations|doi=10.46298/dmtcs.1308 |arxiv=1510.06051
== Packing densities ==
Line 98 ⟶ 105:
</math>
An unpublished argument of [[Fred Galvin]] shows that the quantity inside this [[limit of a sequence|limit]] is nonincreasing for ''n'' ≥ ''k'', and so the limit exists. When β is monotone, its packing density is clearly 1, and packing densities are invariant under the group of symmetries generated by inverse and reverse, so for permutations of length three, there is only one nontrivial packing density. Walter Stromquist (unpublished) settled this case by showing that the packing density of 132 is {{math|2{{radic|3}} − 3}}, approximately 0.46410.
For permutations β of length four, there are (due to symmetries) seven cases to consider:
Line 108 ⟶ 115:
| 1234 || 1 || trivial
|-
| 1432 || root of {{math|''x''<sup>3</sup> − 12''x''<sup>2</sup> + 156''x'' − 64 ≅ 0.42357}} || {{harvtxt|Price|1997}}<ref name="price97">{{citation | last=Price | first=Alkes | title=Packing densities of layered patterns | publisher=University of Pennsylvania | series = Ph.D. thesis | year=1997 | url=https://www.proquest.com/docview/304421853|id={{ProQuest|304421853}} }}.</ref>
|-
| 2143 ||
|-
| 1243 ||
| 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 122 ⟶ 129:
| journal=[[Electronic Journal of Combinatorics]]
| volume=9
| pages=
| doi=10.37236/1622 | mr = 1887086
| url=http://www.combinatorics.org/Volume_9/Abstracts/v9i1r5.html| doi-access=free}}.</ref>
|-
| 1324 || conjectured to be {{math|≅ 0.244}} ||
|-
| 1342 || conjectured to be {{math|≅ 0.19658}} ||
|-
| 2413 || conjectured to be {{math|≅ 0.10474}} ||
|}
Line 153 ⟶ 160:
| pages=287–316
| doi = 10.1017/CBO9780511902499.015
| isbn=978-0-521-72834-8
}}.</ref>
Line 161 ⟶ 169:
| journal = [[Electronic Journal of Combinatorics]]
| mr = 1710623
| page = Article N1, 4 pp
| title = On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
| url = http://www.combinatorics.org/Volume_6/Abstracts/v6i1n1.html
Line 177 ⟶ 185:
| issue = 1
| pages = 4–24
| arxiv = 1810.08252
}}</ref>
This upper bound is conjectured to be best possible, up to lower-order terms.<ref name="eelw">{{citation
Line 185 ⟶ 194:
| doi = 10.1007/s00026-007-0329-7
| issue = 3–4
| journal = [[Annals of Combinatorics]]
| mr = 2376116
| pages = 459–470
Line 194 ⟶ 203:
==Generalizations==
The type of pattern defined above, in which entries do not need to occur consecutively, is called a ''classical'' (permutation) pattern.
There are several ways in which the notion of "pattern" has been generalized. For example, a ''vincular pattern'' is a permutation containing dashes indicating the entries that need not occur consecutively (in the normal pattern definition, no entries need to occur consecutively). For example, the permutation 314265 has two copies of the dashed pattern 2-31-4, given by the entries 3426 and 3425. For a dashed pattern β and any permutation π, we write β(π) for the number of copies of β in π. Thus the number of inversions in π is 2-1(π), while the number of descents is 21(π). Going further, the number of ''valleys'' in π is 213(π) + 312(π), while the number of ''peaks'' is 231(π) + 132(π). These patterns were introduced by {{harvtxt|Babson|Steingrímsson|2000}}, who showed that almost all known [[Mahonian statistic]]s could be expressed in terms of vincular permutations.<ref>{{citation▼
If the entries are required to be consecutive, then the pattern is called a ''consecutive pattern''.
▲There are several ways in which the notion of "pattern" has been generalized. For example, a ''vincular pattern'' is a permutation containing dashes indicating
| 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 203 ⟶ 216:
| pages=Research article B44b, 18 pp
| mr = 1758852
| url=http://www.emis.de/journals/SLC/wpapers/s44stein.html}}.</ref> For example, the [[Major index]] of π is equal to 1
Another generalization is that of a ''barred pattern'', in which some of the entries are barred. For π to avoid the barred pattern β means that every set of entries of π which form a copy of the nonbarred entries of β can be extended to form a copy of all entries of β. {{harvtxt|West|1993}} introduced these types of patterns in his study of permutations which could be sorted by passing them twice through a stack.<ref>{{Citation | last1=West | first1=Julian | title=Sorting twice through a stack| mr = 1235186| year=1993 | journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]| volume=117 | issue=1–2 | pages=303–313| doi = 10.1016/0304-3975(93)90321-J| doi-access=free}}.</ref> (Note that West's definition of sorting twice through a stack is not the same as sorting with two stacks in series.) Another example of barred patterns occurs in the work of {{harvtxt|Bousquet-Mélou|Butler|2007}}, who showed that the [[Schubert variety]] corresponding to π is [[Schubert variety#Locally factorial|locally factorial]] if and only if π avoids 1324 and 21<span style="text-decoration: overline;">3</span>54.<ref>{{Citation
Line 210 ⟶ 223:
| title=Forest-like permutations
| year=2007
| journal=[[Annals of Combinatorics]]
| volume=11
| issue=3–4 | pages=335–354
Line 221 ⟶ 234:
==External links==
{{Commonscat|Permutation patterns}}
* [
▲* [http://www.cs.otago.ac.nz/PermLab PermLab: software for permutation patterns], maintained by [[Michael H. Albert|Michael Albert]].
* [https://permpal.com/ PermPAL: The Permutation Pattern Avoidance Library], a database of algorithmically-derived theorems about permutation classes, maintained by Christian Bean, Émile Nadeau, Jay Pantone and Henning Ulfarsson.
| |||