A Survey of Stack-Sorting Disciplines
---
paper_title: Computing permutations with double-ended queues, parallel stacks and parallel queues

paper_content:

A memory may be regarded as a computer with input, output and storage facilities, but with no explicit functional capability. The only possible outputs are permutations of a multiset of its inputs. Thus the natural question to ask of a class of memories is, what permutations can its members compute? We are particularly interested here in switchyard networks studied by Knuth [1968], Even and Itai [1971], and Tarjan [1972], where the permutations are of the set of inputs, rather than of a multiset of them.
---
paper_title: The Solution of a Conjecture of Stanley and Wilf for All Layered Patterns

paper_content:

Proving a conjecture of Wilf and Stanley in hitherto the most general case, we show that for any layered patternqthere is a constantcso thatqis avoided by less thancnpermutations of lengthn. This will imply the solution of this conjecture for at least 2kpatterns of lengthk, for anyk.
---
paper_title: Permutations generated by token passing in graphs

paper_content:

Abstract A transportation graph is a directed graph with a designated input node and a designated output node. Initially, the input node contains an ordered set of tokens 1,2,3, … The tokens are removed from the input node in this order and transferred through the graph to the output node in a series of moves; each move transfers a token from a node to an adjacent node. Two or more tokens cannot reside on an internal node simultaneously. When the tokens arrive at the output node they will appear in a permutation of their original order. The main result is a description of the possible arrival permutations in terms of regular sets. This description allows the number of arrival permutations of each length to be computed. The theory is then applied to packet-switching networks and has implications for the resequencing problem. It is also applied to some complex data structures and extends previously known results to the case that the data structures are of bounded capacity. A by-product of this investigation is a new proof that permutations which avoid the pattern 321 are in one to one correspondence with those that avoid 312.
---
paper_title: Computing permutations with double-ended queues, parallel stacks and parallel queues

paper_content:

A memory may be regarded as a computer with input, output and storage facilities, but with no explicit functional capability. The only possible outputs are permutations of a multiset of its inputs. Thus the natural question to ask of a class of memories is, what permutations can its members compute? We are particularly interested here in switchyard networks studied by Knuth [1968], Even and Itai [1971], and Tarjan [1972], where the permutations are of the set of inputs, rather than of a multiset of them.
---
paper_title: Permutations generated by token passing in graphs

paper_content:

Abstract A transportation graph is a directed graph with a designated input node and a designated output node. Initially, the input node contains an ordered set of tokens 1,2,3, … The tokens are removed from the input node in this order and transferred through the graph to the output node in a series of moves; each move transfers a token from a node to an adjacent node. Two or more tokens cannot reside on an internal node simultaneously. When the tokens arrive at the output node they will appear in a permutation of their original order. The main result is a description of the possible arrival permutations in terms of regular sets. This description allows the number of arrival permutations of each length to be computed. The theory is then applied to packet-switching networks and has implications for the resequencing problem. It is also applied to some complex data structures and extends previously known results to the case that the data structures are of bounded capacity. A by-product of this investigation is a new proof that permutations which avoid the pattern 321 are in one to one correspondence with those that avoid 312.
---
paper_title: Sorting with two ordered stacks in series

paper_content:

The permutations that can be sorted by two stacks in series are considered, subject to the condition that each stack remains ordered. A forbidden characterisation of such permutations is obtained and the number of permutations of each length is determined by a generating function.
---
paper_title: Sorting permutations with networks of stacks

paper_content:

Sea water contaminated with suspended organic matter and the like can be purified by expanding a mixture of the water with air so as to generate a froth, and letting the froth carrying the impurities overflow from a tubular riser attached to the expansion vessel while purified water is drawn off from the bottom of the vessel. The froth is stabilized by maintaining a layer of more alkaline liquid on the inner wall of the riser. The apparatus employed uses a rotating nozzle for continuously rinsing the wall of the riser with a liquid more alkaline than the froth, such as the original sea water prior to its being mixed with air.
---
paper_title: Sorting with parallel pop - stacks

paper_content:

