In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation 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
For instance, permutation
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
If a permutation
Early results
editA 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
editThe study of permutation patterns began in earnest with Donald Knuth's consideration of stack-sorting in 1968.[3] Knuth showed that the permutation
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
editA 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 {
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(
- Stankova (1994) proved that the permutations 1342 and 2413 are Wilf-equivalent.[11]
- Stankova & West (2002) proved that for any permutation
β , the permutations 231 ⊕β and 312 ⊕β are Wilf-equivalent, where ⊕ denotes the direct sum operation.[12] - Backelin, West & Xin (2007) proved that for any permutation
β and any positive integer m, the permutations 12..m ⊕β and m...21 ⊕β are Wilf-equivalent.[13]
From these two Wilf-equivalences and the inverse and reverse symmetries, it follows that there are three different sequences |Avn(
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
Closed classes
editA 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
Möbius function
editAs 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 [
It is known that, asymptotically, at least 39.95% of all permutations
Computational complexity
editGiven 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, and the problem of counting the number of such matches is #P-complete.[22] However, PPM can be solved in linear time when k is a constant. Indeed, Guillemot and Marx[23] 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.[24] For example, if the match is required to consist of contiguous entries then the problem can be solved in polynomial time.[25] A different natural variant is obtained when the pattern is restricted to a proper permutation class . This problem is known as -Pattern PPM and it was shown to be polynomial-time solvable for separable permutations.[22] Later, Jelínek and Kynčl[26] completely resolved the complexity of -Pattern PPM by showing that it is polynomial-time solvable when 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 , in which case the problem is called -PPM. For example, Guillemot and Vialette[27] showed that -PPM could be solved in time. Albert, Lackner, Lackner, and Vatter[28] 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 . This question was answered negatively by Jelínek and Kynčl who showed that -PPM is in fact NP-complete.[26] Later, Jelínek, Opler, and Pekárek[29] showed that -PPM is NP-complete for any of length at least 4 not symmetric to one of 3412, 3142, 4213, 4123 or 41352.
Packing densities
editThe permutation
An unpublished argument of Fred Galvin shows that the quantity inside this limit is nonincreasing for n ≥ k, and so the limit exists. When
For permutations
packing density | reference | |
---|---|---|
1234 | 1 | trivial |
1432 | root of x3 − 12x2 + 156x − 64 ≅ 0.42357 | Price (1997)[30] |
2143 | 3/8 = 0.375 | Price (1997)[30] |
1243 | 3/8 = 0.375 | Albert et al. (2002)[31] |
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.[30] 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.[32]
Superpatterns
editA 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,[33] and that there exist k-superpatterns of length ⌈(k2 + 1)/2⌉.[34] This upper bound is conjectured to be best possible, up to lower-order terms.[35]
Generalizations
editThe 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
Another generalization is that of a barred pattern, in which some of the entries are barred. For
References
edit- ^ MacMahon, Percy A. (1915), Combinatory Analysis, London: Cambridge University Press, Volume I, Section III, Chapter V.
- ^ MacMahon (1915), Items 97 and 98.
- ^ Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, ISBN 0-201-89683-4, MR 0286317, OCLC 155842391.
- ^ Knuth (1968), Section 2.2.1, Exercises 4 and 5.
- ^ Knuth (1968), Section 2.2.1, Exercise 13, rated M49 in the first printing, and M48 in the second.
- ^ 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, S2CID 13608929.
- ^ 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, S2CID 15740957.
- ^ 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.
- ^ Simion, Rodica; Schmidt, Frank W. (1985), "Restricted permutations", European Journal of Combinatorics, 6 (4): 383–406, doi:10.1016/s0195-6698(85)80052-4, MR 0829358.
- ^ Claesson, Anders; Kitaev, Sergey (2008), "Classification of bijections between 321- and 132-avoiding permutations", Séminaire Lotharingien de Combinatoire, 60: B60d, 30pp, arXiv:0805.1325, MR 2465405.
- ^ Stankova, Zvezdelina (1994), "Forbidden subsequences", Discrete Mathematics, 132 (1–3): 291–316, doi:10.1016/0012-365X(94)90242-9, MR 1297387.
- ^ 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, S2CID 13921676.
- ^ 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.
- ^ 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, arXiv:math/9702223, doi:10.1006/jcta.1997.2800, MR 1485138, S2CID 18352890.
- ^ 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.
- ^ 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.
- ^ Wilf, Herbert (2002), "Patterns of permutations", Discrete Mathematics, 257 (2): 575–583, doi:10.1016/S0012-365X(02)00515-0, MR 1935750.
- ^ 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, S2CID 11283347.
- ^ 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, S2CID 13978488.
- ^ Brignall, Robert; Jelínek, Vit; Kynčl, Jan; Marchant, David (2019), "Zeros of the Möbius function of permutations" (PDF), Mathematika, 65 (4): 1074–1092, arXiv:1810.05449, doi:10.1112/S0025579319000251, MR 3992365, S2CID 53366318
- ^ Marchant, David (2020), "2413-balloon permutations and the growth of the Möbius function", Electronic Journal of Combinatorics, 27 (1): Article P1.7, 18 pp, arXiv:1812.05064, doi:10.37236/8554
- ^ a b 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
- ^ 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. ISBN 978-1-61197-338-9. S2CID 1846959.
- ^ Bruner, Marie-Louise; Lackner, Martin (2013), "The computational landscape of permutation patterns", Pure Mathematics and Applications, 24 (2): 83–101, arXiv:1301.0340
- ^ 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
- ^ a b Jelínek, Vít; Kynčl, Jan (2017). "Hardness of Permutation Pattern Matching". Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. SIAM. pp. 378–396. arXiv:1608.00529. doi:10.1137/1.9781611974782.24.
- ^ Guillemot, Sylvain; Vialette, Stéphane (2009), "Pattern matching for 321-avoiding permutations", Algorithms and Computation, Lecture Notes in Computer Science, vol. 5878, pp. 1064–1073, arXiv:1511.01770, doi:10.1007/978-3-642-10631-6_107, ISBN 978-3-642-10630-9
- ^ 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, doi:10.46298/dmtcs.1308, S2CID 5827603
- ^ Jelínek, Vít; Opler, Michal; Pekárek, Jakub (2021). "Griddings of Permutations and Hardness of Pattern Matching". 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 65:1–65:22. arXiv:2107.10897. doi:10.4230/LIPIcs.MFCS.2021.65.
- ^ a b c Price, Alkes (1997), Packing densities of layered patterns, Ph.D. thesis, University of Pennsylvania, ProQuest 304421853.
- ^ 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: Article R5, 20 pp, doi:10.37236/1622, MR 1887086.
- ^ 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 (eds.), Permutation Patterns, London Math. Soc. Lecture Notes, vol. 376, Cambridge University Press, pp. 287–316, doi:10.1017/CBO9780511902499.015, ISBN 978-0-521-72834-8.
- ^ Arratia, Richard (1999), "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern", Electronic Journal of Combinatorics, 6: Article N1, 4 pp, doi:10.37236/1477, MR 1710623.
- ^ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly, 128 (1): 4–24, arXiv:1810.08252, doi:10.1080/00029890.2021.1835384
- ^ Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (2007), "Dense packing of patterns in a permutation", Annals of Combinatorics, 11 (3–4): 459–470, doi:10.1007/s00026-007-0329-7, MR 2376116, S2CID 2021533.
- ^ 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.
- ^ 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.
- ^ Bousquet-Mélou, Mireille; Butler, Steve (2007), "Forest-like permutations", Annals of Combinatorics, 11 (3–4): 335–354, arXiv:math/0603617, doi:10.1007/s00026-007-0322-1, MR 2376109, S2CID 31236417.
External links
editA conference on permutation patterns has been held annually since 2003:
- Permutation Patterns 2003, February 10–14, 2003, University of Otago, Dunedin, New Zealand.
- Permutation Patterns 2004, July 5–9, 2004, Malaspina University-College, Nanaimo, British Columbia, Canada.
- Permutation Patterns 2005, March 7–11, 2005, University of Florida, Gainesville, Florida, USA.
- Permutation Patterns 2006, June 12–16, 2006, Reykjavík University, Reykjavík, Iceland.
- Permutation Patterns 2007, June 11–15, 2007, University of St. Andrews, St. Andrews, Scotland.
- Permutation Patterns 2008, June 16–20, 2008, University of Otago, Dunedin, New Zealand.
- Permutation Patterns 2009, July 13–17, 2009, Università di Firenze, Florence, Italy.
- Permutation Patterns 2010, August 9–13, 2010, Dartmouth College, 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, Glasgow, Scotland.
- Permutation Patterns 2013, July 1–5, 2013, Université Paris Diderot, Paris, France.
- Permutation Patterns 2014, July 7–11, 2014, East Tennessee State University, 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, Washington, DC, USA.
- Permutation Patterns 2017, June 26–30, 2017, Reykjavík University, Reykjavík, Iceland.
- Permutation Patterns 2018, July 9–13, 2018, Dartmouth College, Hanover, New Hampshire, USA.
- Permutation Patterns 2019, June 17–21, 2019, Universität Zürich, Zürich, Switzerland.
- Permutation Patterns 2020 Virtual Workshop, June 30–July 1, 2020, hosted by Valparaiso University, Valparaiso, Indiana, USA.
- Permutation Patterns 2021 Virtual Workshop, June 15–16, 2021, hosted by University of Strathclyde, Glasgow, Scotland.
- Permutation Patterns 2022, June 20-24, 2022, Valparaiso University, Valparaiso, Indiana, USA.
- Permutation Patterns 2023, July 3-7, 2023, University of Burgundy, Dijon, France.
American Mathematical Society 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, NY.
- Joint Mathematics Meetings, January 12, 2013, San Diego, CA.
- Central Fall Sectional Meeting, September 20–21, 2014, University of Wisconsin-Eau Claire, Eau Claire, WI.
- Spring Eastern Sectional Meeting, March 7–8, 2015, Georgetown University, Washington, DC.
Other permutation patterns meetings:
- Workshop on Permutation Patterns, May 29–June 3, 2005, University of Haifa, 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.
- 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.