Kaimei Huang,

Sherry H.F. Yan · 2025

Read Kaimei Huang, by Sherry H.F. Yan (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-2501-12083.txt.

Introduction

Kaimei Huang and Sherry Yan settle a conjecture in the combinatorics of permutations. Two classic statistics, descents and major index, share their distribution with excedances and Denert's statistic. Rawlings generalized the first pair by a parameter, creating a notion of Euler-Mahonian pairs at each level. Liu conjectured that a certain gap-and-level pair of statistics forms such a pair.

The authors prove the conjecture for all positive values of its two parameters. Their proof is bijective: they build an explicit matching that carries one distribution onto the other. A second result covers a shifted variant of the pair, again at every parameter choice. Setting both parameters to one recovers the classical equidistribution first conjectured by Denert and proved by Foata and Zeilberger. The work extends a nineteenth-century style symmetry into a two-parameter family.

Catalog record

CREATORSherry H.F. Yan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12083

Browse the full library · About the Tower of Babel

Full text

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

Kaimei Huang, Sherry H.F. Yan Abstract Further results on r -Euler-Mahonian statistics Abstract. As natural generalizations of the descent number ( \mathsf{des} ) and the major index ( \mathsf{maj} ), Rawlings introduced the notions of the r -descent number ( r\mathsf{des} ) and the r -major index ( r\mathsf{maj} ) for a given positive integer r . A pair (\mathsf{st}_{1},\mathsf{st}_{2}) of permutation statistics is said to be r -Euler-Mahonian if (\mathrm{st_{1}},\mathrm{st_{2}}) and (r\mathsf{des},r\mathsf{maj}) are equidistributed over the set \mathfrak{S}_{n} of all permutations of \{1,2,\ldots,n\} . The main objective of this paper is to confirm a recent conjecture posed by Liu which asserts that (g\mathsf{exc}_{\ell},g\mathsf{den}_{\ell}) is (g+\ell-1) -Euler-Mahonian for all positive integers g and \ell , where g\mathsf{exc}_{\ell} denotes the g -gap \ell -level excedance number and g\mathsf{den}_{\ell} denotes the g -gap \ell -level Denert’s statistic. This is accomplished via a bijective proof of the equidistribution of (g\mathsf{exc}_{\ell},g\mathsf{den}_{\ell}) and (r\mathsf{des},r\mathsf{maj}) where r=g+\ell-1 . Setting g=\ell=1 , our result recovers the equidistribution of (\mathsf{des},\mathsf{maj}) and (\mathsf{exc},\mathsf{den}) , which was first conjectured by Denert and proved by Foata and Zeilberger. Our second main result is concerned with the analogous result for (g\mathsf{exc}_{\ell},g\mathsf{den}_{g+\ell}) which states that (g\mathsf{exc}_{\ell},g\mathsf{den}_{g+\ell}) is (g+\ell-1) -Euler-Mahonian for all positive integers g and \ell . Keywords : r -major index, r -descent number, g -gap \ell -level Denert’s statistic, g -gap \ell -level excedance number, r -Euler-Mahonian statistic. AMS Subject Classifications : 05A05, 05A19 1 Introduction Let \mathfrak{S}_{n} denote the set of permutations of [n]:=\{1,2,\ldots,n\} . A permutation \pi\in\mathfrak{S}_{n} is usually written in one-line notation as \pi=\pi_{1}\pi_{2}\cdots\pi_{n} . Given a permutation \pi\in\mathfrak{S}_{n} , a pair (i,j) is called an inversion of \pi if i<j and \pi_{i}>\pi_{j} . Let \mathsf{inv}(\pi) denote the number of inversions of \pi . Define the descent set of \pi as \mathsf{Des}(\pi)=\{i\mid\pi_{i}>\pi_{i+1},\,\,1\leq i\leq n-1\}. The descent number of \pi , denoted by \mathsf{des}(\pi) , is defined to be the cardinality of the set \mathsf{Des}(\pi) . The major index of \pi is defined as \mathsf{maj}(\pi)=\sum\limits_{i\in\mathsf{Des}(\pi)}i. The well-known MacMahon’s equidistribution theorem [ 12 ] states that \sum\limits_{\pi\in\mathfrak{S}_{n}}q^{\mathrm{inv(\pi)}}=\sum\limits_{\pi\in\mathfrak{S}_{n}}q^{\mathrm{maj(\pi)}}=[n]_{q}[n-1]_{q}\ldots[1]_{q}, (1.1) where [k]_{q}:=1+q+q^{2}+\ldots+q^{k-1} . Any permutation statistic equidistributed with \mathsf{inv} is said to be Mahonian . Various interesting extensions of MacMahon’s equidistribution theorem have been obtained for other combinatorial objects (see e.g. [ 1 , 2 , 10 , 11 , 15 , 16 ] ). Let r\geq 1 . Rawlings [ 13 ] introduced the notions of r -descent number and r -major index , which are natural generalizations of the descent number and the major index. Let r\geq 1 . Given a permutation \pi=\pi_{1}\pi_{2}\ldots\pi_{n}\in\mathfrak{S}_{n} , define the r -descent set and the r -inversion set of \pi to be r\mathsf{Des}(\pi)=\{i\in[n-1]\mid\pi_{i}\geq\pi_{i+1}+r\}, r\mathsf{Inv}(\pi)=\{(i,j)\in\mathsf{Inv}(\pi)\mid\pi_{i}<\pi_{j}+r\}, respectively, where \mathsf{Inv}(\pi)=\{(i,j)\mid\pi_{i}>\pi_{j},\,\,i<j\} . The r -descent number of \pi , denoted by r\mathsf{des}(\pi) , is defined to be the cardinality of the set r\mathsf{Des}(\pi) . The r -major index of \pi is defined to be r\mathsf{maj}(\pi)=\sum\limits_{i\in r\mathsf{Des}(\pi)}i+|r\mathsf{Inv}(\pi)|. Clearly, the statistic r\mathsf{maj} interpolates between \mathsf{maj} and \mathsf{inv} since r\mathsf{maj} reduces to \mathsf{maj} when r=1 , and reduces to \mathsf{inv} when r\geq n . Rawlings [ 13 ] presented a bijective proof of the equidistribution of r\mathsf{maj} and \mathsf{inv} over \mathfrak{S}_{n} , thereby proving that r\mathsf{maj} is Mahonian. A pair (\mathsf{st}_{1},\mathsf{st}_{2}) of permutation statistics is said to be r -Euler-Mahonian if \sum\limits_{\pi\in\mathfrak{S}_{n}}t^{\mathsf{st}_{1}(\pi)}q^{\mathsf{st}_{2}(\pi)}=\sum\limits_{\pi\in\mathfrak{S}_{n}}t^{r\mathsf{des}(\pi)}q^{r\mathsf{maj}(\pi)}. Given a permutation \pi=\pi_{1}\pi_{2}\ldots\pi_{n}\in\mathfrak{S}_{n} , an index i , 1\leq i<n , is called an excedance place of \pi if \pi_{i}>i . The excedance number of \pi , denoted by \mathsf{exc}(\pi) , is defined to be the number of excedance places of \pi . Denert [ 4 ] introduced a new permutation statistic \mathsf{den} and conjectured that (\mathsf{exc},\mathsf{den}) has the same distribution as (\mathsf{des},\mathsf{maj}) over \mathfrak{S}_{n} , that is, \sum_{\pi\in\mathfrak{S}_{n}}t^{\mathsf{des}(\pi)}q^{\mathsf{maj}(\pi)}=\sum_{\pi\in\mathfrak{S}_{n}}t^{\mathsf{exc}(\pi)}q^{\mathsf{den}(\pi)}. (1.2) This conjecture was first proved by Foata and Zeilberger [ 5 ] and a bijective proof was provided by Han [ 6 ] . Motivated by finding extensions of ( 1.2 ) for r -Euler-Mahonian statistics, Liu [ 9 ] introduced the notions of g -gap \ell -level excedance number and g -gap \ell -level Denert’s statistic . Fix integers g,\ell\geq 1 . Given a permutation \pi\in\mathfrak{S}_{n} , an index i\in[n-1] is called a g -gap \ell -level excedance place and \pi_{i} is called a g -gap \ell -level excedance letter if \pi_{i}\geq i+g and \pi_{i}\geq\ell . For example, if we let \pi=836295417 , then the 2 -gap 3 -level excedance places of \pi are given by 1,3,5 and the 2 -gap 3 -level excedance letters of \pi are given by 6,8,9 . Let g\mathsf{Excp}_{\ell}(\pi) and g\mathsf{Nexcp}_{\ell}(\pi) denote the set of g -gap \ell -level excedance places of \pi and the set of non- g -gap- \ell -level excedance places of \pi , respectively. Let g\mathsf{Excl}_{\ell}(\pi) denote the set of g -gap \ell -level excedance letters of \pi . Assume that g\mathsf{Excp}_{\ell}(\pi)=\{i_{1},i_{2},\ldots,i_{k}\} with i_{1}<i_{2}<\cdots<i_{k} and g\mathrm{Nexcp}_{\ell}(\pi)=\{j_{1},j_{2},\ldots,j_{n-k}\} with j_{1}<j_{2}<\cdots<j_{n-k} . Define g\mathsf{Exc}_{\ell}(\pi)=\pi_{i_{1}}\pi_{i_{2}}\ldots\pi_{i_{k}}, and g\mathsf{Nexc}_{\ell}(\pi)=\pi_{j_{1}}\pi_{j_{2}}\ldots\pi_{j_{n-k}}. The g -gap \ell -level Denert’s statistic of \pi , denoted by g\mathsf{den}_{\ell}(\pi) , is defined as g\mathsf{den}_{\ell}(\pi)=\sum\limits_{i\in g\mathsf{Excp}_{\ell}(\pi)}(i+g-1)+{\mathsf{inv}}(g\mathsf{Exc}_{\ell}(\pi))+{\mathsf{inv}}(g\mathsf{Nexc}_{\ell}(\pi)). For example, if we let \pi=836295417 , then 2\mathsf{Excp}_{3}(\pi)=\{1,3,5\} , 2\mathsf{Excl}_{3}(\pi)=\{6,8,9\} , 2\mathrm{Nexcp}_{3}(\pi)=\{2,4,6,7,8,9\} , 2\mathsf{Exc}_{3}(\pi)=869 , and 2\mathsf{Nexc}_{3}(\pi)=325417 . Therefore, we have \begin{array}[]{ll}2\mathsf{den}_{3}(\pi)&=\sum\limits_{i\in 2\mathsf{Excp}_{3}(\pi)}(i+g-1)+{\mathsf{inv}}(2\mathsf{Exc}_{3}(\pi))+{\mathsf{inv}}(2\mathsf{Nexc}_{3}(\pi))\\ &=2+4+6+{\mathsf{inv}}(869)+{\mathsf{inv}}(325417)\\ &=19.\end{array} When g=\ell=1 , the statistic g\mathsf{den}_{\ell} reduces to the Denert’s statistic \mathsf{den} introduced by Denert [ 4 ] . The g -gap 1 -level Denert’s statistic of \pi is called the g -gap Denert’s statistic of \pi , denoted by g\mathsf{den}(\pi) . Similarly, The 1 -gap \ell -level Denert’s statistic of \pi is called the \ell -level Denert’s statistic of \pi , denoted by \mathsf{den}_{\ell}(\pi) . The g -gap \ell -level excedance number of \pi , denoted by g\mathsf{exc}_{\ell}(\pi) , is defined to be the number of g -gap \ell -level excedance letters that occurs weakly to the right of \pi_{\ell} , that is, g\mathsf{exc}_{\ell}(\pi)=|\{i\mid\pi_{i}\geq i+g,i\geq\ell\}|. For example, if we let \pi=836295417 , then we have 2\mathsf{exc}_{3}(\pi)=2 . The g -gap 1 -level excedance number of \pi is called the g -gap excedance number of \pi , denoted by g\mathsf{exc}(\pi) . Similarly, the 1 -gap \ell -level excedance number of \pi is called the \ell -level excedance number of \pi , denoted by \mathsf{exc}_{\ell}(\pi) . Recently, Liu [ 9 ] proved that the pair (g\mathsf{exc},g\mathsf{den}) is g -Euler-Mahonian for all g\geq 1 and further posed the following two conjectures. Conjecture 1.1 (Liu [ 9 ] , Conjecture 1) For \ell\geq 1 , the pair (\mathsf{exc}_{\ell},\mathsf{den}_{\ell}) is \ell -Euler-Mahonian. Conjecture 1.2 (Liu [ 9 ] , Conjecture 2) For all g\geq 1 and \ell\geq 1 , the pair (g\mathsf{exc}_{\ell},g\mathsf{den}_{\ell}) is r -Euler-Mahonian, where r=g+\ell-1 . It should be mentioned that Conjecture 1.1 has been confirmed by Huang-Lin-Yan [ 8 ] . Our second main result is concerned with the following analogous result of Conjecture 1.2 . Theorem 1.3 For all g\geq 1 and \ell\geq 1 , the pair (g\mathsf{exc}_{\ell},g\mathsf{den}_{g+\ell}) is r -Euler-Mahonian, where r=g+\ell-1 . From Table 1 , one can easily see that \begin{array}[]{lll}\sum\limits_{\pi\in\mathfrak{S}_{4}}t^{3\mathsf{des}(\pi)}q^{3\mathsf{maj}(\pi)}&=&1+3q+5q^{2}+5q^{3}+3q^{4}+q^{5}+tq^{3}+2tq^{4}+2tq^{5}+tq^{6}\\ &=&\sum\limits_{\pi\in\mathfrak{S}_{4}}t^{2\mathsf{exc}_{2}}q^{2\mathsf{den}_{4}}.\end{array} Table 1: The values of the pairs ( 3\mathsf{des} , 3\mathsf{maj} ) and ( 2\mathsf{exc}_{2} , 2\mathsf{den}_{4} ) of each permutation in \mathfrak{S}_{4} . \mathfrak{S}_{4} ( 3\mathsf{des} , 3\mathsf{maj} ) ( 2\mathsf{exc}_{2} , 2\mathsf{den}_{4} ) 1234 (0,0) (0,0) 1243 (0,1) (0,1) 1324 (0,1) (0,1) 1342 (0,2) (0,2) 1423 (0,2) (1,3) 1432 (0,3) (1,4) 2134 (0,1)

Read the complete text