Detrimental color changes in liquid diphenylamine age-resisters have been inhibited and/or reduced by combining with the age-resisters small amounts of a color inhibitor selected from the group consisting of trialkylol amines, glycol diesters of sulphur-containing monocarboxylic acids, and dialkyl esters of thiodicarboxylic acids in a weight ratio of color inhibitor to age-resister of from 0.25:99.75 to 5:95.
---
paper_title: Computing permutations with double-ended queues, parallel stacks and parallel queues

paper_content:

A memory may be regarded as a computer with input, output and storage facilities, but with no explicit functional capability. The only possible outputs are permutations of a multiset of its inputs. Thus the natural question to ask of a class of memories is, what permutations can its members compute? We are particularly interested here in switchyard networks studied by Knuth [1968], Even and Itai [1971], and Tarjan [1972], where the permutations are of the set of inputs, rather than of a multiset of them.
---
paper_title: Raney Paths and a Combinatorial Relationship between Rooted Nonseparable Planar Maps and Two-Stack-Sortable Permutations

paper_content:

An encoding of the set of two-stack-sortable permutations (TSS) in terms of lattice paths and ordered lists of strings is obtained. These lattice paths are called Raney paths. The encoding yields combinatorial decompositions for two complementary subsets of TSS, which are the analogues of previously known decompositions for the set of nonseparable rooted planar maps (NS). This provides a combinatorial relationship between TSS and NS, and, hence, a bijection is determined between these sets that is different, simpler, and more refined than the previously known bijection.
---
paper_title: A proof of Julian West's conjecture that the number of two-stacksortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!)

paper_content:

