Permutation pattern

In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. A permutation π of length n is written as a word in one-line notation (i.e., in two-line notation with the first line omitted) as π = π1π2…πn, where πi is the ith number in the word. For example, in the permutation π = 391867452, π1=3 and π9=2. A permutation π is said to contain the permutation σ if there exists a subsequence of (not necessarily consecutive) entries of π that has the same relative order as σ, and in this case σ is said to be a pattern of π, written σ ≤ π. Otherwise, π is said to avoid the permutation σ. For example, the permutation π = 391867452 contains the pattern σ = 51342, as can be seen in the highlighted subsequence of π = 391867452 (or π = 391867452 or π = 391867452). Each subsequence (91674, 91675, 91672) is called a copy, instance, or occurrence of σ. Since the permutation π = 391867452 contains no increasing subsequence of length four, π avoids 1234.

Early results

A case can be made that Percy MacMahon (1915) was the first to prove a result in the field with his study of "lattice permutations".[1] 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 numbers.[2]

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 ab + 1 must contain either the pattern 1, 2, 3, ..., a + 1 or the pattern b + 1, b, ..., 2, 1.

Computer science origins

The study of permutation patterns began in earnest with Donald Knuth's consideration of stack-sorting in 1968.[3] 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 numbers.[4] 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.[5] Shortly thereafter, Robert Tarjan (1972) investigated sorting by networks of stacks,[6] while Vaughan Pratt (1973) showed that the permutation π can be sorted by a deque if and only if for all k, π avoids 5,2,7,4,...,4k+1,4k−2,3,4k,1, and 5,2,7,4,...,4k+3,4k,1,4k+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.[7] 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. Rosenstiehl & Tarjan (1984) later presented a linear (in the length of π) time algorithm which determines if π can be sorted by a deque.[8]

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”.[7]

Enumerative origins

Many problems in the study of permutation patterns are pursued using the tools of the field of enumerative combinatorics. Two central problems are Wilf-equivalence and the Stanley-Wilf conjecture.

Wilf-equivalence

One central problem in pattern avoidance that has been studied in the last 40 years is that of determining the number of permutations of length n which avoid a fixed permutation β. Let Avn(β) denote the set of permutations of length n which avoid β, and let |Avn(β)| denote the number of such permutations. Two patterns β and σ are said to be Wilf-equivalent if |Avn(β)| = |Avn(σ)| for all n.

A basic example is if π = π1π2…πn avoids 321, i.e., has no decreasing subsequence of length 3, then its reverse, π' = πnπn-1…π1 avoids 123, i.e., has no increasing subsequence of length 3. It follows that, for each n, there are the same number of patterns of length n which avoid the patterns 123 and 321, i.e., 123 and 321 are Wilf-equivalent. By symmetry we see that the patterns 132, 231, 213, 312 are Wilf-equivalent: If π = π1π2…πn avoids 132, then its reverse, π' = πnπn-1…π1 avoids 231, its complement π" = (n+1-π1)(n+1-π2)…(n+1-πn) avoids 312, and the reverse of π" avoids 213. Since these operations are bijective, there are the same number of permutations of length n which avoid 132, 231, 213, and 312.

One way in which symmetry classes of permutations are commonly visualized is by using permutation matrices. Let M(π) be the permutation matrix having a 1 in position (i,π(i)) for 1 ≤ i ≤ n and 0's elsewhere. Then a permutation p contains the pattern π precisely when the matrix M(p) contains M(π) as a submatrix. The bijective reverse operation just described corresponds to a flip of the permutation matrix across a vertical axis; the bijective complement operation above corresponds to a flip of the permutation matrix across a horizontal axis. There is also a bijective operation which takes a permutation π = π1π2…πn to another permutation via the map which takes (i,π_i) to (π_i, i), which corresponds to a reflection across a diagonal of the permutation matrix. The symmetry class of p is the set of all permutations of p obtained by a finite number of reflections across vertical, horizontal, and diagonal axes. In other words, the symmetry class of p is the orbit of an action by the Dihedral group D8 on M(p). Within each symmetry class, permutations are Wilf-equivalent.[9]

