Descent generating polynomials for (n-3)- and (n-4)-stack-sortable (pattern-avoiding) permutations

Tools

Zhang, Philip B. and Kitaev, Sergey (2025) Descent generating polynomials for (n-3)- and (n-4)-stack-sortable (pattern-avoiding) permutations. Discrete Applied Mathematics. ISSN 0166-218X (In Press)

[thumbnail of Zhang-Kitaev-DAM-2025-Descent-generating-polynomials-for-n-3-and-n-4-stack-sortable] Text. Filename: Zhang-Kitaev-DAM-2025-Descent-generating-polynomials-for-n-3-and-n-4-stack-sortable.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 1 January 2099.
Download (780kB) | Request a copy

Abstract

In this paper, we find distribution of descents over (n − 3)- and (n − 4)-stack-sortable permutations in terms of Eulerian polynomials. Our results generalize the enumeration results by Claesson, Dukes, and Steingrímsson on (n−3)- and (n−4)-stack-sortable permutations. Moreover, we find distribution of descents on (n − 2)-, (n − 3)- and (n − 4)-stack-sortable permutations that avoid any given pattern of length 3, which extends known results in the literature on distribution of descents over pattern-avoiding 1- and 2-stack-sortable permutations. Our distribution results also give enumeration of (n − 2)-, (n − 3)- and (n − 4)-stack-sortable permutations avoiding any pattern of length 3. One of our conjectures links our work to stack-sorting with restricted stacks, and the other conjecture states that 213-avoiding permutations sortable with t stacks are equinumerous with 321-avoiding permutations sortable with t stacks for any t.

ORCID iDs

Zhang, Philip B. and Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
CORE (COnnecting REpositories)