Sorted and/or sortable permutations
This paper studies a procedure \(\Pi\) which partly sorts permutations, which can be defined recursively as follows: If \(\sigma\) is a permutation in which the largest letter is \(n\) we write it as \(\sigma=\sigma_1 n\sigma_2\) where \(\sigma_1\) and \(\sigma_2\) are subwords of \(\sigma\) and then define \(\Pi(\sigma_1 n\sigma_2)=\Pi(\sigma_1)\Pi(\sigma_2)n\). The main objects studied in this paper are the permutations which can be fully sorted by either one or two applications of \(\Pi\), and the permutations which are in the image of \(\Pi\). Characterisations and recognition algorithms for these permutations are found, as are functional equations for their generating functions. In some cases these equations are solved explicitly, in others \(q\)-analogues are found which count the number of inversions in the permutations. The paper is accessible and well written and includes a number of nice connections between permutations and labelled binary trees.
- Preimages under the Queuesort algorithm
- Restricted stacks as functions
- Further bijections to pattern-avoiding valid hook configurations
- Stack-sorting with consecutive-pattern-avoiding stacks
- Preimages under the bubblesort operator
- Troupes, cumulants, and stack-sorting
- Catalan intervals and uniquely sorted permutations
- Polyurethane toggles
- Stack-sorting preimages of permutation classes
- Uniquely sorted permutations
- Stack sorting with increasing and decreasing stacks
- Counting 3-stack-sortable permutations
- Preimages under the stack-sorting algorithm
- Noncontiguous pattern containment in binary trees
- Actions on permutations and unimodality of descent polynomials
- Fighting fish and two-stack sortable permutations
- All sorts of permutations (functional pearl)
- scientific article; zbMATH DE number 2127737 (Why is no real title available?)
- Stack-sorting for words
- Edit distance between unlabeled ordered trees
- Algorithms and Properties on Balanced Permutations
- Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
- Two permutation classes related to the bubble sort operator
- Operators of equivalent sorting power and related Wilf-equivalences
- scientific article; zbMATH DE number 218835 (Why is no real title available?)
- Sorting Cayley permutations with pattern-avoiding machines
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Lattice paths and pattern-avoiding uniquely sorted permutations
- Highly sorted permutations and Bell numbers
- Fertility, Strong Fertility, and Postorder Wilf Equivalence
- scientific article; zbMATH DE number 7286740 (Why is no real title available?)
- Fast Sorting and Pattern-Avoiding Permutations
- Quantifying CDS sortability of permutations by strategic pile size
- Permutree sorting
- Permutree sorting
- Sorting with networks of data structures
- Fertilitopes
- Highly sorted permutations with respect to a 312-avoiding stack
- Dynamical aspects of \(\sigma\)-machines
- Troupes, cumulants, and stack-sorting
- Characterization and enumeration of preimages under the \texttt{Queuesort} algorithm
- Sorting permutations using a pop stack with a bypass
- Periodic points of consecutive-pattern-avoiding stack-sorting maps
- The order of the (123, 132)-avoiding stack sort
- Pop stacks with a bypass
- Stack-sorting, set partitions, and Lassalle's sequence
This page was built for publication: Sorted and/or sortable permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1591137)