There are also numerous examples of nontrivial Wilf-equivalences, including |Avn(123)| = |Avn(231)|. This was proved by combining the works of MacMahon and Knuth, who showed that for a given n these sets each have size Cn, the nth Catalan number. Simion & Schmidt (1985) gave the first bijective proof that 123- and 231-avoiding permutations are equinumerous.[10] It follows that all permutations of length 3 are Wilf-equivalent, meaning there is one Wilf-equivalence class for permutations of length 3. Many other bijections between sets of permutations which avoid a pattern in the symmetry class {123,321} and sets of permutations which avoid a pattern in the symmetry class {132,231,213,312} have been given; see Claesson & Kitaev (2008) or Kitaev (2011) for a survey.[11][12]

Classifying patterns of length 4 required novel approaches leading to other nontrivial Wilf-equivalences:

There are 7 symmetry classes of permutations of length 4: {1234,4321}, {1324,4231}, {2143,3412}, {2413,3142}, {1243,2134,3421,4312}, {1432,2341,3214,4123}, and {1342,1423,2314,2431,3124,3241,4132,4213}. These symmetry classes together with the aforementioned Wilf-equivalences determine three Wilf-equivalence classes for patterns of length 4, namely {1234,1243,1432,2134,2143,2341,3142,3214,3412,4123,4312,4321}, {1342,1423,2314,2413,3142,2431,3124,3241,4132,4213}, and {1324,4231}. The following are the 3 different sequences |Avn(β)| where β is of length four:

β sequence enumerating Avn(β) OEIS reference exact enumeration reference
 1342  1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ... A022558 Bóna (1997)[16]
 1234  1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ... A005802 Gessel (1990)[17]
 1324  1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ... A061552 unenumerated

Stanley-Wilf conjecture

In the late 1980s, Richard P. Stanley and Herbert Wilf conjectured that for every permutation β, there is some constant K such that |Avn(β)| < Kn. This was known as the Stanley–Wilf conjecture until it was proved by Adam Marcus and Gabor Tardos.[18]

Poset and its Möbius Function

The set of all permutations of n with the definition that π ≤ p if π occurs as a pattern in p is a poset. If π occurs as a pattern in p but π ≠ p, then we write π < p. A closed interval of a poset P is defined whenever s ≤ t as [s,t]=\{u\in P:s \leq u \leq t\} and [s,t]=\emptyset if s\nleq t in P.

The Möbius function (see incidence algebra) is an important poset invariant (mathematics), and Wilf first expressed the problem of computing the Möbius function of the permutation pattern poset in Wilf (2002).[19] For a given interval [s,t] of a poset P, its Möbius function is defined recursively:

\mu(x,y) = \begin{cases} {}\qquad 1 & \textrm{if}\quad x = y\\[6pt] \displaystyle -\sum_{z : x\leq z <y} \mu(x,z) & \textrm{for} \quad x<y \\[6pt] {}\qquad 0 & \textrm{otherwise}. \end{cases}

Calculating values of the Möbius function for permutations within an interval [s,t] of a poset P becomes difficult as the lengths of s and t increase. Burstein et al. (2011) give a computationally efficient formula for the Möbius function of an interval [s,t] for which s and t are both separable permutations.[20] Two consequences of this formula derived in Burstein et al. (2011) are that if s is separable, then μ(1,s)∈{0,1,-1}; and if s and t are separable, then |μ(s,t)| is at most the number of occurrences of s in t.

Closed classes

A closed class, also known as a pattern class, permutation class, or simply class of permutations is a downset 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 {231}, 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.

Given a class of permutations, there are numerous questions that one may seek to answer, such as:

General techniques to answer these questions are few and far between.

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_{n\rightarrow\infty} \frac{\text{number of copies of }\beta\text{ in a }\beta\text{-optimal permutation of length }n}{\displaystyle{n\choose k}}.

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 2√3 − 3, approximately 0.46410.

For permutations β of length four, there are (due to symmetries) seven cases to consider:

β packing density reference
 1234  1 trivial
 1432  root of x3 − 12x2 + 156x − 64 ≅ 0.42357 Price (1997)[21]
 2143  ⅜ = 0.375 Price (1997)[21]
 1243  ⅜ = 0.375 Albert et al. (2002)[22]
 1324  conjectured to be ≅ 0.244
 1342  conjectured to be ≅ 0.19658
 2413  conjectured to be ≅ 0.10474

For the three unknown permutations, there are bounds and conjectures. Price (1997) used an approximation algorithm which suggests that the packing density of 1324 is around 0.244.[21] 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. Presutti & Stromquist (2010) 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.[23]

Generalizations

