arXiv Analytics

Sign in

arXiv:1809.09158 [math.CO]AbstractReferencesReviewsResources

Stack-sorting for Words

Colin Defant, Noah Kravitz

Published 2018-09-24Version 1

We introduce operators $\mathsf{hare}$ and $\mathsf{tortoise}$, which act on words as natural generalizations of West's stack-sorting map. We show that the heuristically slower algorithm $\mathsf{tortoise}$ can sort words arbitrarily faster than its counterpart $\mathsf{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 $\mathsf{hare}$ and $\mathsf{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. We conclude with several open problems and conjectures. In particular, our investigation of $\mathsf{tortoise}$-sortable words leads us to conjecture that there are $\frac{1}{\ell n+1}{(\ell+1)n\choose n}$ $\ell$-uniform (normalized) words of length $\ell n$ that avoid the patterns $231$ and $221$; we prove this conjecture in the case $\ell=2$.

Related articles: Most relevant | Search more
arXiv:math/0610977 [math.CO] (Published 2006-10-31)
New results related to a conjecture of Manickam and Singhi
arXiv:math/0502504 [math.CO] (Published 2005-02-23)
On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia
arXiv:math/0508537 [math.CO] (Published 2005-08-26)
On a conjecture of Widom