Postorder Preimages

MaRDI QIDQ2965992zbMATH OpenFDO

Authors Colin Defant

Publication date 3 March 2017

Full work available at URL https://arxiv.org/abs/1604.01723, https://dmtcs.episciences.org/3116/pdf

zbMATH Keywords

permutationstack-sortingtree traversaldecreasing plane treepostorder

Mathematics Subject Classification ID

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

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.

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; zbMATH DE number 4134108
• Counting preimages
• scientific article; zbMATH DE number 1912105
• Sorting and preimages of pattern classes

Cited in

(23)

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

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)