HOME

TheInfoList



OR:

In combinatorial mathematics and
theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, a (classical) permutation pattern is a sub-permutation of a longer
permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...
. Any permutation may be written in
one-line notation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first meanin ...
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 In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a ...
of the entries of π has the same relative order as all of the entries of σ. For instance, permutation π contains the pattern 213 whenever π has three entries ''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 entries with the same ordering as 213. Note that the entries do not need to be consecutive. 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 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''.


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 The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...
s. Another early landmark result in the field is the Erdős–Szekeres theorem; in permutation pattern language, the theorem states that for any positive integers ''a'' and ''b'' every permutation of length at least (a-1)(b-1) + 1 must contain either the pattern 1, 2, 3,\dots , a or the pattern b,b-1,\dots , 2, 1.


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 and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
's consideration of stack-sorting in 1968. Knuth showed that the permutation π can be sorted by a
stack Stack may refer to: Places * Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group * Blue Stack Mountains, in Co. Donegal, Ireland People * Stack (surname) (including a list of people ...
if and only if π avoids 231, and that the stack-sortable permutations are enumerated by the
Catalan number The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...
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 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), = ''Cn'', the ''n''th Catalan number. Thus these are isomorphic combinatorial classes. 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 tota ...
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 (mathematics), matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permu ...
.) 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 The direct sum is an operation between structures in abstract algebra, a branch of mathematics. It is defined differently but analogously for different kinds of structures. As an example, the direct sum of two abelian groups A and B is anothe ...
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 conjectured that for every permutation ''β'', there is some constant ''K'' such that , Av''n''(''β''), < ''Kn''. This was known as the Stanley–Wilf conjecture until it was proved by Adam Marcus and Gábor Tardos.


Permutation classes

A ''permutation class'', also known as a ''pattern class'' (mostly in older work), or simply a ''class'' of permutations is a
downset Downset may refer to: *Downset lattice *Down set *Downset., an American rap metal band *''Downset. (album), downset.'', the 1994 self-titled debut studio album *"Downset (song), Downset", the title track of the Downset. (album), self-titled 1994 al ...
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 known to be 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 partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
it is natural to ask about its
Möbius function The Möbius function \mu(n) 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 m ...
, 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 combinatorics, combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by Direct sum of permutations, direct sums and Skew sum of permutations, skew sums. Separable permutations may ...
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 \tau (called the ''text'') of length n and another permutation \pi of length k (called the ''pattern''), the ''permutation pattern matching (PPM)'' problem asks whether \pi is contained in \tau. When both n and k are regarded as variables, the problem is known to be
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
, and the problem of counting the number of such matches is #P-complete. However, PPM can be solved in
linear time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
when ''k'' is a constant. Indeed, Guillemot and Marx showed that PPM can be solved in time 2^ \cdot n, meaning that it is fixed-parameter tractable with respect to k. 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. A different natural variant is obtained when the pattern is restricted to a proper permutation class \mathcal. This problem is known as \mathcal-Pattern PPM and it was shown to be polynomial-time solvable for separable permutations. Later, Jelínek and Kynčl completely resolved the complexity of \mbox(\sigma)-Pattern PPM by showing that it is polynomial-time solvable when \sigma is equal to one of 1, 12, 21, 132, 231, 312 or 213 and NP-complete otherwise. Another variant is when both the pattern and text are restricted to a proper permutation class \mathcal, in which case the problem is called \mathcal-PPM. For example, Guillemot and Vialette showed that \mbox(321)-PPM could be solved in O(k^2n^6) time. Albert, Lackner, Lackner, and Vatter later lowered this to O(kn) and showed that the same bound holds for the class of skew-merged permutations. They further asked if the \mathcal-PPM problem can be solved in polynomial time for every fixed proper permutation class \mathcal. This question was answered negatively by Jelínek and Kynčl who showed that \mbox(4321)-PPM is in fact NP-complete. Later, Jelínek, Opler, and Pekárek showed that \mbox(\sigma)-PPM is NP-complete for any \sigma of length at least 4 not symmetric to one of 3412, 3142, 4213, 4123 or 41352.


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 : \lim_ \frac. An unpublished argument of Fred Galvin shows that the quantity inside this 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 , 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 is a mathematical constant approximately equal to 2.71828 that is the base of the natural logarithm and exponential function. It is sometimes called Euler's number, after the Swiss mathematician Leonhard Euler, though this can ...
, 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

The type of pattern defined above, in which entries do not need to occur consecutively, is called a ''classical'' (permutation) pattern. 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 which adjacent pairs of entries need not 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 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 corresponding to π is locally factorial if and only if π avoids 1324 and 21354..


References


External links

{{Commonscat, Permutation patterns
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 on a variety of subjects. He has set up his own media outfits, magazines, and podcasts. He is known for ...
.
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.