Philip B. Zhang

a · 2025

Read Philip B. Zhang by a (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22067.txt.

Introduction

Sergey Kitaev and Philip Zhang wrote this 2025 arXiv paper in enumerative combinatorics, counting permutations by their descents and their sortability. A permutation is stack-sortable if a simple stack machine can rearrange it into order; restricting the number of stacks gives families whose counting is partly understood. The authors work near the top of the range, with almost as many stacks as elements.

They find the full distribution of descents, packaged in Eulerian polynomials, for permutations sortable with all but three or all but four stacks. They extend the count to permutations that also avoid any chosen pattern of length three, across three stack levels. The distributions double as enumerations of the families themselves. Two conjectures close the paper, one linking the work to restricted stacks and another claiming a hidden symmetry between two pattern classes at every stack count.

Catalog record

CREATORa
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-22067

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Philip B. Zhang a Abstract Descent generating polynomials for ( n-3 )- and ( n-4 )-stack-sortable (pattern-avoiding) permutations 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 . AMS Classification 2010: 05A15 Keywords: t -stack-sortable permutation; descent statistic; Eulerian polynomial; pattern-avoidance 1 Introduction Let n be a positive integer. A permutation of length n is a rearrangement of the set [n]:=\{1,2,\ldots,n\} and \varepsilon denotes the empty permutation. For a permutation \pi=\pi_{1}\pi_{2}\cdots\pi_{n} with \pi_{i}=n , the stack-sorting operation \mathcal{S} is recursively defined as follows, where \mathcal{S}(\varepsilon)=\varepsilon : \mathcal{S}(\pi)=\mathcal{S}(\pi_{1}\cdots\pi_{i-1})\,\mathcal{S}(\pi_{i+1}\cdots\pi_{n})\,n. A permutation \pi is t -stack-sortable if the permutation \mathcal{S}^{t}(\pi) , obtained by applying the stack-sorting operation t times, is the identity permutation. The study of ( t -)stack-sortable permutations has attracted great attention in mathematics and theoretical computer science (see, e.g. [ 1 , 2 , 7 , 8 , 9 , 11 , 13 , 14 , 24 ] ). Clearly, all permutations are (n-1) -stack-sortable. Knuth [ 18 ] discovered that the Catalan numbers C_{n}=\frac{1}{n+1}\binom{2n}{n} count the number of permutations of length n whose resulting permutations are 1-stack-sortable permutations of length n . It turns out that 1-stack-sortable permutations are precisely 231-avoiding permutations, where a permutation \pi_{1}\pi_{2}\cdots\pi_{n} avoids a pattern p=p_{1}p_{2}\cdots p_{k} (which is also a permutation) if there is no subsequence \pi_{i_{1}}\pi_{i_{2}}\cdots\pi_{i_{k}} such that \pi_{i_{j}}<\pi_{i_{m}} if and only if p_{j}<p_{m} [ 17 ] . For the cases of t=2 and t=n-2 , enumeration results for t -stack-sortable permutations were given by West [ 23 ] , and for t=n-3 and t=n-4 by Claesson, Dukes, and Steingrímsson [ 11 ] . For an overview of properties of t -stack-sortable permutations, see [ 2 , 18 , 23 ] and [ 17 , Sec 2.1] . More recent results related to stack-sortings can be found here [ 7 , 9 , 12 , 13 , 14 ] . In this paper, we consider the descent generating polynomials for (pattern-avoiding) t -stack-sortable permutations for certain values of t . Given a permutation \pi=\pi_{1}\pi_{2}\cdots\pi_{n} , the descent statistic on \pi is defined as the number of i\in[n-1] such that \pi_{i}>\pi_{i+1} . Denote by \mathfrak{S}_{n} the set of permutations of [n] . The Eulerian polynomial A_{n}(x) is defined as the generating function of the descent statistic over \mathfrak{S}_{n} , namely, \displaystyle A_{n}(x):=\sum_{\pi\in\mathfrak{S}_{n}}x^{\des(\pi)}. It is known that the Eulerian polynomials can be computed inductively by A_{0}(x)=1,\ \ A_{n}(x)=\sum_{k=0}^{n-1}{n\choose k}A_{k}(x)(x-1)^{n-1-k},\ \ n\geq 1. Also, for n\geq 1 , the Eulerian polynomials can be computed as A_{n}(x)=\sum_{k=1}^{n}k!S(n,k)(x-1)^{n-k} where S(n,k) is the Stirling numbers of the second kind . Denote by \mathcal{W}_{n,t} the set of t -stack-sortable permutations of [n] . Let \displaystyle W_{n,t}(x):=\sum_{\pi\in\mathcal{W}_{n,t}}x^{\des(\pi)} be the generating function for the descent statistic over t -stack-sortable permutations. It is known that W_{n,1}(x) are the Narayana polynomials N_{n}(x):=\sum_{k=0}^{n-1}\frac{1}{n}\binom{n}{k}\binom{n}{k+1}x^{k} and W_{n,n-1}(x) , being the set of all permutations of length n , are the Eulerian polynomials A_{n}(x) . Jacquard and Schaeffer [ 16 ] gave the following formula in the case of t=2 \displaystyle W_{n,2}(x)=\sum_{k=0}^{n-1}\frac{(n+k)!(2n-k-1)!}{(k+1)!(n-k)!(2k+1)!(2n-2k-1)!}x^{k}, which also counts certain planar maps and so-called \beta(0,1) -trees encoding them [ 17 ] . For the case of t=n-2 , Brändén [ 3 , Sec. 5] proved that \displaystyle W_{n,n-2}(x)=A_{n}(x)-x\,A_{n-2}(x). (1) Let W_{n,t}^{p}(x) denote the generating function for descents over permutations in \mathcal{W}_{n,t} that avoid a pattern p . It is known [ 7 ] that there are \displaystyle\frac{1}{k+1}{n-1\choose k}{n\choose k} (2) p -avoiding permutations of length n with k descents if p\in\{132,213,231,312\} , which in particular gives the distribution of descents over 1-stack-sortable permutations (which are precisely 231-avoiding permutations). On the other hand, the distribution of descents over 123-avoiding permutations is given by the following formula [ 1 , 7 ] , where t and x correspond to the length and the number of descents, \displaystyle 1+\sum_{n=1}t^{n}{\sum_{\begin{subarray}{c}\pi\in\mathfrak{S}_{n}\\ \pi\text{ avoids }123\end{subarray}}x^{\des(\pi)}}=\frac{-1+2tx+2t^{2}x-2tx^{2}-4t^{2}x^{2}+2t^{2}x^{3}+\sqrt{1-4tx-4t^{2}x+4t^{2}x^{2}}}{2tx^{2}(tx-1-t)}. For k\geq 1 , the number of 321-avoiding permutations of length n with k descents [ 21 , A091156] is \displaystyle\frac{1}{n+1}{n+1\choose k}\sum_{j=0}^{n-2k}{k+j-1\choose k-1}{n+1-k\choose n-2k-j}. (3) The number of descents plus the number of ascents in a permutation of length n is n-1 , and reading all 321-avoiding permutations in the reverse order gives all 123-avoiding permutations. Hence, we have the following distribution of descents over 123-avoiding permutations of length n , \displaystyle\frac{1}{n+1}{n+1\choose k+2}\sum_{j=0}^{2k-n+2}{n-k+j-2\choose j}{k+2\choose n-k+j}. (4) A particular result of Bukata at el. [ 7 ] states that the number of 213-avoiding 1-stack-sortable (i.e. 213-avoiding and 231-avoiding) permutations of length n with k descents is given by {n-1\choose k} . Egge and Mansour [ 15 ] studied 132-avoiding 2-stack-sortable permutations. In this paper, we give formulas for W_{n,n-3}(x) and W_{n,n-4}(x) in terms of Eulerian polynomials, which generalize the enumeration results of Claesson, Dukes, and Steingrímsson [ 11 ] . Moreover, we derive explicit formulas for W^{p}_{n,n-2}(x) , W^{p}_{n,n-3}(x) and W^{p}_{n,n-4}(x) , where p is any permutation of length 3, which extend the studies in [ 1 , 7 , 15 ] . Setting x=1 in these formulas gives us enumeration of p -avoiding (n-2) -, (n-3) - and (n-4) -stack-sortable permutations for p\in\mathfrak{S}_{3} (see Table 1 ). The paper is organized as follows. In Section 2 we list the main enumerative results in the paper and introduce the stack-sorting complexity. In Sections 3 and 4 we prove Theorems 1 and 2 , respectively. In Section 5 we provide proofs of Theorems 3 – 8 . Finally, in Section 6 we give some concluding remarks and state two conjectures. 2 The main results in the paper The main results in this paper are stated in the following theorems. Theorem 1 . For n\geq 4 , we have that \displaystyle W_{n,n-3}(x)= \displaystyle\,A_{n}(x)-\frac{5}{2}xA_{n-2}(x)-\left(n-\frac{3}{2}\right)x(x+1)A_{n-3}(x). (5) Theorem 2 . For n\geq 4 , we have that \displaystyle W_{n,n-4}(x)=\left\{\begin{array}[]{ll}1&\mbox{if }n=4,\\ x^{4}+10x^{3}+20x^{2}+10x+1&\mbox{if }n=5,\\[2.0pt] {\begin{aligned} &\frac{1}{6}\Big[6A_{n}(x)-26xA_{n-2}(x)-(15n-30)x(x+1)A_{n-3}(x)\\ &\qquad-\Big((3n^{2}-12n+10)(x^{3}+x)+(12n^{2}-48n+28)x^{2}\Big)A_{n-4}(x)\Big]\end{aligned}}&\mbox{if }n\geq 6.\end{array}\right. Theorem 3 . We have that \displaystyle W^{231}_{n,t}(x)= \displaystyle\,\displaystyle\sum_{k=0}^{n-1}\frac{1}{k+1}{n-1\choose k}{n\choose k}x^{k}\quad\mbox{ for }1\leq t\leq n-1. Theorem 4 . For n\geq 4 , we have that \displaystyle W^{123}_{n,n-2}(x)= \displaystyle\,W^{123}_{n,n-1}(x)-x^{n-2}; \displaystyle W^{123}_{n,n-3}(x)= \displaystyle\,W^{123}_{n,n-1}(x)-(n-2)x^{n-3}-(n+1)x^{n-2}; \displaystyle W^{123}_{n,n-4}(x)= \displaystyle\,W^{123}_{n,n-1}(x)-\left\{\begin{array}[]{ll}(2x+11x^{2}+x^{3})&\mbox{if }n=4\\ (15x^{2}+16x^{3})&\mbox{if }n=5\\ \left((n^{2}-n-3)x^{n-3}+\frac{n^{2}+n+2}{2}\,x^{n-2}\right)&\mbox{if }n\geq 6\end{array}\right. where W^{123}_{n,n-1}(x)=\displaystyle\sum_{k\geq 0}\frac{1}{n+1}{n+1\choose k+2}\sum_{j=0}^{2k-n+2}{n-k+j-2\choose{j}}{k+2\choose n-k+j}x^{k} . Theorem 5 . For n\geq 4 , we have that \displaystyle W^{321}_{n,n-2}(x)= \displaystyle\,W^{321}_{n,n-1}(x)-x; \displaystyle W^{321}_{n,n-3}(x)= \displaystyle\,W^{321}_{n,n-1}(x)\,-(n+1)x-(n-3)x^{2}; \displaystyle W^{321}_{n,n-4}(x)= \displaystyle\,W^{321}_{n,n-1}(x)-\frac{n^{2}+n+2}{2}x-\left(n^{2}-n-10\right)x^{2}-\binom{n-4}{2}x^{3}; where W^{321}_{n,n-1}(x)={1+\displaystyle\sum_{k\geq 1}}\frac{1}{n+1}{n+1\choose k}\sum_{j=0}^{n-2k}{k+j-1\choose k-1}{n+1-k\choose n-2k-j}x^{k} . Recall that the Narayana polynomials are defined as N_{n}(x)=\displaystyle\sum_{k=0}^{n-1}\frac{1}{k+1}{n-1\choose k}{n\choose k}x^{k} for n\geq 1 and N_{0}(x)=1 . It is known that W^{213}_{n,n-1}(x)=W^{132}_{n,n-1}(x)=W^{312}_{n,n-1}(x)=N_{n}(x). Theorem 6 . For n\geq 4 , we have that \displaystyle W^{213}_{n,n-2}(x)= \displaystyle\,N_{n}(x)-x; \displaystyle W^{213}_{n,n-3}(x)= \displaystyle\,N_{n}(x)-3x-(2n-5)x^{2}; \displaystyle W^{213}_{n,n-4}(x)= \displaystyle\,N_{n}(x)-(6x+(8n-26)x^{2}+(2n-7)(n-3)x^{3}). Theorem 7 . For n\geq 4 , we have that \displaystyle W^{132}_{n,n-2}(x)=

Read the complete text