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

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.