Search

We study preimages of permutations under the bubblesort operator $\mathbf{B}$. We achieve a description of these preimages much more complete than what is known for the more complicated sorting operators $\mathbf{S}$ (stacksort) and $\mathbf{Q}$ (queuesort). We describe explicitly the set of preimages under $\mathbf{B}$ of any permutation $\pi$ from the left-to-right maxima of $\pi$, showing that there are $2^{k-1}$ such preimages if $k$ is the number of these left-to-right maxima. We further consider, for each $n$, the tree $T_n$ recording all permutations of size $n$ in its nodes, in which an edge from child to parent corresponds to an application of $\mathbf{B}$ (the root being the identity permutation), and we present several properties of these trees. In particular, for each permutation $\pi$, we show how the subtree of $T_n$ rooted at $\pi$ is determined by the number of left-to-right maxima of $\pi$ and the length of the longest suffix of left-to-right maxima of $\pi$. Building on this result, we determine the number of nodes and leaves at every height in such trees, and we recover (resp. obtain) the average height of nodes (resp. leaves) in $T_n$.

The interval poset of a permutation is the set of intervals of a permutation, ordered with respect to inclusion. It has been introduced and studied recently in [B. Tenner, arXiv:2007.06142]. We study this poset from the perspective of the decomposition trees of permutations, describing a procedure to obtain the former from the latter. We then give alternative proofs of some of the results in [B. Tenner, arXiv:2007.06142], and we solve the open problems that it posed (and some other enumerative problems) using techniques from symbolic and analytic combinatorics. Finally, we compute the M\"obius function on such posets., Comment: V5 added oeis sequences

Following the footprints of what have been done with the algorithm Stacksort, we investigate the preimages of the map associated with a slightly less well known algorithm, called Queuesort. After having described an equivalent version of Queuesort, we provide a recursive description of the set of all preimages of a given permutation, which can be also translated into a recursive procedure to effectively find such preimages. We then deal with some enumerative issues. More specifically, we investigate the cardinality of the set of preimages of a given permutation, showing that all cardinalities are possible, except for 3. We also give exact enumeration results for the number of permutations having 0,1 and 2 preimages. Finally, we consider the special case of those permutations $\pi$ whose set of left-to-right maxima is the disjoint union of a prefix and a suffix of $\pi$: we determine a closed formula for the number of preimages of such permutations, which involves two different incarnations of ballot numbers, and we show that our formula can be expressed as a linear combination of Catalan numbers., Comment: 18 pages

We introduce a sorting machine consisting of $k+1$ stacks in series: the first $k$ stacks can only contain elements in decreasing order from top to bottom, while the last one has the opposite restriction. This device generalizes \cite{SM}, which studies the case $k=1$. Here we show that, for $k=2$, the set of sortable permutations is a class with infinite basis, by explicitly finding an antichain of minimal nonsortable permutations. This construction can easily be adapted to each $k \ge 3$. Next we describe an optimal sorting algorithm, again for the case $k=2$. We then analyze two types of left-greedy sorting procedures, obtaining complete results in one case and only some partial results in the other one. We close the paper by discussing a few open questions., Comment: 16 pages, 4 figures

The set of Schr\"oder words (Schr\"oder language) is endowed with a natural partial order, which can be conveniently described by interpreting Schr\"oder words as lattice paths. The resulting poset is called the Schr\"oder pattern poset. We find closed formulas for the number of Schr\"oder words covering/covered by a given Schr\"oder word in terms of classical parameters of the associated Schr\"oder path. We also enumerate several classes of Schr\"oder avoiding words (with respect to the length), i.e. sets of Schr\"oder words which do not contain a given Schr\"oder word., Comment: 12 pages, 1 figure