Defant, Colin - Postorder Preimages

dmtcs:3116 - Discrete Mathematics & Theoretical Computer Science, February 6, 2017, Vol 19 no. 1
Postorder Preimages

Authors: Defant, Colin

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.


Source : oai:arXiv.org:1604.01723
Volume: Vol 19 no. 1
Section: Combinatorics
Published on: February 6, 2017
Submitted on: February 2, 2017
Keywords: Mathematics - Combinatorics,05A19, 05C05


Share

Browsing statistics

This page has been seen 67 times.
This article's PDF has been downloaded 43 times.