Counting 3-stack-sortable permutations

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:172

Article

Defant, Colin¹ 

[1] Princeton Univ, Fine Hall,304 Washington Rd, Princeton, NJ 08544 USA

关键词: Stack-sorting;    Polynomial-time algorithm;    Permutation pattern;    Descent;    Peak;    gamma-nonnegative;    Real-rooted;    Valid hook configuration;   

DOI  :  10.1016/j.jcta.2020.105209

来源: Elsevier

【 摘 要 】

We prove a decomposition lemma that allows us to count preimages of certain sets of permutations under West's stacksorting map s. As a first application, we give a new proof of Zeilberger's formula for the number W-2(n) of 2-stack-sortable permutations in S-n. 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. This is also the first proof of this formula that generalizes to the setting of 3-stack-sortable permutations. Indeed, the same method allows us to obtain a recurrence relation for W-3(n), the number of 3-stack-sortable permutations in S-n. Hence, we obtain the first polynomial-time algorithm for computing these numbers. We compute W-3(n) for n <= 174, vastly extending the 13 terms of this sequence that were known before. We also prove the first nontrivial lower bound for lim(n ->infinity) W-3(n)(1/n), showing that it is at least 8.659702. Invoking a result of Kremer, we also prove that lim(n ->infinity) W-t(n)(1/n) >= (root t + 1)(2) for all t >= 1, which we use to improve a result of Smith concerning a variant of the stacksorting procedure. Our computations allow us to disprove a conjecture of Bona, although we do not yet know for sure which one. In fact, we can refine our methods to obtain a recurrence for W-3(n, k, p), the number of 3-stack-sortable permutations in S-n with k descents and p peaks. This allows us to gain a large amount of evidence supporting a real-rootedness conjecture of Bona. Using part of the theory of valid hook configurations, we give a new proof of a gamma-nonnegativity result of Branden, which in turn implies an older result of Bona. We then answer a question of the current author by producing a set A subset of S-11 such that Sigma(sigma is an element of s-1)(A)(xdes(sigma)) has nonreal roots. We interpret this as partial evidence against the same real-rootedness conjecture of Bona that we found evidence supporting. Examining the parities of the numbers W-3(n), we obtain strong evidence against yet another conjecture of Bona. We end with some conjectures of our own. (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free