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, 372. pp. 1-14. ISSN 0166-218X (https://doi.org/10.1016/j.dam.2025.03.032)

[thumbnail of Zhang-Kitaev-DAM-2025-Descent-generating-polynomials-for-n-3-and-n-4-stack-sortable]
Preview
 Text. Filename: Zhang-Kitaev-DAM-2025-Descent-generating-polynomials-for-n-3-and-n-4-stack-sortable.pdf
Accepted Author Manuscript
License: Creative Commons Attribution 4.0 logo
Download (780kB)| Preview

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;
  • Item type:Article
    ID code:92519
    Dates:
    Date
    Event
    15 September 2025
    Published
    4 April 2025
    Published Online
    28 March 2025
    Accepted
    22 August 2024
    Submitted
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:03 Apr 2025 09:02
    Last modified:22 Apr 2025 07:26
    URI:https://strathprints.strath.ac.uk/id/eprint/92519
CORE (COnnecting REpositories)