2019/03/21 by Defant, Colin · 1 citation
#05A05 #05A15 #05A16 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1903.09138
We prove a "decomposition lemma" that allows us to count preimages of certain sets of permutations under West's stack-sorting map s. As a first application, we give a new proof of Zeilberger's formula for the number of 2-stack-sortable permutations in Sn. Our proof generalizes, allowing us to find an algebraic equation satisfied by the generating function that counts 2-stack-sortable permutations according to length, number of descents, and number of peaks. The same method yields a recurrence relation for W3(n), the number of 3-stack-sortable permutations in Sn. We compute W3(n) for n≤ 174, extending the 13 terms of this sequence that were known before. We also prove the first nontrivial lower bound for limn→∞W3(n)1/n. Invoking a result of Kremer, we also prove that limn→∞Wt(n)1/n≥(√(t)+1)2 for all t≥ 1, which we use to improve a result of Smith. Our computations allow us to disprove a conjecture of Bóna, although we do not yet know for sure which one. We can refine our methods to obtain a recurrence for the number of 3-stack-sortable permutations in Sn with k descents and p peaks. This produces a large amount of evidence supporting a real-rootedness conjecture of Bóna. Using part of the theory of valid hook configurations, we give a new proof of a γ-nonnegativity result of Brändén, which in turn implies an older result of Bóna. We then answer a question of the current author by producing a set A⊆ S11 such that ∑σ∈ s-1(A)xdes(σ) has nonreal roots. We interpret this as partial evidence against the same real-rootedness conjecture of Bóna that we found evidence supporting. Examining the parities of the numbers W3(n), we obtain strong evidence against yet another conjecture of Bóna. We end with some conjectures of our own.