Postorder Preimages

Abstract

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

15 pages, 4 figures