There are several ways in which this notion of permutation patterns may be 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 Babson & Steingrímsson (2000), who showed that almost all known Mahonian statistics could be expressed in terms of vincular permutations.[24] 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 β. West (1993) introduced these types of patterns in his study of permutations which could be sorted by passing them twice through a stack.[25] (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 Bousquet-Mélou & Butler (2007), who showed that the Schubert variety corresponding to π is locally factorial if and only if π avoids 1324 and 21354.[26]

Superpatterns

Main article: Superpattern

A k-superpattern is a permutation of minimal length that contains all permutation patterns of length k. For example, consider the permutation 25314, which has length 5. It has 10 subsequences of length 3, including 253, 251, 234, 531, 534 and 314. (That is, we take 3 entries at a time, keeping the order preserved.) In each subsequence, we replace the smallest entry with 1, the next largest entry with 2, and the largest with 3. Thus, 253 gets renumbered to 132, 251 to 231, and so on. Applying this operation to the six selected subsequences gives all six possible length-3 patterns, 132, 231, 123, 321, 312 and 213. Thus, 25314 is a 3-superpattern.

It is known that a superpattern must have length at least k2/e2, where e ≈ 2.71828 is Euler's number,[27] and that there exist superpatterns of length k(k + 1)/2.[28] The k(k + 1)/2 bound is conjectured to be within lower-order terms of the best possible value.[28]

Algorithmic point of view

The problem of deciding whether a given permutation \pi of n elements matches a given pattern \sigma of k\leq n elements may be solved in polynomial time when k is a constant. However, when k is variable, the problem is NP-complete, and the problem of counting the number of such matches is #P-complete.[29] Other algorithmic developments have been recently obtained and surveyed by Bruner and Lackner;[30] most notably, the permutation pattern matching problem can be solved in polynomial time:

Moreover, the permutation pattern matching problem is known to be in FPT.[33]

References

  1. ↑ MacMahon, Percy A. (1915), Combinatory Analysis, London: Cambridge University Press, Volume I, Section III, Chapter V.
  2. ↑ MacMahon (1915), Items 97 and 98.
  3. ↑ Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, ISBN 0-201-89683-4, MR 0286317, OCLC 155842391..
  4. ↑ Knuth (1968), Section 2.2.1, Exercises 4 and 5.
  5. ↑ Knuth (1968), Section 2.2.1, Exercise 13, rated M49 in the first printing, and M48 in the second.
  6. ↑ Tarjan, Robert (1972), "Sorting using networks of queues and stacks", Journal of the ACM 19 (2): 341–346, doi:10.1145/321694.321704, MR 0298803.
  7. ↑ 7.0 7.1 Pratt, Vaughan R. (1973), "Computing permutations with double-ended queues. Parallel stacks and parallel queues", Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), pp. 268–277, doi:10.1145/800125.804058, MR 0489115.
  8. ↑ Rosenstiehl, Pierre; Tarjan, Robert (1984), "Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations", Journal of Algorithms 5 (3): 375–390, doi:10.1016/0196-6774(84)90018-X, MR 756164.
  9. ↑ Stankova, Zvezdelina (1996), "Classification of forbidden subsequences of length {$4$}", European Journal of Combinatorics 17: 501–517, doi:10.1006/eujc.1996.0044, MR 1397158
  10. ↑ Simion, Rodica; Schmidt, Frank W. (1985), "Restricted permutations", European Journal of Combinatorics 6: 383–406, doi:10.1016/s0195-6698(85)80052-4, MR 0829358.
  11. ↑ Claesson, Anders; Kitaev, Sergey (2008), "Classification of bijections between 321- and 132-avoiding permutations", Séminaire Lotharingien de Combinatoire 60: B60d, arXiv:0805.1325, MR 2465405.
  12. ↑ Kitaev, Sergey (2011), Patterns in Permutations and Words, Heidelberg: Springer, ISBN 978-3-642-17332-5, MR 3012380.
  13. ↑ Stankova, Zvezdelina (1994), "Forbidden subsequences", Discrete Mathematics 132 (1–3): 291–316, doi:10.1016/0012-365X(94)90242-9, MR 1297387.
  14. ↑ Stankova, Zvezdelina; West, Julian (2002), "A New class of Wilf-Equivalent Permutations", Journal of Algebraic Combinatorics 15 (3): 271–290, doi:10.1023/A:1015016625432, MR 1900628.
  15. ↑ Backelin, Jörgen; West, Julian; Xin, Guoce (2007), "Wilf-equivalence for singleton classes", Advances in Applied Mathematics 38 (2): 133–149, doi:10.1016/j.aam.2004.11.006, MR 2290807.
  16. ↑ Bóna, Miklós (1997), "Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps", Journal of Combinatorial Theory, Series A 80 (2): 257–272, doi:10.1006/jcta.1997.2800, MR 1485138.
  17. ↑ Gessel, Ira M. (1990), "Symmetric functions and P-recursiveness", Journal of Combinatorial Theory, Series A 53 (2): 257–285, doi:10.1016/0097-3165(90)90060-A, MR 1041448.
  18. ↑ Marcus, Adam; Tardos, Gábor (2004), "Excluded permutation matrices and the Stanley-Wilf conjecture", Journal of Combinatorial Theory, Series A 107 (1): 153–160, doi:10.1016/j.jcta.2004.04.002, MR 2063960.
  19. ↑ Wilf, Herbert (2002), "Patterns of permutations", Discrete Mathematics (journal) 257 (2): 575–583, doi:10.1016/S0012-365X(02)00515-0, MR 1935750.
  20. ↑ Burstein, Alexander; Jelinek, Vit; Jelinkova, Eva; Steingrimsson, Einar (2011), "The Möbius function of separable and decomposable permutations", Journal of Combinatorial Theory, Series A 118 (1): 2346–2364, doi:10.1016/j.jcta.2011.06.002, MR 2834180.
  21. ↑ 21.0 21.1 21.2 Price, Alkes (1997), Packing densities of layered patterns, Ph.D. thesis, University of Pennsylvania.
  22. ↑ Albert, Michael H.; Atkinson, M. D.; Handley, C. C.; Holton, D. A.; Stromquist, W. (2002), "On packing densities of permutations", Electronic Journal of Combinatorics 9: Research article 5, 20 pp., MR 1887086.
  23. ↑ Presutti, Cathleen Battiste; Stromquist, Walter (2010), "Packing rates of measures and a conjecture for the packing density of 2413", in Linton, Steve; Ruškuc, Nik; Vatter, Vincent, Permutation Patterns, London Math. Soc. Lecture Notes 376, Cambridge University Press, pp. 287–316, doi:10.1017/CBO9780511902499.015.
  24. ↑ Babson, Erik; Steingrímsson, Einar (2000), "Generalized permutation patterns and a classification of the Mahonian statistics", Séminaire Lotharingien de Combinatoire 44: Research article B44b, 18 pp., MR 1758852.
  25. ↑ West, Julian (1993), "Sorting twice through a stack", Theoretical Computer Science 117 (1–2): 303–313, doi:10.1016/0304-3975(93)90321-J, MR 1235186.
  26. ↑ Bousquet-Mélou, Mireille; Butler, Steve (2007), "Forest-like permutations", Annals of Combinatorics 11: 335–354, doi:10.1007/s00026-007-0322-1l, MR 2376109.
  27. ↑ Arratia, Richard (1999), "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern", Electronic Journal of Combinatorics 6: N1, MR 1710623.
  28. ↑ 28.0 28.1 Miller, Alison (2009), "Asymptotic bounds for permutations containing many different patterns", Journal of Combinatorial Theory, Series A 116 (1): 92–108, doi:10.1016/j.jcta.2008.04.007.
  29. ↑ Bose, Prosenjit; Buss, Jonathan F.; Lubiw, Anna (March 1998), "Pattern matching for permutations", Information Processing Letters 65 (5): 277–283, doi:10.1016/S0020-0190(97)00209-3
  30. ↑ Bruner, Marie-Louise; Lackner, Martin (2013), The computational landscape of permutation patterns, arXiv:1301.0340
  31. ↑ Guillemot, Sylvain; Vialette, Stéphane (2009), "Pattern matching for 321-avoiding permutations", Algorithms and Computation, Lecture Notes in Computer Science 5878, pp. 1064–1073, doi:10.1007/978-3-642-10631-6_107
  32. ↑ Kubica, M.; Kulczyński, T.; Radoszewski, J.; Rytter, W.; Waleń, T. (2013), "A linear time algorithm for consecutive permutation pattern matching", Information Processing Letters 113 (12): 430–433, doi:10.1016/j.ipl.2013.03.015.
  33. ↑ Guillemot, Sylvain; Marx, Daniel (2014). "Finding small patterns in permutations in linear time". Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms: 20. doi:10.1137/1.9781611973402.7.

External links

A conference on permutation patterns has been held annually since 2003:

Other links: