Sorted and/or sortable permutations (Q1591137)

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.