1712:, 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
1691:
1885:
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
383:
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
1999:
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
36:
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
1967:
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 β(π)
1170:
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
95:
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
130:) 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
1606:
372:+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
858:. 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
1995:, 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 β.
1890:
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.
1141:
1686:{\displaystyle \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}}}.}
1558:
1254:
1525:
1358:
294:
1492:
1468:
1325:
1301:
1217:
1193:
398:
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
244:
1404:
200:
1578:
1274:
1440:
1027:
915:
1007:
959:
1165:
1067:
1047:
979:
939:
1968:
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
471:, and gave the first bijective proof that 123- and 231-avoiding permutations are equinumerous. Since their paper, many other bijections have been given, see
468:
393:
3906:, a database of algorithmically-derived theorems about permutation classes, maintained by Christian Bean, Émile Nadeau, Jay Pantone and Henning Ulfarsson.
3446:
3117:; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), "The complexity of pattern matching for 321-avoiding and skew-merged permutations",
2329:
1592:
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
690:
3008:
Kubica, M.; Kulczyński, T.; Radoszewski, J.; Rytter, W.; Waleń, T. (2013), "A linear time algorithm for consecutive permutation pattern matching",
3667:
2743:
Burstein, Alexander; Jelinek, Vit; Jelinkova, Eva; Steingrimsson, Einar (2011), "The Möbius function of separable and decomposable permutations",
114:σ. The permutation 51342 avoids 213; it has ten subsequences of three entries, but none of these ten subsequences has the same ordering as 213.
3475:
3041:
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19
3293:
3099:
2956:
3318:
3235:
2853:
3821:
2690:
2407:
834:. Thus the basis for the stack-sortable permutations is {231}, while the basis for the deque-sortable permutations is infinite. The
3805:
2282:
2080:
2194:
652:
From these two Wilf-equivalences and the inverse and reverse symmetries, it follows that there are three different sequences |Av
3697:
2745:
2606:
2563:
2504:
2462:
2071:
3163:
46th
International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia
3010:
2903:
2648:
2368:
3395:
Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (2007), "Dense packing of patterns in a permutation",
138:
3919:
3794:
3357:
830:
in the permutation pattern order. Every class can be defined by the minimal permutations which do not lie inside it, its
3597:
3516:
21:
3811:
785:
789:
376:
of permutations), it is not immediately clear how long it takes to decide if a permutation can be sorted by a deque.
3687:
3512:
615:
309:
3161:
Jelínek, Vít; Opler, Michal; Pekárek, Jakub (2021). "Griddings of
Permutations and Hardness of Pattern Matching".
3767:
3677:
3627:
1933:
1144:
2032:
1088:
3747:
3647:
1916:. For example, 25314 is a 3-superpattern because it contains all 6 permutations of length 3. It is known that
380:
later presented a linear (in the length of π) time algorithm which determines if π can be sorted by a deque.
3727:
3663:
3617:
3521:
3397:
2502:(1997), "Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps",
1443:
464:
3787:
3773:
1530:
1226:
1220:
313:
3831:
3777:
3757:
3607:
3593:
3208:
1981:
871:
847:
1497:
1330:
249:
2980:
Bruner, Marie-Louise; Lackner, Martin (2013), "The computational landscape of permutation patterns",
827:
578:
463:
was the first paper to focus solely on enumeration. Among other results, Simion and
Schmidt counted
1952:
The type of pattern defined above, in which entries do not need to occur consecutively, is called a
1473:
1449:
1306:
1282:
1198:
1174:
581:.) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between
205:
3846:
3637:
3587:
1956:(permutation) pattern. If the entries are required to be consecutive, then the pattern is called a
1701:
1363:
863:
454:
2929:
Guillemot, Sylvain; Marx, Daniel (2014). "Finding small patterns in permutations in linear time".
1944: + 1)/2⌉. This upper bound is conjectured to be best possible, up to lower-order terms.
152:
3872:
3862:
3852:
3556:
3530:
3422:
3366:
3166:
3144:
3126:
3077:
3072:
Guillemot, Sylvain; Vialette, Stéphane (2009), "Pattern matching for 321-avoiding permutations",
3044:
2989:
2962:
2934:
2862:
2834:
2808:
2772:
2725:
2699:
2539:
2513:
2442:
2416:
2338:
2235:
2217:
2168:
2141:
2040:
755:
571:
321:
3827:
3817:
3801:
3280:, London Math. Soc. Lecture Notes, vol. 376, Cambridge University Press, pp. 287–316,
2192:(1973), "Computing permutations with double-ended queues. Parallel stacks and parallel queues",
1279:
Another variant is when both the pattern and text are restricted to a proper permutation class
3891:
3737:
3717:
3657:
3313:
3289:
3230:
3226:
3114:
3095:
2952:
2499:
2094:
2076:
1963:
There are several ways in which the notion of "pattern" has been generalized. For example, a
1407:
851:
805:
2460:
Backelin, Jörgen; West, Julian; Xin, Guoce (2007), "Wilf-equivalence for singleton classes",
1563:
1259:
3876:
3866:
3856:
3613:
3540:
3484:
3406:
3376:
3327:
3281:
3244:
3176:
3136:
3087:
3054:
3019:
2944:
2912:
2872:
2818:
2754:
2709:
2657:
2615:
2572:
2523:
2471:
2426:
2377:
2324:
2291:
2251:
2199:
2150:
2009:
2005:
1074:
511:
316:
if and only if π avoids 231, and that the stack-sortable permutations are enumerated by the
3842:
3743:
3552:
3498:
3459:
3418:
3341:
3258:
2851:
Marchant, David (2020), "2413-balloon permutations and the growth of the Möbius function",
2830:
2768:
2721:
2671:
2629:
2586:
2535:
2485:
2438:
2391:
2352:
2305:
2263:
2213:
2164:
2090:
1413:
1012:
900:
3548:
3494:
3455:
3414:
3337:
3309:
3254:
2826:
2764:
2717:
2667:
2625:
2582:
2531:
2481:
2434:
2405:
Stankova, Zvezdelina; West, Julian (2002), "A New class of Wilf-Equivalent
Permutations",
2387:
2348:
2301:
2259:
2209:
2160:
2086:
1726:
For permutations β of length four, there are (due to symmetries) seven cases to consider:
992:
944:
881:
satisfy μ(1, π)=0 (that is, the principal Möbius function is equal to zero), but for each
3753:
2791:
2601:
793:
3441:
3314:"On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern"
3797:
Special
Sessions on Patterns in Permutations have been held at the following meetings:
1470:-PPM problem can be solved in polynomial time for every fixed proper permutation class
1150:
1052:
1032:
964:
924:
317:
131:
123:
2916:
2662:
2296:
107:
of the pattern. The fact that π contains σ is written more concisely as σ ≤ π.
3913:
3603:
3489:
2577:
2382:
2320:
2277:
2255:
2239:
2189:
2136:
2126:, Section 2.2.1, Exercise 13, rated M49 in the first printing, and M48 in the second.
337:
329:
141:; in permutation pattern language, the theorem states that for any positive integers
17:
3560:
2838:
2776:
2729:
2543:
2446:
2221:
2172:
3633:
3426:
3148:
2966:
2643:
2242:(1984), "Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations",
2066:
1899:
759:
328:
elements are obtainable with the use of a deque remains open. Shortly thereafter,
305:
3442:"Generalized permutation patterns and a classification of the Mahonian statistics"
3381:
3091:
877:
It is known that, asymptotically, at least 39.95% of all permutations π of length
56:
For instance, permutation π contains the pattern 213 whenever π has three entries
3713:
3285:
3273:
3897:
3763:
3673:
3583:
3212:
3181:
2931:
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on
Discrete Algorithms
2799:
2685:
1985:
1697:
1085:
is a constant. Indeed, Guillemot and Marx showed that PPM can be solved in time
1078:
1070:
838:
for a class is Σ x where the sum is taken over all permutations π in the class.
555:
344:) showed that the permutation π can be sorted by a deque if and only if for all
50:
33:
29:
3058:
2759:
2620:
3703:
3544:
3410:
3023:
2948:
2898:
2822:
2713:
2476:
2430:
1580:
of length at least 4 not symmetric to one of 3412, 3142, 4213, 4123 or 41352.
1276:
is equal to one of 1, 12, 21, 132, 231, 312 or 213 and NP-complete otherwise.
3202:
3039:
Jelínek, Vít; Kynčl, Jan (2017). "Hardness of Permutation Pattern Matching".
2098:
1494:. This question was answered negatively by Jelínek and Kynčl who showed that
3623:
3274:"Packing rates of measures and a conjecture for the packing density of 2413"
2195:
Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973)
1527:-PPM is in fact NP-complete. Later, Jelínek, Opler, and Pekárek showed that
373:
53:
of the entries of π has the same relative order as all of the entries of σ.
3576:
2527:
885:
there exist permutations π such that μ(1, π) is an exponential function of
3683:
3165:. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 65:1–65:22.
2204:
2155:
3229:; Atkinson, M. D.; Handley, C. C.; Holton, D. A.; Stromquist, W. (2002),
3076:, Lecture Notes in Computer Science, vol. 5878, pp. 1064–1073,
2894:
2604:(2004), "Excluded permutation matrices and the Stanley-Wilf conjecture",
2325:"Classification of bijections between 321- and 132-avoiding permutations"
3783:
3693:
3140:
1988:
of π is equal to 1−32(π) + 2−31(π) + 3−21(π) + 21(π).
1984:
could be expressed in terms of vincular permutations. For example, the
3733:
3355:
Engen, Michael; Vatter, Vincent (2021), "Containing all permutations",
1881:
For the three unknown permutations, there are bounds and conjectures.
2688:; Vatter, Vince (2006), "The Möbius function of a composition poset",
430:) is used instead.) As noted above, MacMahon and Knuth showed that |Av
3873:
Pattern Avoidance, Statistical Mechanics and Computational Complexity
3653:
3535:
2704:
2518:
2421:
867:
3887:
2790:
Brignall, Robert; Jelínek, Vit; Kynčl, Jan; Marchant, David (2019),
3643:
3371:
3171:
3131:
3082:
3049:
2867:
2813:
110:
If a permutation π does not contain a pattern σ, then π is said to
3332:
3249:
2994:
2939:
2877:
2343:
467:
avoiding a pattern of length three, counted permutations avoiding
324:. In particular, Knuth's question asking how many permutation of
92:, the same as the ordering of the values in the permutation 213.
1256:-Pattern PPM by showing that it is polynomial-time solvable when
1223:. Later, Jelínek and Kynčl completely resolved the complexity of
1219:-Pattern PPM and it was shown to be polynomial-time solvable for
312:
in 1968. Knuth showed that the permutation π can be sorted by a
3707:
862:, who gave a formula for the Möbius function of an interval of
846:
As the set of permutations under the containment order forms a
596:
proved that the permutations 1342 and 2413 are Wilf-equivalent.
516:. Many Wilf-equivalences stem from the trivial fact that |Av
3723:
1479:
1455:
1312:
1288:
1204:
1180:
1073:, and the problem of counting the number of such matches is
1886:
is conjectured to be the precise packing density of 1342.
1834:
743:
725:
707:
38:
1912:
is a permutation that contains all permutations of length
3276:, in Linton, Steve; Ruškuc, Nik; Vatter, Vincent (eds.),
3272:
Presutti, Cathleen Battiste; Stromquist, Walter (2010),
304:
The study of permutation patterns began in earnest with
3903:
3119:
Discrete Mathematics & Theoretical Computer Science
2366:
Stankova, Zvezdelina (1994), "Forbidden subsequences",
2280:; Schmidt, Frank W. (1985), "Restricted permutations",
2139:(1972), "Sorting using networks of queues and stacks",
1976:
is 231(π) + 132(π). These patterns were introduced by
3863:
Genomics, Pattern Avoidance, and Statistical Mechanics
3473:
West, Julian (1993), "Sorting twice through a stack",
1535:
1502:
1442:
and showed that the same bound holds for the class of
1335:
1327:-PPM. For example, Guillemot and Vialette showed that
1231:
1069:
are regarded as variables, the problem is known to be
740:
1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ...
722:
1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ...
704:
1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ...
1654:
1609:
1566:
1533:
1500:
1476:
1452:
1416:
1410:, Lackner, Lackner, and Vatter later lowered this to
1366:
1333:
1309:
1285:
1262:
1229:
1201:
1177:
1153:
1091:
1055:
1035:
1015:
995:
967:
947:
927:
903:
252:
208:
155:
2001:
336:) investigated sorting by networks of stacks, while
2901:(March 1998), "Pattern matching for permutations",
1977:
1728:
668:
3904:PermPAL: The Permutation Pattern Avoidance Library
1887:
1685:
1572:
1552:
1519:
1486:
1462:
1434:
1398:
1352:
1319:
1295:
1268:
1248:
1211:
1187:
1159:
1135:
1061:
1041:
1021:
1001:
973:
953:
933:
909:
320:. Knuth also raised questions about sorting with
288:
238:
194:
137:Another early landmark result in the field is the
1671:
1658:
377:
2557:Gessel, Ira M. (1990), "Symmetric functions and
1611:
621:
614:are Wilf-equivalent, where ⊕ denotes the
408:which avoid all of the permutations in the set
3575:A conference on permutation patterns has been
2792:"Zeros of the Möbius function of permutations"
472:
1972:in π is 213(π) + 312(π), while the number of
460:
453:th Catalan number. Thus these are isomorphic
404:(B) denote the set of permutations of length
37:permutations and are unrelated to the number
8:
3207:, Ph.D. thesis, University of Pennsylvania,
599:
394:Enumerations of specific permutation classes
3440:Babson, Erik; Steingrímsson, Einar (2000),
2889:
2887:
859:
3888:PermLab: software for permutation patterns
3764:Permutation Patterns 2021 Virtual Workshop
3754:Permutation Patterns 2020 Virtual Workshop
3196:
3194:
3192:
3034:
3032:
3898:Database of Permutation Pattern Avoidance
3534:
3488:
3380:
3370:
3331:
3248:
3180:
3170:
3130:
3081:
3048:
2993:
2938:
2876:
2866:
2812:
2758:
2703:
2661:
2619:
2576:
2517:
2475:
2420:
2381:
2342:
2295:
2203:
2184:
2182:
2154:
1920:-superpatterns must have length at least
1670:
1657:
1655:
1645:
1637:
1629:
1626:
1614:
1608:
1565:
1534:
1532:
1501:
1499:
1478:
1477:
1475:
1454:
1453:
1451:
1415:
1387:
1377:
1365:
1334:
1332:
1311:
1310:
1308:
1287:
1286:
1284:
1261:
1230:
1228:
1203:
1202:
1200:
1179:
1178:
1176:
1152:
1136:{\displaystyle 2^{O(k^{2}\log k)}\cdot n}
1107:
1096:
1090:
1054:
1034:
1014:
994:
966:
946:
926:
902:
251:
207:
154:
2053:
870:generalized this result to intervals of
593:
127:
3668:California Polytechnic State University
2024:
854:, a goal first explicitly presented by
762:conjectured that for every permutation
3447:Séminaire Lotharingien de Combinatoire
3231:"On packing densities of permutations"
2330:Séminaire Lotharingien de Combinatoire
2072:The Art Of Computer Programming Vol. 1
2039:, London: Cambridge University Press,
1303:, in which case the problem is called
730:
570:. (These two operations generate the
333:
149:every permutation of length at least
3838:Other permutation patterns meetings:
3204:Packing densities of layered patterns
2123:
2111:
1882:
1804:
1774:
341:
7:
3853:Pattern Avoidance and Genome Sorting
3600:, Nanaimo, British Columbia, Canada.
3519:(2007), "Forest-like permutations",
2646:(2002), "Patterns of permutations",
1996:
1991:Another generalization is that of a
1700:shows that the quantity inside this
1647:-optimal permutation of length
1553:{\displaystyle {\mbox{Av}}(\sigma )}
1249:{\displaystyle {\mbox{Av}}(\sigma )}
855:
712:
32:. Any permutation may be written in
3670:, San Luis Obispo, California, USA.
3319:Electronic Journal of Combinatorics
3236:Electronic Journal of Combinatorics
2854:Electronic Journal of Combinatorics
2114:, Section 2.2.1, Exercises 4 and 5.
2012:if and only if π avoids 1324 and 21
1980:, who showed that almost all known
3822:University of Wisconsin-Eau Claire
3814:, January 12, 2013, San Diego, CA.
3756:, June 30–July 1, 2020, hosted by
2691:Journal of Algebraic Combinatorics
2408:Journal of Algebraic Combinatorics
2002:Bousquet-Mélou & Butler (2007)
1662:
1621:
1588:The permutation π is said to be β-
987:permutation pattern matching (PPM)
68:that appear within π in the order
14:
3806:Rochester Institute of Technology
2982:Pure Mathematics and Applications
2283:European Journal of Combinatorics
1978:Babson & Steingrímsson (2000)
1520:{\displaystyle {\mbox{Av}}(4321)}
28:is a sub-permutation of a longer
3843:Workshop on Permutation Patterns
3828:Spring Eastern Sectional Meeting
3454:: Research article B44b, 18 pp,
2041:Volume I, Section III, Chapter V
1888:Presutti & Stromquist (2010)
1353:{\displaystyle {\mbox{Av}}(321)}
1077:. However, PPM can be solved in
624:proved that for any permutation
602:proved that for any permutation
289:{\displaystyle b,b-1,\dots ,2,1}
202:must contain either the pattern
80:but whose values are ordered as
3900:, maintained by Bridget Tenner.
3700:, Johnson City, Tennessee, USA.
3698:East Tennessee State University
2746:Journal of Combinatorial Theory
2607:Journal of Combinatorial Theory
2564:Journal of Combinatorial Theory
2505:Journal of Combinatorial Theory
2463:Advances in Applied Mathematics
1596:of the permutation β of length
850:it is natural to ask about its
622:Backelin, West & Xin (2007)
606:, the permutations 231 ⊕
378:Rosenstiehl & Tarjan (1984)
3818:Central Fall Sectional Meeting
3802:Fall Eastern Sectional Meeting
3766:, June 15–16, 2021, hosted by
3740:, Hanover, New Hampshire, USA.
3660:, Hanover, New Hampshire, USA.
3011:Information Processing Letters
2904:Information Processing Letters
1618:
1547:
1541:
1514:
1508:
1487:{\displaystyle {\mathcal {C}}}
1463:{\displaystyle {\mathcal {C}}}
1429:
1420:
1393:
1370:
1347:
1341:
1320:{\displaystyle {\mathcal {C}}}
1296:{\displaystyle {\mathcal {C}}}
1243:
1237:
1212:{\displaystyle {\mathcal {C}}}
1188:{\displaystyle {\mathcal {C}}}
1122:
1100:
239:{\displaystyle 1,2,3,\dots ,a}
183:
171:
168:
156:
1:
3795:American Mathematical Society
3382:10.1080/00029890.2021.1835384
3358:American Mathematical Monthly
3092:10.1007/978-3-642-10631-6_107
2917:10.1016/S0020-0190(97)00209-3
2663:10.1016/S0012-365X(02)00515-0
2297:10.1016/s0195-6698(85)80052-4
1399:{\displaystyle O(k^{2}n^{6})}
3610:, Gainesville, Florida, USA.
3598:Malaspina University-College
3490:10.1016/0304-3975(93)90321-J
3476:Theoretical Computer Science
3286:10.1017/CBO9780511902499.015
2578:10.1016/0097-3165(90)90060-A
2383:10.1016/0012-365X(94)90242-9
2256:10.1016/0196-6774(84)90018-X
1560:-PPM is NP-complete for any
1446:. They further asked if the
696:exact enumeration reference
473:Claesson & Kitaev (2008)
469:two patterns of length three
195:{\displaystyle (a-1)(b-1)+1}
22:theoretical computer science
3780:, Valparaiso, Indiana, USA.
3760:, Valparaiso, Indiana, USA.
3182:10.4230/LIPIcs.MFCS.2021.65
1940:-superpatterns of length ⌈(
1696:An unpublished argument of
1195:. This problem is known as
461:Simion & Schmidt (1985)
3936:
3812:Joint Mathematics Meetings
3074:Algorithms and Computation
3059:10.1137/1.9781611974782.24
3043:. SIAM. pp. 378–396.
2861:(1): Article P1.7, 18 pp,
2760:10.1016/j.jcta.2011.06.002
2621:10.1016/j.jcta.2004.04.002
2075:, Boston: Addison-Wesley,
1897:
1770:− 64 ≅ 0.42357
803:
600:Stankova & West (2002)
391:
3820:, September 20–21, 2014,
3804:, September 22–23, 2012,
3784:Permutation Patterns 2023
3774:Permutation Patterns 2022
3768:University of Strathclyde
3744:Permutation Patterns 2019
3734:Permutation Patterns 2018
3724:Permutation Patterns 2017
3714:Permutation Patterns 2016
3704:Permutation Patterns 2015
3694:Permutation Patterns 2014
3684:Permutation Patterns 2013
3678:University of Strathclyde
3674:Permutation Patterns 2012
3664:Permutation Patterns 2011
3654:Permutation Patterns 2010
3644:Permutation Patterns 2009
3634:Permutation Patterns 2008
3628:University of St. Andrews
3624:Permutation Patterns 2007
3614:Permutation Patterns 2006
3604:Permutation Patterns 2005
3594:Permutation Patterns 2004
3584:Permutation Patterns 2003
3545:10.1007/s00026-007-0322-1
3411:10.1007/s00026-007-0329-7
3024:10.1016/j.ipl.2013.03.015
2949:10.1137/1.9781611973402.7
2823:10.1112/S0025579319000251
2714:10.1007/s10801-006-0017-4
2477:10.1016/j.aam.2004.11.006
1932: ≈ 2.71828 is
1723:, approximately 0.46410.
1631:number of copies of
1145:fixed-parameter tractable
860:Sagan & Vatter (2006)
784:. This was known as the
766:, there is some constant
628:and any positive integer
577:with a natural action on
465:even and odd permutations
18:combinatorial mathematics
3855:, February 14-19, 2016,
3716:, June 27–July 1, 2016,
3688:Université Paris Diderot
3630:, St. Andrews, Scotland.
3586:, February 10–14, 2003,
3577:held annually since 2003
3513:Bousquet-Mélou, Mireille
1444:skew-merged permutations
1360:-PPM could be solved in
941:and another permutation
893:Computational complexity
644:...21 ⊕
348:, π avoids 5,2,7,4,...,4
300:Computer science origins
122:A case can be made that
3845:, May 29–June 3, 2005,
3640:, Dunedin, New Zealand.
3590:, Dunedin, New Zealand.
3522:Annals of Combinatorics
3398:Annals of Combinatorics
2431:10.1023/A:1015016625432
1936:, and that there exist
1573:{\displaystyle \sigma }
1269:{\displaystyle \sigma }
788:until it was proved by
786:Stanley–Wilf conjecture
677:sequence enumerating Av
632:, the permutations 12..
566:denotes the reverse of
3865:, November 4-9, 2018,
3788:University of Burgundy
3750:, Zürich, Switzerland.
3720:, Washington, DC, USA.
2528:10.1006/jcta.1997.2800
2008:corresponding to π is
2004:, who showed that the
1687:
1574:
1554:
1521:
1488:
1464:
1436:
1400:
1354:
1321:
1297:
1270:
1250:
1221:separable permutations
1213:
1189:
1161:
1137:
1063:
1043:
1023:
1003:
975:
955:
935:
911:
872:separable permutations
868:Burstein et al. (2011)
420:}, the abbreviation Av
290:
240:
196:
139:Erdős–Szekeres theorem
3875:, March 19-24, 2023,
3832:Georgetown University
3778:Valparaiso University
3758:Valparaiso University
3730:, Reykjavík, Iceland.
3656:, August 9–13, 2010,
3648:Università di Firenze
3620:, Reykjavík, Iceland.
3608:University of Florida
3243:: Article R5, 20 pp,
3201:Price, Alkes (1997),
2897:; Buss, Jonathan F.;
2244:Journal of Algorithms
2205:10.1145/800125.804058
2156:10.1145/321694.321704
1704:is nonincreasing for
1688:
1575:
1555:
1522:
1489:
1465:
1437:
1435:{\displaystyle O(kn)}
1401:
1355:
1322:
1298:
1271:
1251:
1214:
1190:
1162:
1143:, meaning that it is
1138:
1064:
1044:
1024:
1022:{\displaystyle \tau }
1004:
989:problem asks whether
976:
956:
936:
912:
910:{\displaystyle \tau }
826:of permutations is a
455:combinatorial classes
416:is a singleton, say {
360:,1, and 5,2,7,4,...,4
291:
241:
197:
41:), then π is said to
3920:Permutation patterns
3776:, June 20-24, 2022,
3770:, Glasgow, Scotland.
3746:, June 17–21, 2019,
3728:Reykjavík University
3726:, June 26–30, 2017,
3706:, June 15–19, 2015,
3680:, Glasgow, Scotland.
3676:, June 11–15, 2012,
3666:, June 20–24, 2011,
3646:, July 13–17, 2009,
3636:, June 16–20, 2008,
3626:, June 11–15, 2007,
3618:Reykjavík University
3616:, June 12–16, 2006,
3606:, March 7–11, 2005,
3326:: Article N1, 4 pp,
3278:Permutation Patterns
2649:Discrete Mathematics
2369:Discrete Mathematics
2198:, pp. 268–277,
2037:Combinatory Analysis
1835:Albert et al. (2002)
1721: − 3
1607:
1564:
1531:
1498:
1474:
1450:
1414:
1364:
1331:
1307:
1283:
1260:
1227:
1199:
1175:
1151:
1089:
1053:
1033:
1013:
1002:{\displaystyle \pi }
993:
965:
954:{\displaystyle \pi }
945:
925:
901:
897:Given a permutation
864:layered permutations
648:are Wilf-equivalent.
579:permutation matrices
308:'s consideration of
250:
206:
153:
3847:University of Haifa
3830:, March 7–8, 2015,
3736:, July 9–13, 2018,
3696:, July 7–11, 2014,
3638:University of Otago
3588:University of Otago
3141:10.46298/dmtcs.1308
2236:Rosenstiehl, Pierre
1982:Mahonian statistics
1958:consecutive pattern
836:generating function
754:In the late 1980s,
666:is of length four:
388:Enumerative origins
26:permutation pattern
3879:, Wadern, Germany.
3869:, Wadern, Germany.
3859:, Wadern, Germany.
3786:, July 3-7, 2023,
3748:Universität Zürich
3710:, London, England.
3686:, July 1–5, 2013,
3650:, Florence, Italy.
3596:, July 5–9, 2004,
3227:Albert, Michael H.
2319:Claesson, Anders;
2142:Journal of the ACM
2056:, Items 97 and 98.
2033:MacMahon, Percy A.
1870:conjectured to be
1857:conjectured to be
1844:conjectured to be
1683:
1677:
1625:
1570:
1550:
1539:
1517:
1506:
1484:
1460:
1432:
1396:
1350:
1339:
1317:
1293:
1266:
1246:
1235:
1209:
1185:
1157:
1133:
1059:
1039:
1019:
999:
971:
951:
931:
907:
814:, also known as a
478:In general, if |Av
286:
236:
192:
124:Percy MacMahon
3834:, Washington, DC.
3824:, Eau Claire, WI.
3738:Dartmouth College
3718:Howard University
3658:Dartmouth College
3295:978-0-521-72834-8
3101:978-3-642-10630-9
2958:978-1-61197-338-9
2561:-recursiveness",
2190:Pratt, Vaughan R.
2010:locally factorial
1879:
1878:
1678:
1669:
1648:
1640:
1632:
1610:
1584:Packing densities
1538:
1505:
1338:
1234:
1160:{\displaystyle k}
1062:{\displaystyle k}
1042:{\displaystyle n}
974:{\displaystyle k}
934:{\displaystyle n}
820:permutation class
806:Permutation class
752:
751:
384:characterizing”.
338:Vaughan Pratt
330:Robert Tarjan
34:one-line notation
3927:
3890:, maintained by
3877:Schloss Dagstuhl
3867:Schloss Dagstuhl
3857:Schloss Dagstuhl
3849:, Haifa, Israel.
3808:, Rochester, NY.
3790:, Dijon, France.
3690:, Paris, France.
3565:
3563:
3538:
3529:(3–4): 335–354,
3509:
3503:
3501:
3492:
3483:(1–2): 303–313,
3470:
3464:
3462:
3437:
3431:
3429:
3405:(3–4): 459–470,
3392:
3386:
3385:
3384:
3374:
3352:
3346:
3344:
3335:
3310:Arratia, Richard
3306:
3300:
3298:
3269:
3263:
3261:
3252:
3223:
3217:
3215:
3198:
3187:
3186:
3184:
3174:
3158:
3152:
3151:
3134:
3111:
3105:
3104:
3085:
3069:
3063:
3062:
3052:
3036:
3027:
3026:
3005:
2999:
2998:
2997:
2977:
2971:
2970:
2942:
2926:
2920:
2919:
2891:
2882:
2881:
2880:
2870:
2848:
2842:
2841:
2816:
2807:(4): 1074–1092,
2796:
2787:
2781:
2779:
2762:
2753:(1): 2346–2364,
2740:
2734:
2732:
2707:
2682:
2676:
2674:
2665:
2640:
2634:
2632:
2623:
2597:
2591:
2589:
2580:
2554:
2548:
2546:
2521:
2496:
2490:
2488:
2479:
2457:
2451:
2449:
2424:
2402:
2396:
2394:
2385:
2376:(1–3): 291–316,
2363:
2357:
2355:
2346:
2316:
2310:
2308:
2299:
2274:
2268:
2266:
2232:
2226:
2224:
2207:
2186:
2177:
2175:
2158:
2133:
2127:
2121:
2115:
2109:
2103:
2101:
2067:Knuth, Donald E.
2063:
2057:
2051:
2045:
2043:
2029:
2015:
2006:Schubert variety
1965:vincular pattern
1873:
1867: 2413
1860:
1854: 1342
1847:
1841: 1324
1831:
1829:
1827:
1826:
1823:
1820:
1811: 1243
1801:
1799:
1797:
1796:
1793:
1790:
1781: 2143
1771:
1754: 1432
1743: 1234
1729:
1722:
1720:
1719:
1692:
1690:
1689:
1684:
1679:
1676:
1675:
1674:
1661:
1653:
1649:
1646:
1641:
1639: in a
1638:
1633:
1630:
1627:
1624:
1579:
1577:
1576:
1571:
1559:
1557:
1556:
1551:
1540:
1536:
1526:
1524:
1523:
1518:
1507:
1503:
1493:
1491:
1490:
1485:
1483:
1482:
1469:
1467:
1466:
1461:
1459:
1458:
1441:
1439:
1438:
1433:
1405:
1403:
1402:
1397:
1392:
1391:
1382:
1381:
1359:
1357:
1356:
1351:
1340:
1336:
1326:
1324:
1323:
1318:
1316:
1315:
1302:
1300:
1299:
1294:
1292:
1291:
1275:
1273:
1272:
1267:
1255:
1253:
1252:
1247:
1236:
1232:
1218:
1216:
1215:
1210:
1208:
1207:
1194:
1192:
1191:
1186:
1184:
1183:
1166:
1164:
1163:
1158:
1147:with respect to
1142:
1140:
1139:
1134:
1126:
1125:
1112:
1111:
1068:
1066:
1065:
1060:
1048:
1046:
1045:
1040:
1028:
1026:
1025:
1020:
1009:is contained in
1008:
1006:
1005:
1000:
980:
978:
977:
972:
960:
958:
957:
952:
940:
938:
937:
932:
916:
914:
913:
908:
737: 1324
719: 1234
701: 1342
669:
610:and 312 ⊕
572:Dihedral group D
295:
293:
292:
287:
245:
243:
242:
237:
201:
199:
198:
193:
88: <
84: <
24:, a (classical)
3935:
3934:
3930:
3929:
3928:
3926:
3925:
3924:
3910:
3909:
3708:De Morgan House
3573:
3568:
3511:
3510:
3506:
3472:
3471:
3467:
3439:
3438:
3434:
3394:
3393:
3389:
3354:
3353:
3349:
3308:
3307:
3303:
3296:
3271:
3270:
3266:
3225:
3224:
3220:
3200:
3199:
3190:
3160:
3159:
3155:
3115:Albert, Michael
3113:
3112:
3108:
3102:
3071:
3070:
3066:
3038:
3037:
3030:
3018:(12): 430–433,
3007:
3006:
3002:
2979:
2978:
2974:
2959:
2928:
2927:
2923:
2895:Bose, Prosenjit
2893:
2892:
2885:
2850:
2849:
2845:
2794:
2789:
2788:
2784:
2742:
2741:
2737:
2684:
2683:
2679:
2642:
2641:
2637:
2599:
2598:
2594:
2556:
2555:
2551:
2498:
2497:
2493:
2459:
2458:
2454:
2404:
2403:
2399:
2365:
2364:
2360:
2318:
2317:
2313:
2276:
2275:
2271:
2234:
2233:
2229:
2188:
2187:
2180:
2135:
2134:
2130:
2122:
2118:
2110:
2106:
2083:
2065:
2064:
2060:
2054:MacMahon (1915)
2052:
2048:
2031:
2030:
2026:
2022:
2013:
1950:
1948:Generalizations
1902:
1896:
1872:≅ 0.10474
1871:
1859:≅ 0.19658
1858:
1845:
1824:
1821:
1818:
1817:
1815:
1814:
1794:
1791:
1788:
1787:
1785:
1784:
1758:
1735:packing density
1717:
1715:
1713:
1656:
1628:
1605:
1604:
1594:packing density
1586:
1562:
1561:
1529:
1528:
1496:
1495:
1472:
1471:
1448:
1447:
1412:
1411:
1383:
1373:
1362:
1361:
1329:
1328:
1305:
1304:
1281:
1280:
1258:
1257:
1225:
1224:
1197:
1196:
1173:
1172:
1149:
1148:
1103:
1092:
1087:
1086:
1051:
1050:
1031:
1030:
1011:
1010:
991:
990:
963:
962:
943:
942:
923:
922:
899:
898:
895:
852:Möbius function
844:
842:Möbius function
808:
802:
774:
756:Richard Stanley
681:
656:
594:Stankova (1994)
575:
540:
530:
520:
513:Wilf-equivalent
510:are said to be
492:
482:
447:
440:
434:
424:
412:. (In the case
402:
396:
390:
318:Catalan numbers
302:
248:
247:
246:or the pattern
204:
203:
151:
150:
132:Catalan numbers
120:
12:
11:
5:
3933:
3931:
3923:
3922:
3912:
3911:
3908:
3907:
3901:
3895:
3892:Michael Albert
3881:
3880:
3870:
3860:
3850:
3836:
3835:
3825:
3815:
3809:
3792:
3791:
3781:
3771:
3761:
3751:
3741:
3731:
3721:
3711:
3701:
3691:
3681:
3671:
3661:
3651:
3641:
3631:
3621:
3611:
3601:
3591:
3572:
3571:External links
3569:
3567:
3566:
3504:
3465:
3432:
3387:
3347:
3301:
3294:
3264:
3218:
3188:
3153:
3106:
3100:
3064:
3028:
3000:
2972:
2957:
2921:
2911:(5): 277–283,
2883:
2843:
2782:
2735:
2698:(2): 117–136,
2677:
2656:(2): 575–583,
2635:
2614:(1): 153–160,
2600:Marcus, Adam;
2592:
2571:(2): 257–285,
2549:
2512:(2): 257–272,
2491:
2470:(2): 133–149,
2452:
2415:(3): 271–290,
2397:
2358:
2337:: B60d, 30pp,
2321:Kitaev, Sergey
2311:
2290:(4): 383–406,
2278:Simion, Rodica
2269:
2250:(3): 375–390,
2240:Tarjan, Robert
2227:
2178:
2149:(2): 341–346,
2137:Tarjan, Robert
2128:
2116:
2104:
2081:
2058:
2046:
2023:
2021:
2018:
1993:barred pattern
1949:
1946:
1934:Euler's number
1898:Main article:
1895:
1892:
1877:
1876:
1874:
1868:
1864:
1863:
1861:
1855:
1851:
1850:
1848:
1842:
1838:
1837:
1832:
1812:
1808:
1807:
1802:
1782:
1778:
1777:
1772:
1755:
1751:
1750:
1747:
1744:
1740:
1739:
1736:
1733:
1694:
1693:
1682:
1673:
1668:
1665:
1660:
1652:
1644:
1636:
1623:
1620:
1617:
1613:
1585:
1582:
1569:
1549:
1546:
1543:
1516:
1513:
1510:
1481:
1457:
1431:
1428:
1425:
1422:
1419:
1395:
1390:
1386:
1380:
1376:
1372:
1369:
1349:
1346:
1343:
1314:
1290:
1265:
1245:
1242:
1239:
1206:
1182:
1156:
1132:
1129:
1124:
1121:
1118:
1115:
1110:
1106:
1102:
1099:
1095:
1058:
1038:
1018:
998:
970:
950:
930:
906:
894:
891:
843:
840:
804:Main article:
801:
800:Closed classes
798:
772:
750:
749:
746:
741:
738:
734:
733:
728:
723:
720:
716:
715:
710:
705:
702:
698:
697:
694:
688:
679:
675:
654:
650:
649:
619:
597:
573:
538:
528:
518:
490:
480:
475:for a survey.
445:
438:
432:
422:
400:
392:Main article:
389:
386:
301:
298:
285:
282:
279:
276:
273:
270:
267:
264:
261:
258:
255:
235:
232:
229:
226:
223:
220:
217:
214:
211:
191:
188:
185:
182:
179:
176:
173:
170:
167:
164:
161:
158:
119:
116:
13:
10:
9:
6:
4:
3:
2:
3932:
3921:
3918:
3917:
3915:
3905:
3902:
3899:
3896:
3893:
3889:
3886:
3885:
3884:
3883:Other links:
3878:
3874:
3871:
3868:
3864:
3861:
3858:
3854:
3851:
3848:
3844:
3841:
3840:
3839:
3833:
3829:
3826:
3823:
3819:
3816:
3813:
3810:
3807:
3803:
3800:
3799:
3798:
3796:
3789:
3785:
3782:
3779:
3775:
3772:
3769:
3765:
3762:
3759:
3755:
3752:
3749:
3745:
3742:
3739:
3735:
3732:
3729:
3725:
3722:
3719:
3715:
3712:
3709:
3705:
3702:
3699:
3695:
3692:
3689:
3685:
3682:
3679:
3675:
3672:
3669:
3665:
3662:
3659:
3655:
3652:
3649:
3645:
3642:
3639:
3635:
3632:
3629:
3625:
3622:
3619:
3615:
3612:
3609:
3605:
3602:
3599:
3595:
3592:
3589:
3585:
3582:
3581:
3580:
3578:
3570:
3562:
3558:
3554:
3550:
3546:
3542:
3537:
3532:
3528:
3524:
3523:
3518:
3517:Butler, Steve
3514:
3508:
3505:
3500:
3496:
3491:
3486:
3482:
3478:
3477:
3469:
3466:
3461:
3457:
3453:
3449:
3448:
3443:
3436:
3433:
3428:
3424:
3420:
3416:
3412:
3408:
3404:
3400:
3399:
3391:
3388:
3383:
3378:
3373:
3368:
3364:
3360:
3359:
3351:
3348:
3343:
3339:
3334:
3333:10.37236/1477
3329:
3325:
3321:
3320:
3315:
3311:
3305:
3302:
3297:
3291:
3287:
3283:
3279:
3275:
3268:
3265:
3260:
3256:
3251:
3250:10.37236/1622
3246:
3242:
3238:
3237:
3232:
3228:
3222:
3219:
3214:
3210:
3206:
3205:
3197:
3195:
3193:
3189:
3183:
3178:
3173:
3168:
3164:
3157:
3154:
3150:
3146:
3142:
3138:
3133:
3128:
3124:
3120:
3116:
3110:
3107:
3103:
3097:
3093:
3089:
3084:
3079:
3075:
3068:
3065:
3060:
3056:
3051:
3046:
3042:
3035:
3033:
3029:
3025:
3021:
3017:
3013:
3012:
3004:
3001:
2996:
2991:
2988:(2): 83–101,
2987:
2983:
2976:
2973:
2968:
2964:
2960:
2954:
2950:
2946:
2941:
2936:
2932:
2925:
2922:
2918:
2914:
2910:
2906:
2905:
2900:
2896:
2890:
2888:
2884:
2879:
2878:10.37236/8554
2874:
2869:
2864:
2860:
2856:
2855:
2847:
2844:
2840:
2836:
2832:
2828:
2824:
2820:
2815:
2810:
2806:
2802:
2801:
2793:
2786:
2783:
2778:
2774:
2770:
2766:
2761:
2756:
2752:
2748:
2747:
2739:
2736:
2731:
2727:
2723:
2719:
2715:
2711:
2706:
2701:
2697:
2693:
2692:
2687:
2681:
2678:
2673:
2669:
2664:
2659:
2655:
2651:
2650:
2645:
2644:Wilf, Herbert
2639:
2636:
2631:
2627:
2622:
2617:
2613:
2609:
2608:
2603:
2602:Tardos, Gábor
2596:
2593:
2588:
2584:
2579:
2574:
2570:
2566:
2565:
2560:
2553:
2550:
2545:
2541:
2537:
2533:
2529:
2525:
2520:
2515:
2511:
2507:
2506:
2501:
2495:
2492:
2487:
2483:
2478:
2473:
2469:
2465:
2464:
2456:
2453:
2448:
2444:
2440:
2436:
2432:
2428:
2423:
2418:
2414:
2410:
2409:
2401:
2398:
2393:
2389:
2384:
2379:
2375:
2371:
2370:
2362:
2359:
2354:
2350:
2345:
2340:
2336:
2332:
2331:
2326:
2322:
2315:
2312:
2307:
2303:
2298:
2293:
2289:
2285:
2284:
2279:
2273:
2270:
2265:
2261:
2257:
2253:
2249:
2245:
2241:
2237:
2231:
2228:
2223:
2219:
2215:
2211:
2206:
2201:
2197:
2196:
2191:
2185:
2183:
2179:
2174:
2170:
2166:
2162:
2157:
2152:
2148:
2144:
2143:
2138:
2132:
2129:
2125:
2120:
2117:
2113:
2108:
2105:
2100:
2096:
2092:
2088:
2084:
2082:0-201-89683-4
2078:
2074:
2073:
2068:
2062:
2059:
2055:
2050:
2047:
2042:
2038:
2034:
2028:
2025:
2019:
2017:
2011:
2007:
2003:
1998:
1994:
1989:
1987:
1983:
1979:
1975:
1971:
1966:
1961:
1959:
1955:
1947:
1945:
1943:
1939:
1935:
1931:
1927:
1923:
1919:
1915:
1911:
1907:
1901:
1894:Superpatterns
1893:
1891:
1889:
1884:
1875:
1869:
1866:
1865:
1862:
1856:
1853:
1852:
1849:
1846:≅ 0.244
1843:
1840:
1839:
1836:
1833:
1813:
1810:
1809:
1806:
1803:
1783:
1780:
1779:
1776:
1773:
1769:
1765:
1761:
1756:
1753:
1752:
1748:
1745:
1742:
1741:
1737:
1734:
1731:
1730:
1727:
1724:
1711:
1707:
1703:
1699:
1680:
1666:
1663:
1650:
1642:
1634:
1615:
1603:
1602:
1601:
1599:
1595:
1591:
1583:
1581:
1567:
1544:
1511:
1445:
1426:
1423:
1417:
1409:
1388:
1384:
1378:
1374:
1367:
1344:
1277:
1263:
1240:
1222:
1168:
1154:
1146:
1130:
1127:
1119:
1116:
1113:
1108:
1104:
1097:
1093:
1084:
1080:
1076:
1072:
1056:
1036:
1016:
996:
988:
984:
968:
948:
928:
920:
904:
892:
890:
888:
884:
880:
875:
873:
869:
865:
861:
857:
853:
849:
841:
839:
837:
833:
829:
825:
821:
817:
816:pattern class
813:
807:
799:
797:
795:
791:
787:
783:
779:
775:
770:such that |Av
769:
765:
761:
757:
748:unenumerated
747:
745:
742:
739:
736:
735:
732:
731:Gessel (1990)
729:
727:
724:
721:
718:
717:
714:
711:
709:
706:
703:
700:
699:
695:
692:
689:
686:
682:
676:
674:
671:
670:
667:
665:
661:
657:
647:
643:
639:
635:
631:
627:
623:
620:
617:
613:
609:
605:
601:
598:
595:
592:
591:
590:
588:
584:
580:
576:
569:
565:
561:
557:
553:
549:
545:
541:
535:
531:
525:
521:
515:
514:
509:
505:
501:
497:
493:
487:
483:
476:
474:
470:
466:
462:
458:
456:
452:
448:
441:
435:
429:
425:
419:
415:
411:
407:
403:
395:
387:
385:
381:
379:
375:
371:
367:
363:
359:
355:
351:
347:
343:
339:
335:
331:
327:
323:
319:
315:
311:
310:stack-sorting
307:
299:
297:
283:
280:
277:
274:
271:
268:
265:
262:
259:
256:
253:
233:
230:
227:
224:
221:
218:
215:
212:
209:
189:
186:
180:
177:
174:
165:
162:
159:
148:
144:
140:
135:
133:
129:
125:
118:Early results
117:
115:
113:
108:
106:
102:
99:
93:
91:
87:
83:
79:
75:
71:
67:
63:
59:
54:
52:
48:
44:
40:
35:
31:
27:
23:
19:
3882:
3837:
3793:
3574:
3536:math/0603617
3526:
3520:
3507:
3480:
3474:
3468:
3451:
3445:
3435:
3402:
3396:
3390:
3362:
3356:
3350:
3323:
3317:
3304:
3277:
3267:
3240:
3234:
3221:
3203:
3162:
3156:
3122:
3118:
3109:
3073:
3067:
3040:
3015:
3009:
3003:
2985:
2981:
2975:
2930:
2924:
2908:
2902:
2858:
2852:
2846:
2804:
2798:
2785:
2750:
2749:, Series A,
2744:
2738:
2705:math/0507485
2695:
2689:
2686:Sagan, Bruce
2680:
2653:
2647:
2638:
2611:
2610:, Series A,
2605:
2595:
2568:
2567:, Series A,
2562:
2558:
2552:
2519:math/9702223
2509:
2508:, Series A,
2503:
2500:Bóna, Miklós
2494:
2467:
2461:
2455:
2422:math/0103152
2412:
2406:
2400:
2373:
2367:
2361:
2334:
2328:
2314:
2287:
2281:
2272:
2247:
2243:
2230:
2193:
2146:
2140:
2131:
2124:Knuth (1968)
2119:
2112:Knuth (1968)
2107:
2070:
2061:
2049:
2036:
2027:
1992:
1990:
1973:
1969:
1964:
1962:
1957:
1953:
1951:
1941:
1937:
1929:
1925:
1921:
1917:
1913:
1910:superpattern
1909:
1905:
1903:
1900:Superpattern
1883:Price (1997)
1880:
1805:Price (1997)
1775:Price (1997)
1767:
1763:
1759:
1725:
1709:
1705:
1695:
1597:
1593:
1589:
1587:
1278:
1169:
1082:
1029:. When both
986:
982:
981:(called the
921:) of length
918:
917:(called the
896:
886:
882:
878:
876:
845:
835:
831:
823:
822:, or simply
819:
815:
812:closed class
811:
809:
794:Gábor Tardos
781:
777:
771:
767:
763:
760:Herbert Wilf
753:
684:
678:
672:
663:
659:
653:
651:
645:
641:
637:
633:
629:
625:
611:
607:
603:
586:
582:
567:
563:
559:
554:denotes the
551:
547:
543:
537:
533:
527:
523:
517:
512:
507:
503:
499:
495:
489:
485:
479:
477:
459:
450:
443:
437:
436:(123)| = |Av
431:
427:
421:
417:
413:
409:
405:
399:
397:
382:
369:
365:
361:
357:
356:−2,3,4
353:
349:
345:
325:
306:Donald Knuth
303:
146:
142:
136:
121:
111:
109:
104:
100:
97:
94:
89:
85:
81:
77:
73:
69:
65:
61:
57:
55:
46:
42:
25:
15:
3365:(1): 4–24,
2899:Lubiw, Anna
2800:Mathematika
1997:West (1993)
1986:Major index
1698:Fred Galvin
1079:linear time
1075:#P-complete
1071:NP-complete
856:Wilf (2002)
790:Adam Marcus
713:Bóna (1997)
546:)| for all
498:)| for all
51:subsequence
30:permutation
3372:1810.08252
3172:2107.10897
3132:1510.06051
3083:1511.01770
3050:1608.00529
2868:1812.05064
2814:1810.05449
2020:References
1762:− 12
1738:reference
961:of length
618:operation.
616:direct sum
442:(231)| =
105:occurrence
3213:304421853
2995:1301.0340
2940:1307.3073
2344:0805.1325
2099:155842391
1954:classical
1643:β
1635:β
1622:∞
1619:→
1568:σ
1545:σ
1264:σ
1241:σ
1128:⋅
1117:
1017:τ
997:π
949:π
905:τ
866:. Later,
693:reference
662:)| where
374:antichain
272:…
263:−
228:…
178:−
163:−
101:instance,
96:called a
3914:Category
3561:31236417
3312:(1999),
3209:ProQuest
2839:53366318
2777:13978488
2730:11283347
2544:18352890
2447:13921676
2323:(2008),
2222:15740957
2173:13608929
2069:(1968),
2035:(1915),
1928:, where
1757:root of
1749:trivial
1708:≥
780:)| <
636:⊕
550:, where
536:)| = |Av
526:)| = |Av
488:)| = |Av
49:if some
3553:2376109
3499:1235186
3460:1758852
3427:2021533
3419:2376116
3342:1710623
3259:1887086
3149:5827603
2967:1846959
2831:3992365
2769:2834180
2722:2259013
2672:1935750
2630:2063960
2587:1041448
2536:1485138
2486:2290807
2439:1900628
2392:1297387
2353:2465405
2306:0829358
2264:0756164
2214:0489115
2165:0298803
2091:0286317
1970:valleys
1830:= 0.375
1828:
1816:
1800:= 0.375
1798:
1786:
1716:√
1590:optimal
985:), the
983:pattern
828:downset
744:A061552
726:A005802
708:A022558
556:inverse
502:, then
340: (
332: (
126: (
47:pattern
45:σ as a
43:contain
3559:
3551:
3497:
3458:
3425:
3417:
3340:
3292:
3257:
3211:
3147:
3098:
2965:
2955:
2933:: 20.
2837:
2829:
2775:
2767:
2728:
2720:
2670:
2628:
2585:
2542:
2534:
2484:
2445:
2437:
2390:
2351:
2304:
2262:
2220:
2212:
2171:
2163:
2097:
2089:
2079:
1408:Albert
1406:time.
1171:class
449:, the
322:deques
64:, and
3557:S2CID
3531:arXiv
3423:S2CID
3367:arXiv
3167:arXiv
3145:S2CID
3127:arXiv
3125:(2),
3078:arXiv
3045:arXiv
2990:arXiv
2963:S2CID
2935:arXiv
2863:arXiv
2835:S2CID
2809:arXiv
2795:(PDF)
2773:S2CID
2726:S2CID
2700:arXiv
2540:S2CID
2514:arXiv
2443:S2CID
2417:arXiv
2339:arXiv
2218:S2CID
2169:S2CID
1974:peaks
1766:+ 156
1702:limit
1081:when
848:poset
832:basis
824:class
314:stack
112:avoid
98:copy,
3290:ISBN
3096:ISBN
2953:ISBN
2095:OCLC
2077:ISBN
2016:54.
1512:4321
1049:and
919:text
792:and
758:and
691:OEIS
640:and
585:and
562:and
506:and
368:,1,4
364:+3,4
352:+1,4
342:1973
334:1972
145:and
128:1915
20:and
3541:doi
3485:doi
3481:117
3407:doi
3377:doi
3363:128
3328:doi
3282:doi
3245:doi
3177:doi
3137:doi
3088:doi
3055:doi
3020:doi
3016:113
2945:doi
2913:doi
2873:doi
2819:doi
2755:doi
2751:118
2710:doi
2658:doi
2654:257
2616:doi
2612:107
2573:doi
2524:doi
2472:doi
2427:doi
2378:doi
2374:132
2292:doi
2252:doi
2200:doi
2151:doi
1612:lim
1600:as
1345:321
1114:log
589:):
587:231
583:123
558:of
103:or
76:...
72:...
16:In
3916::
3579::
3555:,
3549:MR
3547:,
3539:,
3527:11
3525:,
3515:;
3495:MR
3493:,
3479:,
3456:MR
3452:44
3450:,
3444:,
3421:,
3415:MR
3413:,
3403:11
3401:,
3375:,
3361:,
3338:MR
3336:,
3322:,
3316:,
3288:,
3255:MR
3253:,
3239:,
3233:,
3191:^
3175:.
3143:,
3135:,
3123:18
3121:,
3094:,
3086:,
3053:.
3031:^
3014:,
2986:24
2984:,
2961:.
2951:.
2943:.
2909:65
2907:,
2886:^
2871:,
2859:27
2857:,
2833:,
2827:MR
2825:,
2817:,
2805:65
2803:,
2797:,
2771:,
2765:MR
2763:,
2724:,
2718:MR
2716:,
2708:,
2696:24
2694:,
2668:MR
2666:,
2652:,
2626:MR
2624:,
2583:MR
2581:,
2569:53
2538:,
2532:MR
2530:,
2522:,
2510:80
2482:MR
2480:,
2468:38
2466:,
2441:,
2435:MR
2433:,
2425:,
2413:15
2411:,
2388:MR
2386:,
2372:,
2349:MR
2347:,
2335:60
2333:,
2327:,
2302:MR
2300:,
2286:,
2260:MR
2258:,
2246:,
2238:;
2216:,
2210:MR
2208:,
2181:^
2167:,
2161:MR
2159:,
2147:19
2145:,
2093:,
2087:MR
2085:,
1960:.
1904:A
1537:Av
1504:Av
1337:Av
1233:Av
1167:.
889:.
874:.
818:,
810:A
796:.
457:.
296:.
134:.
60:,
39:pi
3894:.
3564:.
3543::
3533::
3502:.
3487::
3463:.
3430:.
3409::
3379::
3369::
3345:.
3330::
3324:6
3299:.
3284::
3262:.
3247::
3241:9
3216:.
3185:.
3179::
3169::
3139::
3129::
3090::
3080::
3061:.
3057::
3047::
3022::
2992::
2969:.
2947::
2937::
2915::
2875::
2865::
2821::
2811::
2780:.
2757::
2733:.
2712::
2702::
2675:.
2660::
2633:.
2618::
2590:.
2575::
2559:P
2547:.
2526::
2516::
2489:.
2474::
2450:.
2429::
2419::
2395:.
2380::
2356:.
2341::
2309:.
2294::
2288:6
2267:.
2254::
2248:5
2225:.
2202::
2176:.
2153::
2102:.
2044:.
2014:3
1942:k
1938:k
1930:e
1926:e
1924:/
1922:k
1918:k
1914:k
1908:-
1906:k
1825:8
1822:/
1819:3
1795:8
1792:/
1789:3
1768:x
1764:x
1760:x
1746:1
1732:β
1718:3
1714:2
1710:k
1706:n
1681:.
1672:)
1667:k
1664:n
1659:(
1651:n
1616:n
1598:k
1548:)
1542:(
1515:)
1509:(
1480:C
1456:C
1430:)
1427:n
1424:k
1421:(
1418:O
1394:)
1389:6
1385:n
1379:2
1375:k
1371:(
1368:O
1348:)
1342:(
1313:C
1289:C
1244:)
1238:(
1205:C
1181:C
1155:k
1131:n
1123:)
1120:k
1109:2
1105:k
1101:(
1098:O
1094:2
1083:k
1057:k
1037:n
969:k
929:n
887:n
883:n
879:n
782:K
778:β
776:(
773:n
768:K
764:β
687:)
685:β
683:(
680:n
673:β
664:β
660:β
658:(
655:n
646:β
642:m
638:β
634:m
630:m
626:β
612:β
608:β
604:β
574:8
568:β
564:β
560:β
552:β
548:n
544:β
542:(
539:n
534:β
532:(
529:n
524:β
522:(
519:n
508:σ
504:β
500:n
496:σ
494:(
491:n
486:β
484:(
481:n
451:n
446:n
444:C
439:n
433:n
428:β
426:(
423:n
418:β
414:B
410:B
406:n
401:n
370:k
366:k
362:k
358:k
354:k
350:k
346:k
326:n
284:1
281:,
278:2
275:,
269:,
266:1
260:b
257:,
254:b
234:a
231:,
225:,
222:3
219:,
216:2
213:,
210:1
190:1
187:+
184:)
181:1
175:b
172:(
169:)
166:1
160:a
157:(
147:b
143:a
90:z
86:x
82:y
78:z
74:y
70:x
66:z
62:y
58:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.