Abstract The Polya-Schutzenberger-Tutte methodology of weight enumeration, combined with about 10 hours of CPU time (of Maple running on Drexel University's Sun network) established Julian West's conjecture that 2-stack-sortable permutations are enumerated by sequence # 651 in the Sloane listing.
---
paper_title: Permutations with forbidden subsequences and nonseparable planar maps

paper_content:

The goal of the present work is to connect combinatorially a family of maps to a family of permutations with forbidden subsequences. We obtain a generating tree of nonseparable planar rooted maps and show that this tree is the generating tree of a family of permutations. The distribution of these permutations is then obtained. Finally, the different steps leading to the combinatorial proof of West's conjecture are listed.
---
paper_title: Restricted permutations and the wreath product

paper_content:

Restricted permutations are those constrained by having to avoid subsequences ordered in various prescribed ways. A closed set is a set of permutations all satisfying a given basis set of restrictions. A wreath product construction is introduced and it is shown that this construction gives rise to a number of useful techniques for deciding the finite basis question and solving the enumeration problem. Several applications of these techniques are given.
---
paper_title: Pattern Matching For Permutations

paper_content:

Given a permutation T of 1 to n, and a permutation P of 1 to k, for k ⩽ n, we wish to find a k-element subsequence of T whose elements are ordered according to the permutation P. For example, if P is (1, 2, …, k), then we wish to find an increasing subsequence of length k in T; this special case was done in time O(n log log n) by Chang and Wang. We prove that the general problem is NP-complete. We give a polynomial time algorithm for the decision problem, and the corresponding counting problem, in the case that P is separable — i.e., contains neither the subpattern (3, 1, 4, 2) nor its reverse, the subpattern (2, 4, 1, 3).
---
paper_title: Sorted and/or sortable permutations

paper_content:

Abstract In his Ph.D. thesis, Julian West (Permutations with restricted subsequences and stack-sortable permutations, MIT, 1990) studied in depth a map Π that acts on permutations of the symmetric group S n by partially sorting them through a stack. The main motivation of this paper is to characterize and count the permutations of Π( S n ) , which we call sorted permutations. This is equivalent to counting preorders of increasing binary trees. We first find a local characterization of sorted permutations. Then, using an extension of Zeilberger's factorization of two-stack sortable permutations (D. Zeilberger, Discrete Math. 102 (1992) 85–93), we obtain for the generating function of sorted permutations an unusual functional equation. Out of curiosity, we apply the same treatment to four other families of permutations (general permutations, one-stack sortable permutations, two-stack sortable permutations, sorted and sortable permutations) and compare the functional equations we obtain. All of them have similar features, involving a divided difference. Moreover, most of them have interesting q-analogs obtained by counting inversions. We solve (some of) our equations.
---
paper_title: A Bijective Census of Nonseparable Planar Maps

paper_content:

Bijections are obtained between nonseparable planar maps and two different kinds of trees: description trees and skew ternary trees. A combinatorial relation between the latter and ternary trees allows bijective enumeration and random generation of nonseparable planar maps. The involved bijections take account of the usual combinatorial parameters and give a bijective proof of formulae established by Brown and Tutte. These results, combined with a bijection due to Goulden and West, give a purely combinatorial enumeration of two-stack-sortable permutations.
---
paper_title: Symmetry and Unimodality in t-Stack Sortable Permutations

paper_content:

We present the first nontrivial results on t-stack sortable permutations by constructively proving that the sequence Wt(n, k) of the numbers of t-stack sortable permutations with k descents is symmetric and unimodal.
---
paper_title: On the Neggers–Stanley Conjecture and the Eulerian Polynomials

paper_content:

Abstract We prove combinatorially that the W -polynomials of naturally labeled graded posets of rank 1 or 2 (an antichain has rank 0) are unimodal, thus providing further supporting evidence for the Neggers–Stanley conjecture. For such posets we also obtain a combinatorial proof that the W -polynomials are symmetric. Combinatorial proofs that the Eulerian polynomials are log-concave and unimodal are given and we construct a simplicial complex Δ with the property that the Hilbert function of the exterior algebra modulo the Stanley–Reisner ideal of Δ is the sequence of Eulerian numbers, thus providing a combinatorial proof of a result of Brenti.
---
paper_title: Hilbert Polynomials in Combinatorics

paper_content:

We prove that several polynomials naturally arising in combinatorics are Hilbert polynomials of standard graded commutative k-algebras.
---
paper_title: Symmetry and Unimodality in t-Stack Sortable Permutations

paper_content:

We present the first nontrivial results on t-stack sortable permutations by constructively proving that the sequence Wt(n, k) of the numbers of t-stack sortable permutations with k descents is symmetric and unimodal.
---
paper_title: On the Neggers–Stanley Conjecture and the Eulerian Polynomials

paper_content:

Abstract We prove combinatorially that the W -polynomials of naturally labeled graded posets of rank 1 or 2 (an antichain has rank 0) are unimodal, thus providing further supporting evidence for the Neggers–Stanley conjecture. For such posets we also obtain a combinatorial proof that the W -polynomials are symmetric. Combinatorial proofs that the Eulerian polynomials are log-concave and unimodal are given and we construct a simplicial complex Δ with the property that the Hilbert function of the exterior algebra modulo the Stanley–Reisner ideal of Δ is the sequence of Eulerian numbers, thus providing a combinatorial proof of a result of Brenti.
---
paper_title: A simplicial complex of 2-stack sortable permutations

paper_content:

For each n, we construct a simplicial complex whose k-dimensional faces are in one-to-one correspondence with 2-stack sortable permutations of length n having k ascents.
---

Title: A Survey of Stack-Sorting Disciplines

Section 1: Introduction
Description 1: Provide an overview of the stack sorting problem, its historical context, and the motivation behind studying it. Introduce the main concepts and the scope of the survey.

Section 2: Variations on a Single Stack
Description 2: Discuss the different generalizations of the basic stack model, including deques, pop-stacks, (r, s)-stacks, and fork-stacks. Explain their sorting abilities and associated enumeration problems.

Section 3: Systems of Stacks
Description 3: Explore the models involving multiple stacks either in parallel or in series. Discuss key results and challenges in sorting with these systems, including known sorting algorithms and NP-completeness results.

Section 4: Enumeration of West t-Stack-Sortable Permutations by Ascents
Description 4: Review the enumeration of permutations sorted by West's t-stack model, focusing on properties such as unimodality, log-concavity, and real zeros. Discuss bijections with combinatorial structures like β(1, 0)-trees and related theorems.

Section 5: Open Problems and Future Directions
Description 5: Highlight unresolved questions and potential areas for future research in the context of stack-sorting and permutation patterns. Suggest new models or extensions to existing ones that could be explored.