Postorder Preimages

zbMATH Open1397.05010arXiv1604.01723MaRDI QIDQ2965992FDOQ2965992

Colin Defant

Publication date: 3 March 2017

Abstract: Given a set $Y$ of decreasing plane trees and a permutation $pi$, how many trees in $Y$ have $pi$ as their postorder? Using combinatorial and geometric constructions, we provide a method for answering this question for certain sets $Y$ and all permutations $pi$. We then provide applications of our results to the study of the deterministic stack-sorting algorithm.

Full work available at URL: https://arxiv.org/abs/1604.01723

Recommendations

• Preimages under the stack-sorting algorithm
• Splaying preorders and postorders
• Preimages under the bubblesort operator
• Preimages under a popqueue-sorting algorithm
• Postorder rearrangement operators
• Preimages under the Queuesort algorithm
• scientific article
• Counting preimages
• scientific article; zbMATH DE number 1912105
• Sorting and preimages of pattern classes

zbMATH Keywords

permutationstack-sortingtree traversaldecreasing plane treepostorder

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms (68W40)

Cited In (23)

• Fertility monotonicity and average complexity of the stack-sorting map
• Counting 3-stack-sortable permutations
• Preimages under the stack-sorting algorithm
• Quantifying noninvertibility in discrete dynamical systems
• Stack-sorting for Words
• Stack-sorting for Coxeter groups
• Characterization and enumeration of preimages under the \texttt{Queuesort} algorithm
• Polyurethane toggles
• Stack sorting with increasing and decreasing stacks
• Sorting Cayley permutations with pattern-avoiding machines
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Lattice paths and \((n - 2)\)-stack sortable permutations
• Stack-sorting, set partitions, and Lassalle's sequence
• Supertrees
• 312-Avoiding reduced valid hook configurations and duck words
• Stack-sorting preimages of permutation classes
• Fertilitopes
• Uniquely sorted permutations
• Further bijections to pattern-avoiding valid hook configurations
• Preimages under the Queuesort algorithm
• Troupes, cumulants, and stack-sorting
• Catalan intervals and uniquely sorted permutations

This page was built for publication: Postorder Preimages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965992)