Permutation pattern

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation 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, 32··5, 324··, and ·2·15 all form triples of digits with the same ordering as 213. Each of the subsequences 315, 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[edit]

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 must contain either the pattern or the pattern .

Computer science origins[edit]

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[edit]

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 Avn(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 Avn(β) is used instead). As noted above, MacMahon and Knuth showed that |Avn(123)| = |Avn(231)| = Cn, the nth Catalan number. Thus these are isomorphic combinatorial classes.

Simion & Schmidt (1985) was the first paper to focus solely on enumeration. Among other results, Simion and Schmidt counted even and odd permutations 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.[9] Since their paper, many other bijections have been given, see Claesson & Kitaev (2008) for a survey.[10]

In general, if |Avn(β)| = |Avn(σ)| for all n, then β and σ are said to be Wilf-equivalent. Many Wilf-equivalences stem from the trivial fact that |Avn(β)| = |Avn(β−1)| = |Avnrev)| 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.) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between 123 and 231):

From these two Wilf-equivalences and the inverse and reverse symmetries, it follows that there are three 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)[14]
 1234  1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ... A005802 Gessel (1990)[15]
 1324  1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ... A061552 unenumerated

In the late 1980s, Richard 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 Gábor Tardos.[16]

Closed classes[edit]

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.

Möbius function[edit]

As the set of permutations under the containment order forms a poset it is natural to ask about its Möbius function, a goal first explicitly presented by Wilf (2002).[17] 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 Sagan & Vatter (2006), who gave a formula for the Möbius function of an interval of layered permutations.[18] Later, Burstein et al. (2011) generalized this result to intervals of separable permutations.[19]

Computational complexity[edit]

Given a permutation (called the text) of length and another permutation (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, and the problem of counting the number of such matches is #P-complete.[20] However, PPM can be solved in linear time when k is a constant. Indeed, Guillemot and Marx[21] showed that PPM can be solved in time , meaning that it is fixed-parameter tractable with respect to .

There are several variants on the PPM problem, as surveyed by Bruner and Lackner.[22] For example, if the match is required to consist of contiguous entries then the problem can be solved in polynomial time.[23]

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[24] showed that -PPM could be solved in time. Albert, Lackner, Lackner, and Vatter[25] later lowered this to and showed that the same bound holds for the class of skew-merged permutations. They further asked if the -PPM problem can be solved in polynomial time for every fixed proper permutation class .

Packing densities[edit]

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 shows that the quantity inside this limit is nonincreasing for nk, 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 23 − 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)[26]
 2143  ⅜ = 0.375 Price (1997)[26]
 1243  ⅜ = 0.375 Albert et al. (2002)[27]
 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.[26] 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.[28]


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 k2/e2, where e ≈ 2.71828 is Euler's number,[29] and that there exist superpatterns of length k(k + 1)/2.[30] The k(k + 1)/2 bound is conjectured to be best possible, up to lower-order terms.[30]


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 Babson & Steingrímsson (2000), who showed that almost all known Mahonian statistics could be expressed in terms of vincular permutations.[31] 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.[32] (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.[33]


  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. ^ a b 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 0756164.
  9. ^ 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.
  10. ^ Claesson, Anders; Kitaev, Sergey (2008), "Classification of bijections between 321- and 132-avoiding permutations" (PDF), Séminaire Lotharingien de Combinatoire, 60: B60d, arXiv:0805.1325, Bibcode:2008arXiv0805.1325C, MR 2465405.
  11. ^ Stankova, Zvezdelina (1994), "Forbidden subsequences", Discrete Mathematics, 132 (1–3): 291–316, doi:10.1016/0012-365X(94)90242-9, MR 1297387.
  12. ^ Stankova, Zvezdelina; West, Julian (2002), "A New class of Wilf-Equivalent Permutations", Journal of Algebraic Combinatorics, 15 (3): 271–290, arXiv:math/0103152, doi:10.1023/A:1015016625432, MR 1900628.
  13. ^ 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.
  14. ^ 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.
  15. ^ 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.
  16. ^ 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.
  17. ^ Wilf, Herbert (2002), "Patterns of permutations", Discrete Mathematics, 257 (2): 575–583, doi:10.1016/S0012-365X(02)00515-0, MR 1935750.
  18. ^ Sagan, Bruce; Vatter, Vince (2006), "The Möbius function of a composition poset", Journal of Algebraic Combinatorics, 24 (2): 117–136, arXiv:math/0507485, doi:10.1007/s10801-006-0017-4, MR 2259013.
  19. ^ 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.
  20. ^ 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
  21. ^ 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. arXiv:1307.3073. doi:10.1137/1.9781611973402.7.
  22. ^ Bruner, Marie-Louise; Lackner, Martin (2013), "The computational landscape of permutation patterns", Pure Mathematics and Applications, 24 (2): 83–101, arXiv:1301.0340, Bibcode:2013arXiv1301.0340B
  23. ^ 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
  24. ^ 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
  25. ^ Albert, Michael; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), "The complexity of pattern matching for 321-avoiding and skew-merged permutations", Discrete Mathematics & Theoretical Computer Science, 18 (2), arXiv:1510.06051, Bibcode:2015arXiv151006051A
  26. ^ a b c Price, Alkes (1997), Packing densities of layered patterns, Ph.D. thesis, University of Pennsylvania.
  27. ^ 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.
  28. ^ 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.
  29. ^ 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.
  30. ^ a b 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.
  31. ^ 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.
  32. ^ 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.
  33. ^ Bousquet-Mélou, Mireille; Butler, Steve (2007), "Forest-like permutations", Annals of Combinatorics, 11: 335–354, arXiv:math/0603617, doi:10.1007/s00026-007-0322-1, MR 2376109.

External links[edit]

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

American Mathematical Society Special Sessions on Patterns in Permutations have been held at the following meetings:

Other permutation patterns meetings:

Other links: