Séminaire Lotharingien de Combinatoire, 85B.7 (2021), 12 pp.
Colin Defant
3-Stack-Sortable Permutations and Beyond
Abstract.
We state a Decomposition Lemma that allows us to count preimages of permutations under West's stack-sorting map. This result and its generalizations have several applications to the study of stack-sorting and beyond; we will explicate two of these applications and state the remaining ones without details. First, we give a new proof of Zeilberger's formula for the number W2(n) of 2-stack-sortable permutations in Sn. We then obtain a polynomial-time algorithm for counting 3-stack-sortable permutations, settling a 30-year-old open problem. This algorithm allows us to prove the first nontrivial lower bound for limn→∞W3(n)1/n and to disprove a conjecture of Bóna. We also use new data obtained from the algorithm to comment on two of Bóna's other conjectures. Finally, we prove that limn→∞Wt(n)1/n ≥
(t1/2+1)2 for all t ≥ 1, allowing us to improve a result of Smith concerning a variant of the stack-sorting procedure.
Received: December 1, 2020.
Accepted: March 1, 2021.
Final version: April 29, 2021.
The following versions are available: