2018/09/24 by Colin Defant, Defant, Colin, Noah Kravitz +1 · 2 citations
Computer Science · Mathematics · #05A19 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Primary 05A05 #Secondary 05A15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1809.09158
openalex publication_date 2018/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce operators hare and tortoise, which act on words as natural generalizations of West's stack-sorting map. We show that the heuristically slower algorithm tortoise can sort words arbitrarily faster than its counterpart hare. We then generalize the combinatorial objects known as valid hook configurations in order to find a method for computing the number of preimages of any word under these two operators. We relate the question of determining which words are sortable by hare and tortoise to more classical problems in pattern avoidance, and we derive a recurrence for the number of words with a fixed number of copies of each letter (permutations of a multiset) that are sortable by each map. In particular, we use generating trees to prove that the ℓ-uniform words on the alphabet [n] that avoid the patterns 231 and 221 are counted by the (ℓ+1)-Catalan number (1)/(ℓ n+1)(ℓ+1)n\choose n. We conclude with several open problems and conjectures.