An Assortment of Problems in Permutation Patterns: Unimodality, Equivalence, Derangements, and Sorting Vincent Vatter Abstract We collect open problems in permutation patterns on four themes: rank-unimodality in the permutation pattern poset, Wilf-equivalence and shape-Wilf-equivalence, the enumeration of derangements in permutation classes, and sorting by stacks in series, generalized stacks, and restricted containers ( 𝒞 \mathcal{C} -machines). \newpagestyle main[ ] \headrule \sethead [ \usepage ][][] An Assortment of Problems in Permutation Patterns \usepage 1. Introduction This paper accompanies a talk I gave at the pre-conference workshop for early career researchers at Permutation Patterns 2025 , the 23rd year of the conference series, held at the University of St Andrews and organized by Christian Bean and Ruth Hoffmann. It is not a list of the best-known or most difficult open problems in permutation patterns, but simply an assortment of problems on a few themes: problems I have encountered, wondered about, or been asked about. Many are of the “someone really ought to
” variety. A few are folklore, and some may be trivial. This is not meant as a roadmap for the field; describing what I feel are the deepest or most important open problems would require a different approach and considerably more buildup. Think of this instead as a collection of interesting attractions that do not take too long to reach. The best-known open problem in the field is surely the enumeration of 1324 -avoiding permutations, sequence A061552 in the OEIS [ 71 ] . This one is easy to reach, but many have looked and progress has been hard to come by. Asked why, Zeilberger replied, “Because life is hard . The few combinatorial objects that we can count exactly are the trivial ones” [ 64 ] (emphasis in original). There are, in any case, plenty of places to read more about this conundrum [ 67 , 35 , 22 , 54 , 23 , 40 , 38 , 15 , 37 , 14 ] . We have nothing new to add about this problem, and so turn to areas that seem more tractable, or at least where we have less evidence of intractability. The primary venue for results in permutation patterns, and for the exchange of open problems, has been the Permutation Patterns conference series, founded in 2003 by Michael Albert and Michael Atkinson at the University of Otago in Dunedin, New Zealand. Atkinson, who introduced Albert to the subject [ 65 ] , drew many of the field’s current researchers into permutation patterns; his retirement was honored at Permutation Patterns 2013 . Albert and Atkinson, and the conference series they founded, have shaped the research agenda considerably, and the conference’s tradition of open problems sessions has been particularly influential. For his part, Albert became a central figure in permutation patterns, known for his computational and collaborative approach to the subject, and retired in 2024. In this spirit, many of the problems here beg for computation, either because data is the goal, or just to better illuminate the path forward. There are earlier collections of open problems that the reader may also find valuable. Wilf, widely regarded as a founder of the field and the plenary speaker at the inaugural Permutation Patterns conference in 2003, wrote a survey in 1999 [ 98 ] at an early stage in its development; I particularly enjoyed reading it as a graduate student. In that survey, Wilf expressed doubt about the Stanley–Wilf conjecture due to recent results of Alon and Friedgut [ 3 ] ; his doubt was proved wrong a few years later when Marcus and Tardos [ 66 ] proved it. Wilf also recounted Stanley’s skepticism about the Noonan–Zeilberger conjecture [ 70 ] that every finitely based permutation class has a D-finite generating function; that skepticism was vindicated many years later when Garrabrant and Pak [ 49 ] disproved the conjecture. Another valuable resource is SteingrĂ­msson’s 2013 survey [ 89 ] , which covers a broad range of topics, including the Möbius function of the permutation pattern poset, topological properties of intervals, vincular and mesh patterns, and the structure of growth rates. SteingrĂ­msson is himself a leader in the field who has trained many of its current researchers; he delivered the plenary address at Permutation Patterns 2009 . For readers seeking broader introductions to permutation patterns, several general references are available. Kitaev’s Patterns in Permutations and Words [ 56 ] is a comprehensive compendium of the field. BĂłna’s undergraduate textbook A Walk Through Combinatorics [ 24 ] contains a very accessible introduction to the area, while his monograph Combinatorics of Permutations [ 25 ] treats the subject in greater depth. Finally, I can’t help but recommend my own survey [ 94 ] that appears in the Handbook of Enumerative Combinatorics . The remainder of the paper is organized as follows. Section 2 concerns rank-unimodality of intervals in the permutation pattern poset. Section 3 discusses symmetries and Wilf-equivalence. Section 4 addresses the enumeration of derangements in permutation classes. Section 5 looks at sorting machines. Below, we collect the basic definitions and offer some remarks on permutations as relational structures. Basic definitions The basic notions of permutation patterns are easily stated. With apologies to those who view permutations as elements of a Coxeter group (Tenner [ 92 ] ), we use the term length to mean the number of entries in a permutation, which we denote by |\pi| . We identify a permutation \pi with its plot : the set of points \{(i,\pi(i))\} in the plane. When we speak of an entry being to the left or right of, or above or below, another entry, we refer to their relative positions in the plot. Similarly, an entry lies to the southeast of another if it is both to the right and below, and so on for the other cardinal directions. \sim \leq Figure 1: The permutation \sigma=32514 (left) is contained in \pi=362957184 (right). The circled entries in \pi form the subsequence 32918 , which is order-isomorphic to \sigma . The permutation \pi avoids 4321 because it has no decreasing subsequence of length four. A permutation \sigma is contained in \pi , written \sigma\leq\pi , if \pi has a subsequence that is order-isomorphic to \sigma , meaning its entries appear in the same relative order; otherwise \pi avoids \sigma . In terms of plots, \sigma\leq\pi means that some selection of points from the plot of \pi , when rescaled, yields the plot of \sigma . Figure 1 illustrates these definitions. This containment relation is a partial order, and we refer to it as the permutation pattern order . A permutation class is a downset (or order ideal) in this poset: a set \mathcal{C} of permutations such that if \pi\in\mathcal{C} and \sigma\leq\pi , then \sigma\in\mathcal{C} . We denote by \mathcal{C}_{n} the set of permutations of length n in a class \mathcal{C} . Every permutation class \mathcal{C} is characterized by its basis , the set of minimal permutations not in \mathcal{C} . We write \operatorname{Av}(B) for the class of permutations avoiding every element of B . The basis of a class is necessarily an antichain (a set of pairwise incomparable permutations), and since the permutation pattern order contains infinite antichains, bases can be infinite. Permutations as relational structures The study of permutation patterns fits naturally into the broader combinatorics of relational structures. In terms of the plot, a permutation is a set of n points equipped with two total orders: the left-to-right order (by x -coordinate) and the bottom-to-top order (by y -coordinate). As Cameron [ 31 ] observes, this perspective clarifies what it means for one permutation to be contained in another: containment is simply the induced substructure relation, the same notion studied in the context of graphs (induced subgraphs), posets (induced subposets), integer partitions (Young’s lattice), and other combinatorial objects. This point of view will be relevant in the next section, where we compare unimodality results for permutations with analogous results for partitions and words. In most of those cases, the containment order is the natural one for relational structures of that type, and the questions (and answers) turn out to be surprisingly different. 2. Unimodality We begin with what is perhaps the easiest of these problems to state, though it may well be among the hardest to prove. A finite sequence a_{0},a_{1},\dots,a_{n} is said to be unimodal if there exists an index k such that a_{0}\leq a_{1}\leq\cdots\leq a_{k}\geq\cdots\geq a_{n}; that is, the sequence weakly increases to its maximum and then weakly decreases. A polynomial is said to be unimodal if its sequence of coefficients is unimodal. There are scores of unresolved unimodality questions in combinatorics and algebra; for a sample, the reader is referred to Stanley’s 1986 survey [ 87 ] , many of whose conjectures remain open. Given a permutation \pi of length n , let a_{k} denote the number of permutations of length k contained in \pi . Is the sequence a_{0},a_{1},\dots,a_{n} necessarily unimodal? To state this in a more refined form, we recall a few definitions. The set of all permutations contained in a given permutation \pi forms, under the containment order, a principal downset (also called a principal order ideal ). This is a ranked poset, with the rank of a permutation given by its length. A ranked poset is said to be rank-unimodal if the sequence counting the number of elements at each rank is unimodal. Conjecture 2.1 . Every principal downset in the permutation pattern poset is rank-unimodal. This phenomenon may have first been noted in the permutation pattern context by Murphy, who wrote at the end of his 2002 thesis [ 69 , p. 348] , emphasis added: There exists a program that takes a permutation of arbitrary length (usually about 24) and returns the set of all permutations involved in it, sorted by length. This is a simple but somewhat expensive way of finding the basis of the closure of a given permutation or set of permutations. The nicest thing about the program is the waisted shape of the output. Here is the number of permutations of each length in one permutation of length 17: 1,\ 1,\ 2,\ 5,\ 14,\ 36,\ 87,\ 210,\ 486,\ 927,\ 1315,\ 1348,\ 1005,\ 549,\ 218,\ 61,\ 11,\ 1. We may go further and ask whether all intervals in this poset are rank-unimodal. The interval [\sigma,\pi] is the set of all permutations \tau satisfying \sigma\leq\tau\leq\pi . It was in this generality that McNamara and SteingrĂ­msson posed the following conjecture, which subsumes Conjecture 2.1 . Conjecture 2.2 (McNamara and SteingrĂ­msson [ 68 , Conjecture 9.4] ) . Every interval in the permutation pattern poset is rank-unimodal. Analogous structures Before surveying what is known for the permutation pattern poset, we briefly consider analogous questions for other combinatorial structures. The picture that emerges is mixed: rank-unimodality holds in some settings but fails in others, which leaves the permutation case genuinely uncertain. In the consecutive pattern poset on permutations, rank-unimodality of intervals was established by Elizalde and McNamara [ 42 ] . However, their proof relies on the particularly constrained nature of consecutive containment (every permutation covers at most two others in this order) and does not appear to shed light on the standard (not-necessarily-consecutive) permutation pattern order. For integer partitions, the situation is murkier. The containment order on partitions is defined by {\mu\leq\lambda} if the Ferrers diagram of \mu fits inside that of \lambda ; equivalently, if \mu_{i}\leq\lambda_{i} for all i , padding with zeros as needed. This order makes the set of all partitions into a distributive lattice, called Young’s lattice . The principal downset generated by the m\times n rectangular partition (m,m,\dots,m) consisting of n parts each equal to m is denoted by L(m,n) , and its rank-generating function is a Gaussian polynomial. Gaussian polynomials have been known to be unimodal since the mid-nineteenth century, although a combinatorial proof was not given until O’Hara [ 72 ] in 1990, later exposited colorfully by Zeilberger [ 99 ] . One might hope that all principal downsets in Young’s lattice are rank-unimodal. Indeed, in 1986 Pouzet and Rosenberg [ 73 , p. 367] asked something far more general: are principal downsets in the natural ordering on any type of finite relational structures rank-unimodal? This was answered in the negative only a year later by Stanton [ 88 ] , who exhibited a non-unimodal principal downset in Young’s lattice. The partition (8,8,4,4) has rank sequence 1,\ 1,\ 2,\ 3,\ 5,\ 6,\ 9,\ 11,\ 15,\ 17,\ 21,\ 23,\ 27,\ 28,\ \underline{31,\ 30,\ 31},\ 27,\ 24,\ 18,\ 14,\ 8,\ 5,\ 2,\ 1. Stanton’s counterexample for integer partitions also precludes any thoughts of a graph analogue of Conjecture 2.1 , because it shows that the enumeration of induced subgraphs of the graph K_{8}\cup K_{8}\cup K_{4}\cup K_{4} is not unimodal. Although the answer to their question was negative, Pouzet and Rosenberg [ 73 , Corollary 2.11] did establish what might be called the “first half” of rank-unimodality: in any principal downset of a finite relational structure, the rank sequence is weakly increasing up to at least the middle rank. Combined with the symmetry of Young’s lattice, this gives another proof of the unimodality of the Gaussian polynomials. Specialized to permutations, it guarantees that the rank sequence of any principal downset in the permutation pattern poset increases up to at least half its length. Words over a finite alphabet under the subword order are much better behaved. Chase [ 32 ] proved that principal downsets are not merely rank-unimodal but rank-log-concave, a stronger property we now define. Log-concavity A sequence a_{0},a_{1},\dots,a_{n} of nonnegative terms is said to be log-concave if {a_{k}^{2}\geq a_{k-1}a_{k+1}} for all {1\leq k\leq n-1} , and a polynomial p(x)=a_{0}+a_{1}x+\cdots+a_{n}x^{n} is log-concave if its sequence of coefficients is log-concave. For positive sequences, log-concavity implies unimodality because it shows that the ratios a_{k}/a_{k-1} are weakly decreasing, so once this ratio drops below 1 , it remains below 1 . We cannot hope for log-concavity in the permutation pattern poset. The rank sequence of every nontrivial downset begins 1,1,2,\dots , but 1^{2}<1\cdot 2 so these sequences are not log-concave. Even ignoring the empty permutation, sequences beginning 1,2,5 or 1,2,6 (both common) fail log-concavity because 2^{2}<1\cdot 5 . Nevertheless, log-concavity can play a key role in establishing unimodality, via the following classical result due to Ibragimov [ 52 ] and Keilson and Gerber [ 55 ] . 1 1 1 It should be remarked that the product of two unimodal polynomials is not necessarily unimodal. For example, 1+x+3x^{2} is unimodal but (1+x+3x^{2})^{2}=1+2x+7x^{2}+6x^{3}+9x^{4} is not. Proposition 2.3 . A polynomial p(x) with positive coefficients is log-concave if and only if p(x)q(x) is unimodal for every unimodal polynomial q(x) . Layered permutations and compositions One might hope that the conjecture is at least resolved for layered permutations, a particularly tractable permutation class. We briefly recall their definition. The direct sum , or simply sum , of permutations \pi of length m and \sigma of length n is the permutation \pi\oplus\sigma of length {m+n} defined by (\pi\oplus\sigma)(i)\;=\;\begin{cases}\pi(i)&\text{for }1\leq i\leq m,\\ \sigma(i-m)+m&\text{for }m+1\leq i\leq m+n.\end{cases} Visually, the plot of \pi\oplus\sigma places the plot of \sigma above and to the right of the plot of \pi . The operation is associative, so expressions like \pi\oplus\sigma\oplus\tau do not require parentheses. A permutation is layered if it can be expressed as a sum of decreasing permutations; equivalently, the layered permutations are precisely \operatorname{Av}(231,312) . Every layered permutation has a unique decomposition \pi=\delta_{1}\oplus\delta_{2}\oplus\cdots\oplus\delta_{k} where each \delta_{i} is a decreasing permutation, and so layered permutations are in bijection with compositions: the composition c=c(1)c(2)\cdots c(k) corresponds to the layered permutation with consecutive decreasing layers of lengths c(1) , c(2) , \dots , c(k) . For example, the composition (3,1,4) corresponds to the layered permutation 321\oplus 1\oplus 4321=321\,4\,8765 . Under this bijection, the pattern containment order on layered permutations corresponds to the (generalized) subword order on compositions. Concretely, a composition u=u(1)\cdots u(k) with k parts is a subword of a composition w with \ell parts if there exist indices 1\leq i_{1}i ) is the same for 132 -avoiders and 321 -avoiders. Elizalde and Pak [ 43 ] later gave a bijective proof of this result. 5 5 5 The chronology here is unusual: Elizalde and Pak’s bijective paper appeared in 2004, while Elizalde’s initial result, though presented at FPSAC 2003 , was not formally published until 2011, in the Zeilberger Festschrift volume of the Electronic Journal of Combinatorics . For \beta\in\{231,312\} , the \beta -avoiding derangements are counted by A258041 : 0,\ 1,\ 1,\ 4,\ 10,\ 31,\ 94,\ 303,\ 986,\ 3284,\ 11099,\ 38024,\ \dots. Robertson, Saracino, and Zeilberger compute the first eight terms of this sequence [ 78 , Table 3] , and prove [ 78 , Theorem 7.1] that there are strictly fewer 231 -avoiding derangements than 132 -avoiding derangements of each length n\geq 3 (one might skip ahead to Figure 4 ; it’s not even close). Elizalde [ 44 , Theorem 3.7] gives a continued fraction expression for the generating function for 312 -avoiding permutations according to the number of fixed points. 6 6 6 Given the generality of the continued fraction of Blitvić and SteingrĂ­msson [ 17 ] , one might hope it could enumerate these permutations. It can be specialized to count 231 -avoiding permutations, or to count derangements, but not to count 231 -avoiding derangements, nor any of the other pattern-avoiding derangements considered in this section. This leaves the case of 123 -avoiding derangements. Here the sequence begins 0,\ 1,\ 2,\ 7,\ 20,\ 66,\ 218,\ 725,\ 2538,\ 8646,\ 31118,\ 108430,\ \dots. This is sequence A318232 in the OEIS, and that entry references the work of Fu, Tang, Han, and Zeng [ 47 ] . They define G_{n}(t)=\sum_{\pi}t^{\mathsf{exc}\,\pi}, where the sum is over 123 -avoiding derangements of length n and \mathsf{exc}\,\pi denotes the number of excedances of \pi . In particular, G_{n}(1) is the number of 123 -avoiding derangements. Fu, Tang, Han, and Zeng also consider G_{n}(-1) , for which they have a conjecture [ 47 , Conjecture 5.11] . For odd n , we always have G_{n}(-1)=0 : the reverse-complement symmetry preserves 123 -avoidance and, for derangements, exchanges excedances with non-excedances. Thus if \pi has k excedances, its reverse-complement has n-k , and when n is odd these have opposite parities, so the contributions cancel. For even n , they conjecture that (-1)^{n/2}G_{n}(-1) is positive. This amounts to a statement about whether, for a given even length, there are more 123 -avoiding derangements with an even number of excedances or with an odd number. A 123 -avoiding permutation can have at most two fixed points. Elizalde [ 44 , Corollary 3.2] shows that the enumeration of 123 -avoiding permutations by number of fixed points reduces to enumerating those with exactly two fixed points, as the other cases can be computed from this count. He gives a formula [ 44 , Theorem 3.3] for the number of 123 -avoiding permutations with exactly two fixed points, but it involves a quadruple sum. Using this formula, Elizalde [ 44 , Theorem 3.4] proves that for n\geq 4 , there are strictly more 123 -avoiding derangements than 132 -avoiding derangements of length n (see Figure 4 ). This inequality had been observed based on the data for 4\leq n\leq 8 by Robertson, Saracino, and Zeilberger, and Elizalde reports that it was conjectured independently by BĂłna and Guibert. A closed-form enumeration remains elusive. Elizalde [ 44 , p. 8] notes that he has “not been able to find a satisfactory expression” for the generating function, although he expresses hope [ 44 , p. 39] that a simpler formula than his Theorem 3.3 exists. Birmajer, Gil, Tirrell, and Weiner [ 16 , Conjecture A.2] conjecture a simpler formula for the number of 123 -avoiding permutations with two fixed points, parameterized by the distance between the fixed points; if proved, this would reduce Elizalde’s quadruple sum to a double sum. The two formulas agree through n=200 . Using the first 200 terms, Pantone (personal communication) was able to fit a linear differential equation to the generating function, suggesting that it is D-finite. Unfortunately, that differential equation is quite unwieldy (far too long to include here). It remains possible that a nicer expression exists in the form of a continued fraction, as Elizalde [ 44 , Theorem 3.7] found for 231 -avoiding permutations according to the number of fixed points. Proportions 10 20 30 40 50 60 70 80 90 100 1 0 \nicefrac{{1}}{{4}} \nicefrac{{1}}{{2}} \nicefrac{{3}}{{4}} 1 \beta=231 \beta=132 \beta=123 Figure 4: The proportion of \beta -avoiding permutations that are derangements, by length. Figure 4 plots the proportion of \beta -avoiding permutations of length n that are derangements, for each of the three symmetry classes of patterns of length three, with n ranging from 1 to 100 . The figure illustrates the comparisons established above: 123 -avoiding permutations are more likely to be derangements than 132 -avoiding permutations, which in turn are more likely to be derangements than 231 -avoiding permutations. It is tempting to observe that this ordering is reversed from the number of fixed points in the patterns themselves; patterns with more fixed points appear to be avoided by proportionally more derangements. Curious. For {\beta\in\{132,213,321\}} , we have the Robertson, Saracino, and Zeilberger result that the \beta -avoiding derangements are counted by Fine’s sequence. Denoting these numbers by F_{n} , they satisfy C_{n}=2F_{n}+F_{n-1} , where C_{n} denotes the Catalan numbers, so C_{n}/F_{n}=2+F_{n-1}/F_{n} . Since the growth rate of Fine’s sequence is also 4 like the Catalan numbers, we see that C_{n}/F_{n}\to\nicefrac{{9}}{{4}} , and thus F_{n}/C_{n}\to\nicefrac{{4}}{{9}} . For \beta=123 , Figure 4 suggests that the number of 123 -avoiding derangements grows like \delta C_{n} for some limiting proportion \delta\geq\nicefrac{{1}}{{2}} , where C_{n} denotes the n th Catalan number. Assuming this asymptotic form and using the first 200 terms of the enumeration, Pantone (personal communication) applied the method of differential approximants to conjecture that the limiting proportion is precisely \nicefrac{{9}}{{16}} . Conjecture 4.1 (Pantone) . The limiting proportion of derangements among 123 -avoiding permutations is equal to \nicefrac{{9}}{{16}} . For \beta\in\{231,312\} , Figure 4 and numerical experimentation suggest that the proportion tends to 0 . Question 4.2 . Is the limiting proportion of derangements among 231 -avoiding permutations equal to 0 ? These observations suggest broader questions. For a permutation class \mathcal{C} , let \mathcal{C}^{\circ} denote the set of derangements in \mathcal{C} . Question 4.3 . Does the ratio |\mathcal{C}^{\circ}_{n}|/|\mathcal{C}_{n}| converge for every permutation class \mathcal{C} ? Numerous follow-up questions suggest themselves. For the class of all permutations, the limit is of course \nicefrac{{1}}{{e}} . What values in [0,1] are achievable? The case of \operatorname{Av}(132) shows that these limits can be greater than \nicefrac{{1}}{{e}} , but how much greater? Is there a largest possible limit strictly less than 1 ? For which classes is this limit 0 ? Separable derangements The skew sum of permutations \sigma of length m and \tau of length n is the permutation \sigma\ominus\tau of length {m+n} defined by (\sigma\ominus\tau)(i)\;=\;\begin{cases}\sigma(i)+n&\text{for }1\leq i\leq m,\\ \tau(i-m)&\text{for }m+1\leq i\leq m+n.\end{cases} Visually, the plot of \sigma\ominus\tau places the plot of \tau below and to the right of the plot of \sigma . A permutation is separable if it can be built from the singleton permutation 1 by repeated application of sum and skew sum. Bose, Buss, and Lubiw [ 26 ] gave the separable permutations their name and showed that they are precisely \operatorname{Av}(2413,3142) . Notable subclasses include \operatorname{Av}(132) and \operatorname{Av}(231) , which we have just discussed, as well as the layered permutations discussed earlier. The separable permutations of length n are counted by the large Schröder numbers ( A006318 ): 1,\ 2,\ 6,\ 22,\ 90,\ 394,\ 1806,\ 8558,\ 41586,\ 206098,\ 1037718,\ 5293446,\ \dots. This enumeration was first established by Shapiro and Stephens [ 81 ] in 1991, though they worked with the recursive definition via sums and skew sums. This was before Bose, Buss, and Lubiw had identified the basis \{2413,3142\} , which led to an amusing historical coincidence: As West [ 97 ] reports, Shapiro and Getu later conjectured that the large Schröder numbers also count \operatorname{Av}(2413,3142) , not realizing Shapiro had already proved this himself, albeit in a disguised form. West [ 97 ] gave a proof in 1995. 7 7 7 West wrote that this was “the first non-trivial enumerative result to be obtained for any problem involving forbidden subsequences of length k\geq 4 .” This overlooks Gessel’s 1990 paper [ 50 ] , which gives an explicit formula for 1234 -avoiding permutations. Since [ 50 ] is cited in [ 97 ] , this is a puzzling omission; perhaps West meant the first involving non-monotone patterns, or more than one pattern. Stankova [ 84 ] then gave the much more natural proof, decomposing these permutations into sums and skew sums, which brings the story full circle to Shapiro and Stephens. For classes with only finitely many simple permutations (a term we won’t define here), such as the separable permutations, Brignall, Huczynska, and Vatter [ 29 ] show how to systematically obtain algebraic equations for the generating functions of various natural subsets: the alternating permutations, the even permutations, the Dumont permutations of the first kind, the involutions, and many others. However, their method does not apply to derangements. The obstacle is that being a derangement does not lie in a finite “query-complete set of properties” (in the sense of that paper). The proof of this fact uses displacement sets, D(\pi)=\{\pi(i)-i:i\in[n]\} , so a permutation \pi is a derangement if and only if 0\notin D(\pi) . While D(\pi\oplus\sigma)=D(\pi)\cup D(\sigma) , whether a skew sum \pi\ominus\sigma is a derangement depends on the interaction between D(\pi) and D(\sigma) , and so permutations with different displacement sets must be tracked separately. Thus despite the well-understood structure of separable permutations, no explicit expression for the generating function of separable derangements has been found. These permutations are counted by A393394 , 0,\ 1,\ 2,\ 7,\ 30,\ 124,\ 560,\ 2610,\ 12470,\ 60955,\ 302930,\ 1528621,\ \dots. These terms were computed by tracking, for each length, how many separable permutations realize each possible displacement set. The count of separable derangements is then the sum over displacement sets not containing 0 . Problem 4.4 . Find the generating function for the number of separable derangements of length n . The ratios |\mathcal{S}^{\circ}_{n}|/|\mathcal{S}_{n}| , where \mathcal{S} denotes the class of separable permutations, appear to be monotonically decreasing, approaching something between \nicefrac{{1}}{{5}} and \nicefrac{{1}}{{4}} . However, these guesses are based only on the enumeration up to length 18 and so should be taken with a grain of salt. Question 4.5 . What is the limiting proportion of derangements among separable permutations, assuming this limit exists? 5. Sorting The study of sorting devices has been intertwined with permutation patterns since Knuth’s analysis of stack-sorting in The Art of Computer Programming . In this section, we consider several sorting machines: multiple stacks in series, Atkinson’s enhanced (r,s) -stacks, and restricted containers (also known as \mathcal{C} -machines). Each machine gives rise to a permutation class (the permutations it can sort/generate), and there are numerous open problems. Stacks A stack is a last-in first-out linear sorting device with push and pop operations. The greedy algorithm for stack-sorting a permutation \pi=\pi(1)\pi(2)\cdots\pi(n) proceeds as follows. First, push \pi(1) onto the stack. At a later stage, suppose that the entries \pi(1),\dots,\pi(i-1) have all been either output or pushed onto the stack, so \pi(i) is the next entry in the input. If \pi(i) is less than every entry currently on the stack, push \pi(i) onto the stack. Otherwise, pop entries off the stack (to the output) until \pi(i) is less than every remaining stack entry, then push \pi(i) onto the stack. After all entries have been read, pop any remaining entries from the stack to the output. This produces a permutation s(\pi) . A permutation is West t -stack sortable if s^{t}(\pi) is the identity permutation. We caution that for {t\geq 2} , the set of West- t -stack-sortable permutations does not form a permutation class. As one example, 35241 is West- 2 -stack-sortable, because s(s(35241))=s(32145)=12345, but its subpermutation 3241 is not West- 2 -stack-sortable, because s(s(3241))=s(2314)=2134\neq 1234. Indeed, West [ 95 , Theorem 4.2.18] (and later in [ 96 ] ) showed that the West- 2 -stack-sortable permutations (he did not call them this) are characterized by avoiding 2341 in the standard sense, and also avoiding the barred pattern 3\overline{5}241 ; a permutation avoids 3\overline{5}241 if every occurrence of the pattern 3241 can be extended to an occurrence of the pattern 35241 . We will not belabor West stack-sorting any further, and instead turn to sorting with t stacks in series: a permutation is sortable by t stacks in series if there exists some sequence of operations that transforms it into the identity, where each operation pushes to or pops from one of the t stacks, and entries pass through the stacks in order (from the first stack to the second, and so on). Unlike the West notion, this definition behaves as one might reasonably hope. In particular, the set of permutations sortable by t stacks in series forms a permutation class: if a permutation can be sorted, then any subpermutation can be sorted by running the same operations while ignoring the entries not present in the subpermutation. One and two stacks The permutations sortable by a single stack are precisely \operatorname{Av}(231) , as observed by Knuth [ 57 , Exercise 2.2.1-5] . For two stacks in series, Tarjan [ 91 , Lemma 10] found that the shortest unsortable permutation has length 7 . We quote his ‘‘proof’’ 8 8 8 Pratt [ 74 ] , in a paper from the same era, begins a proof with “We leave to the reader the pleasure of convincing himself that none of the permutations in Figure 3 can be computed by a deque.” The implicit assumption in both papers, one published in the Journal of the ACM and the other in STOC , that the reader would verify such claims by hand rather than by computer is now somewhat quaint. : (2435761) is unsortable using two stacks, as the reader may easily verify. Conversely, every sequence of length 6 or less may be sorted using two stacks. Exhaustive case analysis will verify this fact. In a 1992 technical report [ 7 , Theorem 2] , Atkinson seems to have been the first to find all 22 basis elements of length 7 for two stacks in series. Murphy [ 69 , Proposition 257] proved that the class of permutations sortable by two stacks in series has an infinite basis, and in addition to the 22 basis elements of length 7 , he lists the 51 basis elements of length 8 . More generally, the number of basis elements of length n , for n\geq 7 , is given by A111576 : 22,\ 51,\ 146,\ 604,\ \dots. Computing these basis elements up to n=10 is not difficult once one views the sortable permutations in terms of products of 231 -avoiding permutations, as we explain below. Sorting, generating, and duality We pause to discuss a general framework that clarifies several arguments to follow. We think of sorting machines as transforming an input permutation (generally drawn on the right in diagrams, so that the entries enter the machine in their natural order \pi(1) , \pi(2) , \dots ) to an output permutation. Sorting is then the special case where the output is the identity. M \xleftarrow{\phantom{\text{BS}}} \xleftarrow{\phantom{\text{BS}}} 12\cdots n output \pi(1)\pi(2)\cdots\pi(n) input Generating is the special case where the input is the identity. M \xleftarrow{\phantom{\text{BS}}} \xleftarrow{\phantom{\text{BS}}} \pi(1)\pi(2)\cdots\pi(n) output 12\cdots n input A machine is symbol oblivious if its allowed operations are indifferent to the values of the symbols being manipulated. (This terminology follows Atkinson [ 9 ] , although he simply uses oblivious ; we add ‘‘symbol’’ to avoid confusion with other uses of the term ‘‘oblivious’’ in computer science.) A stack is symbol oblivious: a push or pop is permitted regardless of what symbol is involved. 9 9 9 Although not under West’s notion, since the rule “pop if the top of the stack is smaller than the next input entry” depends on comparing symbol values. Compositions of stacks in series are also symbol oblivious. For a symbol-oblivious machine, if we relabel the input symbols and perform the same sequence of operations, we obtain the correspondingly relabeled output. Suppose a symbol-oblivious machine M can transform \pi into \sigma . Relabeling by an arbitrary permutation \tau shows that the same sequence of operations allows M to transform \tau\circ\pi into \tau\circ\sigma . In particular, taking \tau=\sigma^{-1} , we see that M can transform \sigma^{-1}\circ\pi into the identity. In other words: Proposition 5.1 . Let M be a symbol-oblivious machine. Then M can transform \pi into \sigma if and only if M can sort \sigma^{-1}\circ\pi . In particular, M can generate \pi if and only if M can sort \pi^{-1} . For example, a single stack sorts precisely the class \operatorname{Av}(231) . Since 312^{-1}=231 , Proposition 5.1 implies that a single stack generates the class \operatorname{Av}(312) from the identity. More generally, symbol obliviousness clarifies what two stacks in series can generate. Suppose entries pass through the first stack and enter the second stack in the order \sigma(1),\sigma(2),\ldots,\sigma(n) . Since a single stack generates \operatorname{Av}(312) , we have \sigma\in\operatorname{Av}(312) . By symbol obliviousness, the second stack performs some sequence of operations that would transform 12\cdots n into some \tau\in\operatorname{Av}(312) . Since the actual symbols input into the second stack are \sigma(1),\ldots,\sigma(n) rather than 1,\ldots,n , the output is relabeled accordingly, generating \sigma\circ\tau . Thus two stacks in series generate precisely \operatorname{Av}(312)\circ\operatorname{Av}(312) . This yields a simple method for computing the basis mentioned earlier: generate all elements of \operatorname{Av}(231)\circ\operatorname{Av}(231) up to the desired length, and identify the minimal permutations that do not appear. A second useful observation concerns running machines backwards. Suppose that a machine M can transform \pi into \sigma via some sequence of operations. M \xleftarrow{\phantom{\text{BS}}} \xleftarrow{\phantom{\text{BS}}} \sigma(1)\sigma(2)\cdots\sigma(n) output \pi(1)\pi(2)\cdots\pi(n) input Reading that sequence backwards describes a way for a “reversed machine” M^{\mathrm{r}} to transform \sigma^{\mathrm{r}} into \pi^{\mathrm{r}} . M^{\mathrm{r}} \xrightarrow{\phantom{\text{BS}}} \xrightarrow{\phantom{\text{BS}}} \sigma(1)\sigma(2)\cdots\sigma(n) input \pi(1)\pi(2)\cdots\pi(n) output In general, M^{\mathrm{r}} may be a different machine than M , and we say that M is reversible if M^{\mathrm{r}}=M . Stacks in series are reversible (reverse the roles of input and output, reverse the order of the stacks, and exchange pushes with pops). If we assume that M , and hence also M^{\mathrm{r}} , is symbol oblivious, and that M can sort \pi , then M^{\mathrm{r}} can transform \rho=n(n-1)\cdots 21 into \pi^{\mathrm{r}} . M^{\mathrm{r}} \xrightarrow{\phantom{\text{BS}}} \xrightarrow{\phantom{\text{BS}}} n\cdots 21 input \pi(1)\pi(2)\cdots\pi(n) output Relabeling the entries according to (\pi^{\mathrm{r}})^{-1} , we see that M^{\mathrm{r}} transforms (\pi^{\mathrm{r}})^{-1}\circ\rho=\rho\circ\pi^{-1}\circ\rho=(\pi^{\mathrm{rc}})^{-1} into the identity, which we record below. Proposition 5.2 . If a symbol-oblivious machine M can sort \pi , then the reversed machine M^{\mathrm{r}} can sort (\pi^{\mathrm{rc}})^{-1}=\rho\circ\pi^{-1}\circ\rho . Since stacks in series are symbol oblivious and reversible, if \pi can be sorted by t stacks in series, then (\pi^{\mathrm{rc}})^{-1} can also be sorted by t stacks in series. As Figure 2 shows, the permutation (\pi^{\mathrm{rc}})^{-1} is the reflection of \pi about the anti-diagonal. This permutation has been called the “dual” of \pi (Murphy [ 69 , Section 8.1.2] ) or the “two-stack dual” (Smith and Vatter [ 82 ] ). We suggest instead the term sorting dual , since this duality applies to any symbol-oblivious reversible machine. General bounds For general t , Knuth presents an argument in The Art of Computer Programming , Volume 3 [ 58 , Solution to Exercise 5.2.4-19] showing that if all permutations of length n can be sorted by t stacks in series, then all permutations of length 2n can be sorted by t+1 stacks in series. (This argument also appears in Tarjan [ 91 , Lemma 11] .) We sketch the proof. Let \pi be a permutation of length 2n and suppose that all permutations of length n can be sorted by t stacks in series. By symbol-obliviousness, all permutations of length n can be transformed into \rho=n(n-1)\cdots 21 . Thus we can use the first t of our t+1 stacks to output \pi(1),\dots,\pi(n) in descending order, pushing these entries into the last stack so that they sit in increasing order (read top to bottom) before we read \pi(n+1) . We then use the first t stacks to sort \pi(n+1),\dots,\pi(2n) , merging these entries with the contents of the final stack into the output as desired. Murphy [ 69 , Proposition 264] gives a different argument to obtain a similar result. In his approach, we process all entries \pi(1),\dots,\pi(2n) at once. The entries with values 1,2,\dots,n are sorted and output using the last t stacks (these are pushed onto the first stack but immediately popped off it). The entries with values n+1,n+2,\dots,2n are pushed into the first stack, where they remain temporarily. Once all entries with values 1,2,\dots,n have been output, the entries n+1,n+2,\dots,2n sit “upside down” in the first stack, in the reverse order of the subsequence they form in \pi , read top to bottom. We then sort and output these using the last t stacks. In fact, Knuth’s argument and Murphy’s argument are the sorting duals of each other. Suppose that the permutations \pi and \sigma can be sorted by t stacks in series. Knuth’s argument shows that {t+1} stacks in series can sort all horizontal juxtapositions of the form \begin{bmatrix}\rho\circ\pi&\sigma\end{bmatrix} : permutations of length {|\pi|+|\sigma|} in which the first |\pi| entries are order-isomorphic to \rho\circ\pi (the complement of \pi ) and the last |\sigma| entries are order-isomorphic to \sigma . Murphy’s argument shows that t+1 stacks in series can sort all vertical juxtapositions of the form \begin{bmatrix}\pi\circ\rho&\sigma\end{bmatrix}^{\mathrm{T}} : permutations of length |\pi|+|\sigma| in which the largest |\pi| values are order-isomorphic to \pi\circ\rho (the reverse of \pi ) and the smallest |\sigma| values are order-isomorphic to \sigma . To see the duality, substitute the sorting duals of \pi and \sigma into Murphy’s construction. Since the sorting dual of \pi is \rho\circ\pi^{-1}\circ\rho , we obtain vertical juxtapositions of the form \begin{bmatrix}(\rho\circ\pi^{-1}\circ\rho)\circ\rho\\[4.0pt] \rho\circ\sigma^{-1}\circ\rho\end{bmatrix}=\begin{bmatrix}\rho\circ\pi^{-1}\\[4.0pt] \rho\circ\sigma^{-1}\circ\rho\end{bmatrix}. The sorting duals of these permutations are precisely the horizontal juxtapositions from Knuth’s argument. Since two stacks in series can sort every permutation of length 6 , it follows from these constructions that t\geq 2 stacks in series can sort every permutation of length 3\cdot 2^{t-1} . Atkinson [ 7 , Corollary, p.10] refined this bound to 7\cdot 2^{t-2}-1 , but the asymptotics are the same: roughly \log_{2}n stacks in series suffice to sort all permutations of length n . For a lower bound, observe that a single stack can sort precisely C_{n} permutations of length n , where C_{n} denotes the n th Catalan number. Thus t stacks in series can sort at most C_{n}^{t} permutations of length n . This shows that roughly \log_{4}n stacks in series are required to sort all permutations of length n . There is a factor-of-two gap between these bounds, and it has not been significantly narrowed since Knuth first posed the following problem almost sixty years ago, which he rated 47 out of 50 in difficulty. Problem 5.3 (Knuth [ 58 , Exercise 5.2.4-20] ) . Determine the true rate of growth, as n\to\infty , of the number of stacks in series needed to sort every permutation of length n . Three stacks Specializing to three stacks, we immediately run into problems. The exhaustive computational approach that works for two stacks becomes intractable, as computing \operatorname{Av}(231)\circ\operatorname{Av}(231)\circ\operatorname{Av}(231) for even modest lengths is infeasible. We do not even know the length of the shortest basis element for the class of 3 -stack-sortable permutations, although Atkinson’s bound shows that all permutations of length 7\cdot 2-1=13 can be sorted, so this shortest basis element must have length at least 14 . Elder and Vatter [ 41 ] report that Elder and Waton wagered a beer on the problem, with Elder guessing 15 and Waton guessing 22 (“conjecturing,” if one is feeling generous). Question 5.4 (Waton; see Elder and Vatter [ 41 ] ) . What is the length of the shortest permutation that cannot be sorted by three stacks in series? Murphy [ 69 , Conjecture 265] guesses more generally that t stacks in series can sort all permutations of length up to (t+1)! , which would give 25 as the length of the shortest permutation unsortable by three stacks in series. However, Murphy’s conjecture can’t be true for all t , since \log_{4}(t+1)! grows faster than t . The known unsortable permutations are shockingly long, given these conjectured answers. Tarjan [ 91 ] reports that he constructed a permutation of length 41 that cannot be sorted by three stacks in series, although he doesn’t present it. Murphy [ 69 , Proposition 262] gives a general method to construct permutations that cannot be sorted by t+1 stacks in series, starting from a permutation that cannot be sorted by t stacks. We sketch his argument. Suppose that some permutation \beta of length k cannot be sorted by t stacks in series. Consider the permutation \pi\;=\;\beta[\,\underbrace{\,\beta^{\mathrm{r}},\,\beta^{\mathrm{r}},\dots,\,\beta^{\mathrm{r}}}_{\text{$|\beta|-1$ copies}},1\,], the inflation of \beta formed, loosely speaking, by replacing each entry of \beta except the last with a block of entries order-isomorphic to \beta^{\mathrm{r}} . We claim that \pi cannot be sorted by t+1 stacks in series. Indeed, we can never have all entries from a single \beta^{\mathrm{r}} interval together in the first stack, because reading top to bottom they would form a copy of \beta , and the remaining t stacks could not sort them. Thus at least one entry from the first interval must exit the first stack before the first entry of the second interval enters, and similarly for subsequent intervals. Focusing on these |\beta|-1 entries together with the final entry of \pi , we obtain a subsequence order-isomorphic to \beta that enters the last t stacks in that order, and the last t stacks cannot sort \beta , so they cannot sort this subsequence. Murphy’s construction yields an unsortable permutation of length |\beta|^{2}-|\beta|+1 . For three stacks, we start with a permutation of length 7 (the shortest length not sortable by two stacks), giving an unsortable permutation of length 43 , which is longer than Tarjan’s claimed example. Murphy [ 69 , p. 329] examines one such permutation and finds four entries that can be removed without making it sortable, yielding an unsortable permutation of length 39 . In his 1992 technical report, Atkinson [ 7 , Lemma 5] had already done much the same, although he obtained an unsortable permutation of length 38 . This record has stood for over thirty years. Atkinson’s (r,s) -stacks In a 1998 paper, Atkinson [ 8 ] introduced a natural generalization of stacks. With a standard stack, one may push an entry onto the top or pop an entry from the top. An (r,s) -stack relaxes these constraints: one may push the next input entry into any of the top r positions and pop any of the top s entries to the output. Thus a (1,1) -stack is an ordinary stack. These machines are symbol oblivious, as their operations do not depend on the values of the entries, and the reverse of an (r,s) -stack is an (s,r) -stack. Thus, by Proposition 5.2 , we obtain the following. Proposition 5.5 (Atkinson [ 8 , Lemma 1.1] ) . An (r,s) -stack sorts \pi if and only if an (s,r) -stack sorts its sorting dual (\pi^{\mathrm{rc}})^{-1} . In particular, the class of permutations sortable by an (r,r) -stack is closed under the sorting dual. We return to (r,s) -stacks later in this section. Restricted containers ( \mathcal{C} -machines) We now introduce a different generalization of stacks that captures many permutation classes. As we will see, this framework includes Atkinson’s (r,1) - and (1,s) -stacks as special cases. Let \mathcal{C} be a permutation class. A \mathcal{C} -machine is a container that holds entries subject to the constraint that, at all times, the entries in the container (read left to right) must be order-isomorphic to a member of \mathcal{C} . In analyzing these machines, it turns out to be more natural to study generation than sorting; we discuss this choice further below. Thus we take the input to be 12\cdots n , and the machine has three operations: ‱ push : remove the next entry from the input and place it anywhere in the container, provided the resulting arrangement is order-isomorphic to a member of \mathcal{C} ; ‱ pop : remove the leftmost entry from the container and append it to the output; ‱ bypass : remove the next entry from the input and append it directly to the output. The permutation generated by a sequence of operations is the output once all entries have exited. The classical stack is recovered by taking \mathcal{C}=\operatorname{Av}(12) . In this machine, entries in the container must be decreasing, so each push places the new entry on the left. Since pops also occur from the left, the bypass operation is redundant, and we recover the usual stack operations. As Knuth observed, this machine generates precisely \operatorname{Av}(312) . By contrast, for the \operatorname{Av}(21) -machine, the entries in the container must be increasing, so each push places the new entry on the right. Since pops occur from the left, the bypass operation is now essential. This machine generates precisely \operatorname{Av}(321) : clearly it cannot generate 321 or any permutation containing it, and conversely, to generate a 321 -avoiding permutation, output the left-to-right maxima with bypasses while passing the remaining entries (which must be increasing) through the container. (This is equivalent to generating with two queues in parallel.) At the other extreme, taking \mathcal{C} to be the class of all permutations allows entries to be placed anywhere in the container, and this machine generates all permutations. The bypass operation is superfluous in some cases, as the stack example shows. However, including it greatly simplifies the basis theorem below. In practice, bypasses are used precisely to output the left-to-right maxima of the generated permutation. The basis theorem The main structural result for \mathcal{C} -machines characterizes the classes they generate and makes it immediately apparent whether a class of interest can be generated by a \mathcal{C} -machine, and if so, which one. The proof is too simple to omit. In the statement, we use the notation 1\ominus B=\{1\ominus\beta:\beta\in B\} . Theorem 5.6 (Albert, Homberger, Pantone, Shar, and Vatter [ 2 , Theorem 1.1] ) . For any set B of permutations, the \operatorname{Av}(B) -machine generates the class \operatorname{Av}(1\ominus B) . Proof. The \operatorname{Av}(B) -machine cannot generate any permutation of the form 1\ominus\beta for \beta\in B : at the moment when the maximum entry (which appears first in 1\ominus\beta ) is next in the input, the container would need to hold a copy of \beta , and it is not allowed to do so. For the converse, we show how to generate a permutation \pi that avoids all permutations in 1\ominus B . Let i_{1}