In
combinatorial mathematics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
and
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
, a permutation pattern is a sub-permutation of a longer
permutation. Any permutation may be written in
one-line notation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit 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 digits of π has the same relative order as all of the digits of σ.
For instance, permutation π contains the pattern 213 whenever π has three digits ''x'', ''y'', and ''z'' that appear within π in the order ''x''...''y''...''z'' but whose values are ordered as ''y'' < ''x'' < ''z'', the same as the ordering of the values in the permutation 213. 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 digits with the same ordering as 213. Each of the subsequences 315, 415, 325, 324, and 215 is called a ''copy,'' ''instance,'' or ''occurrence'' of the pattern. The fact that π contains σ is written more concisely as σ ≤ π. If a permutation π does not contain a pattern σ, then π is said to ''avoid'' σ. The permutation 51342 avoids 213; it has 10 subsequences of three digits, but none of these 10 subsequences has the same ordering as 213.
Early results
A case can be made that was the first to prove a result in the field with his study of "lattice permutations". 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
In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Ca ...
s.
Another early landmark result in the field is the
Erdős–Szekeres theorem
In mathematics, the Erdős–Szekeres theorem asserts that, given ''r'', ''s,'' any sequence of distinct real numbers with length at least (''r'' − 1)(''s'' − 1) + 1 contains a monotonically increasing su ...
; in permutation pattern language, the theorem states that for any positive integers ''a'' and ''b'' every permutation of length at least
must contain either the pattern
or the pattern
.
Computer science origins
The study of permutation patterns began in earnest with
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
's consideration of
stack-sorting in 1968. Knuth showed that the permutation π can be sorted by a
stack if and only if π avoids 231, and that the stack-sortable permutations are enumerated by the
Catalan number
In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Ca ...
s. Knuth also raised questions about sorting with
deques. In particular, Knuth's question asking how many permutation of ''n'' elements are obtainable with the use of a deque remains open. Shortly thereafter, investigated sorting by networks of stacks, while showed that the permutation π can be sorted by a deque if and only if for all ''k'', π avoids 5,2,7,4,...,4''k''+1,4''k''−2,3,4''k'',1, and 5,2,7,4,...,4''k''+3,4''k'',1,4''k''+2,3, and every permutation that can be obtained from either of these by interchanging the last two elements or the 1 and the 2.
[.] Because this collection of permutations is infinite (in fact, it is the first published example of an infinite
antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.
The size of the largest antichain in a partially ordered set is known as its wid ...
of permutations), it is not immediately clear how long it takes to decide if a permutation can be sorted by a deque. later presented a linear (in the length of π) time algorithm which determines if π can be sorted by a deque.
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”.
Enumerative origins
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
n''(B) denote the set of permutations of length ''n'' which avoid all of the permutations in the set ''B'' (in the case ''B'' is a singleton, say ''β'', the abbreviation ''Av
n''(''β'') is used instead). As noted above, MacMahon and Knuth showed that , ''Av
n''(123), = , ''Av
n''(231), = ''C
n'', the ''n''th Catalan number. Thus these are isomorphic
combinatorial class In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size.
Counting sequences and isomorphis ...
es.
was the first paper to focus solely on enumeration. Among other results, Simion and Schmidt counted
even and odd permutations
In mathematics, when ''X'' is a finite set with at least two elements, the permutations of ''X'' (i.e. the bijective functions from ''X'' to ''X'') fall into two classes of equal size: the even permutations and the odd permutations. If any total ...
avoiding a pattern of length three, counted permutations avoiding
two patterns of length three, and gave the first bijective proof that 123- and 231-avoiding permutations are equinumerous. Since their paper, many other bijections have been given, see for a survey.
In general, if , ''Av
n''(''β''), = , ''Av
n''(''σ''), for all ''n'', then ''β'' and ''σ'' are said to be
''Wilf-equivalent''. Many Wilf-equivalences stem from the trivial fact that , ''Av
n''(''β''), = , ''Av
n''(''β''
−1), = , ''Av
n''(''β''
rev), for all ''n'', where ''β''
−1 denotes the
inverse of ''β'' and ''β''
rev denotes the reverse of ''β''. (These two operations generate the
Dihedral group D8 with a natural action on
permutation matrices
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when ...
.) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between ''123'' and ''231''):
* proved that the permutations 1342 and 2413 are Wilf-equivalent.
* proved that for any permutation ''β'', the permutations 231 ⊕ ''β'' and 312 ⊕ ''β'' are Wilf-equivalent, where ⊕ denotes the
direct sum operation.
* proved that for any permutation ''β'' and any positive integer ''m'', the permutations 12..''m'' ⊕ ''β'' and ''m''...21 ⊕ ''β'' are Wilf-equivalent.
From these two Wilf-equivalences and the inverse and reverse symmetries, it follows that there are three different sequences , ''Av
n''(''β''), where ''β'' is of length four:
In the late 1980s,
Richard Stanley and
Herbert Wilf
Herbert Saul Wilf (June 13, 1931 – January 7, 2012) was a mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professor of Mathematics in Combinatorial Analysis and Computing at the University of Pennsylv ...
conjectured that for every permutation ''β'', there is some constant ''K'' such that , ''Av
n''(''β''), < ''K
n''. This was known as the
Stanley–Wilf conjecture until it was proved by
Adam Marcus and
Gábor Tardos
Gábor Tardos (born 11 July 1964) is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science. He is ...
.
Closed classes
A ''closed class'', also known as a ''pattern class'', ''permutation class'', or simply ''class'' of permutations is a
downset
Downset may refer to:
* Downset lattice
* Down set
* Downset., an American rap metal band
*'' downset.'', the 1994 self-titled debut studio album
*" Downset", the title track of the self-titled 1994 album by downset.
{{disambiguation ...
in the permutation pattern order. Every class can be defined by the minimal permutations which do not lie inside it, its ''basis''. Thus the basis for the stack-sortable permutations is , while the basis for the deque-sortable permutations is infinite. The ''generating function'' for a class is Σ x
, π, where the sum is taken over all permutations π in the class.
Möbius function
As the set of permutations under the containment order forms a
poset
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
it is natural to ask about its
Möbius function
The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most of ...
, a goal first explicitly presented by .
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 , who gave a formula for the Möbius function of an interval of
layered permutations.
Later, generalized this result to intervals of
separable permutation
In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3 ...
s.
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), but for each ''n'' there exist permutations π such that μ(1, π) is an exponential function of ''n''.
Computational complexity
Given a permutation
(called the ''text'') of length
and another permutation
of length
(called the ''pattern''), the ''permutation pattern matching (PPM)'' problem asks whether
is contained in
. When both
and
are regarded as variables, the problem is known to be
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
, and the problem of counting the number of such matches is
#P-complete. However, PPM can be solved in
linear time when ''k'' is a constant. Indeed, Guillemot and Marx showed that PPM can be solved in time
, meaning that it is
fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
with respect to
.
There are several variants on the PPM problem, as surveyed by Bruner and Lackner. For example, if the match is required to consist of contiguous entries then the problem can be solved in polynomial time.
Another variant is when both the pattern and text are restricted to a proper permutation class
, in which case the problem is called
-PPM. For example, Guillemot and Vialette showed that
-PPM could be solved in
time.
Albert
Albert may refer to:
Companies
* Albert (supermarket), a supermarket chain in the Czech Republic
* Albert Heijn, a supermarket chain in the Netherlands
* Albert Market, a street market in The Gambia
* Albert Productions, a record label
* Alber ...
, Lackner, Lackner, and Vatter later lowered this to
and showed that the same bound holds for the class of
skew-merged permutation In the theory of permutation patterns, a skew-merged permutation is a permutation that can be partitioned into an increasing sequence and a decreasing sequence. They were first studied by and given their name by .
Characterization
The two smalles ...
s. They further asked if the
-PPM problem can be solved in polynomial time for every fixed proper permutation class
.
Packing densities
The permutation π is said to be β-''optimal'' if no permutation of the same length as π has more copies of β. In his address to the SIAM meeting on Discrete Mathematics in 1992, Wilf defined the ''packing density'' of the permutation β of length ''k'' as
:
An unpublished argument of
Fred Galvin
Frederick William Galvin is a mathematician, currently a professor at the University of Kansas. His research interests include set theory and combinatorics.
His notable combinatorial work includes the proof of the Dinitz conjecture. In set theory, ...
shows that the quantity inside this
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
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 2 − 3, approximately 0.46410.
For permutations β of length four, there are (due to symmetries) seven cases to consider:
For the three unknown permutations, there are bounds and conjectures. used an approximation algorithm which suggests that the packing density of 1324 is around 0.244.
Birzhan Batkeyev (unpublished) constructed a family of permutations showing that the packing density of 1342 is at least the product of the packing densities of 132 and 1432, approximately 0.19658. This is conjectured to be the precise packing density of 1342. provided a lower bound on the packing density of 2413. This lower bound, which can be expressed in terms of an integral, is approximately 0.10474, and conjectured to be the true packing density.
Superpatterns
A ''k''-superpattern is a permutation that contains all permutations of length ''k''. For example, 25314 is a 3-superpattern because it contains all 6 permutations of length 3. It is known that ''k''-superpatterns must have length at least ''k''
2/''e''
2, where ''e'' ≈ 2.71828 is
Euler's number
The number , also known as Euler's number, is a mathematical constant approximately equal to 2.71828 that can be characterized in many ways. It is the base of the natural logarithms. It is the limit of as approaches infinity, an expressi ...
, and that there exist ''k''-superpatterns of length ⌈(''k''
2 + 1)/2⌉.
This upper bound is conjectured to be best possible, up to lower-order terms.
[.]
Generalizations
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 , who showed that almost all known
Mahonian statistics could be expressed in terms of vincular permutations. For example, the
Major index In mathematics (and particularly in combinatorics), the major index of a permutation is the sum of the positions of the descents of the permutation. In symbols, the major index of the permutation ''w'' is
:
\operatorname(w) = \sum_ i.
For e ...
of π is equal to 1-32(π) + 2-31(π) + 3-21(π) + 21(π).
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 β. introduced these types of patterns in his study of permutations which could be sorted by passing them twice through a stack. (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 , who showed that the
Schubert variety In algebraic geometry, a Schubert variety is a certain subvariety of a Grassmannian, usually with singular points. Like a Grassmannian, it is a kind of moduli space, whose points correspond to certain kinds of subspaces ''V'', specified using line ...
corresponding to π is
locally factorial if and only if π avoids 1324 and 21
354.
[.]
References
External links
{{Commonscat, Permutation patterns
A conference on permutation patterns has bee
held annually since 2003
Permutation Patterns 2003 February 10–14, 2003,
University of Otago
, image_name = University of Otago Registry Building2.jpg
, image_size =
, caption = University clock tower
, motto = la, Sapere aude
, mottoeng = Dare to be wise
, established = 1869; 152 years ago
, type = Public research collegiate ...
, Dunedin, New Zealand.
Permutation Patterns 2004 July 5–9, 2004,
Malaspina University-College
Vancouver Island University (abbreviated as VIU, formerly known as Malaspina University-College and earlier as Malaspina College) is a Canadian public university serving Vancouver Island and coastal British Columbia. Malaspina College began in 196 ...
, Nanaimo, British Columbia, Canada.
Permutation Patterns 2005 March 7–11, 2005,
University of Florida
The University of Florida (Florida or UF) is a public land-grant research university in Gainesville, Florida. It is a senior member of the State University System of Florida, traces its origins to 1853, and has operated continuously on its ...
, Gainesville, Florida, USA.
Permutation Patterns 2006 June 12–16, 2006,
Reykjavík University
Reykjavík University (RU; is, Háskólinn í Reykjavík) is the largest private university in Iceland with approximately 3,300 students (October 2020). It is chartered by the Chamber of Commerce, the Federation of Icelandic Industries, and the ...
, Reykjavík, Iceland.
Permutation Patterns 2007 June 11–15, 2007,
University of St. Andrews
(Aien aristeuein)
, motto_lang = grc
, mottoeng = Ever to ExcelorEver to be the Best
, established =
, type = Public research university
Ancient university
, endowment ...
, St. Andrews, Scotland.
Permutation Patterns 2008 June 16–20, 2008,
University of Otago
, image_name = University of Otago Registry Building2.jpg
, image_size =
, caption = University clock tower
, motto = la, Sapere aude
, mottoeng = Dare to be wise
, established = 1869; 152 years ago
, type = Public research collegiate ...
, Dunedin, New Zealand.
Permutation Patterns 2009 July 13–17, 2009,
Università di Firenze
The University of Florence (Italian: ''Università degli Studi di Firenze'', UniFI) is an Italian public research university located in Florence, Italy. It comprises 12 schools and has around 50,000 students enrolled.
History
The first universi ...
, Florence, Italy.
Permutation Patterns 2010 August 9–13, 2010,
Dartmouth College
Dartmouth College (; ) is a private research university in Hanover, New Hampshire. Established in 1769 by Eleazar Wheelock, it is one of the nine colonial colleges chartered before the American Revolution. Although founded to educate Native ...
, Hanover, New Hampshire, USA.
Permutation Patterns 2011 June 20–24, 2011,
California Polytechnic State University, San Luis Obispo, California, USA.
Permutation Patterns 2012 June 11–15, 2012,
University of Strathclyde
The University of Strathclyde ( gd, Oilthigh Shrath Chluaidh) is a public research university located in Glasgow, Scotland. Founded in 1796 as the Andersonian Institute, it is Glasgow's second-oldest university, having received its royal chart ...
, Glasgow, Scotland.
Permutation Patterns 2013 July 1–5, 2013,
Université Paris Diderot
Paris Diderot University, also known as Paris 7 (french: Université Paris Diderot), was a French university located in Paris, France. It was one of the inheritors of the historic University of Paris, which was split into 13 universities in 197 ...
, Paris, France.
Permutation Patterns 2014 July 7–11, 2014,
East Tennessee State University
East Tennessee State University (ETSU) is a public research university in Johnson City, Tennessee. Although it is part of the State University and Community College System of Tennessee, the university is governed by an institutional Board of Tr ...
, Johnson City, Tennessee, USA.
Permutation Patterns 2015 June 15–19, 2015
De Morgan House London, England.
Permutation Patterns 2016 June 27–July 1, 2016,
Howard University
Howard University (Howard) is a Private university, private, University charter#Federal, federally chartered historically black research university in Washington, D.C. It is Carnegie Classification of Institutions of Higher Education, classifie ...
, Washington, DC, USA.
Permutation Patterns 2017 June 26–30, 2017,
Reykjavík University
Reykjavík University (RU; is, Háskólinn í Reykjavík) is the largest private university in Iceland with approximately 3,300 students (October 2020). It is chartered by the Chamber of Commerce, the Federation of Icelandic Industries, and the ...
, Reykjavík, Iceland.
Permutation Patterns 2018 July 9–13, 2018,
Dartmouth College
Dartmouth College (; ) is a private research university in Hanover, New Hampshire. Established in 1769 by Eleazar Wheelock, it is one of the nine colonial colleges chartered before the American Revolution. Although founded to educate Native ...
, Hanover, New Hampshire, USA.
Permutation Patterns 2019 June 17–21, 2019,
Universität Zürich
The University of Zürich (UZH, german: Universität Zürich) is a public research university located in the city of Zürich, Switzerland. It is the largest university in Switzerland, with its 28,000 enrolled students. It was founded in 1833 f ...
, Zürich, Switzerland.
Permutation Patterns 2020 Virtual Workshop June 30–July 1, 2020, hosted by
Valparaiso University
Valparaiso University (Valpo) is a private university in Valparaiso, Indiana. It is a Lutheran university with about 3,000 students from over 50 countries on a campus of . Originally named Valparaiso Male and Female College, Valparaiso Universit ...
, Valparaiso, Indiana, USA.
Permutation Patterns 2021 Virtual Workshop June 15–16, 2021, hosted by
University of Strathclyde
The University of Strathclyde ( gd, Oilthigh Shrath Chluaidh) is a public research university located in Glasgow, Scotland. Founded in 1796 as the Andersonian Institute, it is Glasgow's second-oldest university, having received its royal chart ...
, Glasgow, Scotland.
Permutation Patterns 2022 June 20-24, 2022,
Valparaiso University
Valparaiso University (Valpo) is a private university in Valparaiso, Indiana. It is a Lutheran university with about 3,000 students from over 50 countries on a campus of . Originally named Valparaiso Male and Female College, Valparaiso Universit ...
, Valparaiso, Indiana, USA.
Permutation Patterns 2023 July 3-7, 2023,
University of Burgundy
The University of Burgundy (french: Université de Bourgogne, uB; formerly known as ''Université de Dijon'') is a public university located in Dijon, France.
The University of Burgundy is situated on a large campus (more than 150 ha) in the east ...
, Dijon, France.
American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
Special Sessions on Patterns in Permutations have been held at the following meetings:
Fall Eastern Sectional Meeting September 22–23, 2012,
Rochester Institute of Technology
Rochester Institute of Technology (RIT) is a private research university in the town of Henrietta in the Rochester, New York, metropolitan area. The university offers undergraduate and graduate degrees, including doctoral and professional ...
, Rochester, NY.
Joint Mathematics Meetings January 12, 2013, San Diego, CA.
September 20–21, 2014,
University of Wisconsin-Eau Claire
A university () is an institution of higher (or tertiary) education and research which awards academic degrees in several academic disciplines. Universities typically offer both undergraduate and postgraduate programs. In the United States, the ...
, Eau Claire, WI.
Spring Eastern Sectional Meeting March 7–8, 2015,
Georgetown University
Georgetown University is a private university, private research university in the Georgetown (Washington, D.C.), Georgetown neighborhood of Washington, D.C. Founded by Bishop John Carroll (archbishop of Baltimore), John Carroll in 1789 as Georg ...
, Washington, DC.
Other permutation patterns meetings:
Workshop on Permutation Patterns May 29–June 3, 2005,
University of Haifa
The University of Haifa ( he, אוניברסיטת חיפה Arabic: جامعة حيفا) is a university located on Mount Carmel in Haifa, Israel. Founded in 1963, the University of Haifa received full academic accreditation in 1972, becoming ...
, Haifa, Israel.
Pattern Avoidance and Genome Sorting February 14-19, 2016,
Schloss Dagstuhl, Wadern, Germany.
Genomics, Pattern Avoidance, and Statistical Mechanics November 4-9, 2018,
Schloss Dagstuhl, Wadern, Germany.
Pattern Avoidance, Statistical Mechanics and Computational Complexity March 19-24, 2023,
Schloss Dagstuhl, Wadern, Germany.
Other links:
PermLab: software for permutation patterns maintained by
Michael Albert
Michael Albert (born April 8, 1947) is an American economist, speaker, writer, and political critic. Since the late 1970s, he has published books, articles, and other contributions on a wide array of subjects. He has also set up his own media ...
.
Database of Permutation Pattern Avoidance maintained by Bridget Tenner.
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.