Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Postorder Preimages
Article

Postorder Preimages

Colin Defant
Download article
Open on arXiv
Submitted on
February 2, 2017
Accepted on
January 31, 2017
Published on
February 6, 2017
Last modified on
March 31, 2025
Volume 19
vol. 19:1
Combinatorics
DOI
10.23638/DMTCS-19-1-3
License
arXiv.org - Non-exclusive license to distribute
Indicators
1139
Views
898
Downloads

Postorder Preimages

Colin Defant
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. Comment: 15 pages, 4 figures
Keywords
  • Mathematics - Combinatorics
  • 05A19, 05C05
Cited by

Source: OpenCitations

  • Quantifying Noninvertibility in Discrete Dynamical Systems

    The Electronic Journal of Combinatorics

    Authors : Colin Defant ORCID, James Propp

    Journal reference : Volume 27, 2020, pp.

    DOI : 10.37236/9475

  • Stack-sorting, set partitions, and Lassalle's sequence

    arXiv (Cornell University)

    Authors : Colin Defant ORCID, Michael Engen, Jordan A. Miller ORCID

    Journal reference : Volume 175, 2020, pp. 105275

    DOI : 10.1016/j.jcta.2020.105275

  • Descents in $t$-sorted permutations

    arXiv (Cornell University)

    Authors : Colin Defant ORCID

    Journal reference : Volume 11, 2020, pp. 511-526

    DOI : 10.4310/joc.2020.v11.n3.a5

  • Troupes, cumulants, and stack-sorting

    arXiv (Cornell University)

    Authors : Colin Defant ORCID

    Journal reference : Volume 399, 2022, pp. 108270

    DOI : 10.1016/j.aim.2022.108270

  • Preimages Under the Stack-Sorting Algorithm

    Graphs and Combinatorics

    Authors : Colin Defant ORCID

    Journal reference : Volume 33, 2016, pp. 103-122

    DOI : 10.1007/s00373-016-1752-5

  • Catalan intervals and uniquely sorted permutations

    arXiv (Cornell University)

    Authors : Colin Defant ORCID

    Journal reference : Volume 174, 2020, pp. 105250

    DOI : 10.1016/j.jcta.2020.105250

  • Fertility numbers

    Journal of Combinatorics

    Authors : Colin Defant ORCID

    Journal reference : Volume 11, 2020, pp. 527-548

    DOI : 10.4310/joc.2020.v11.n3.a6
Preview
Loading PDF preview...