Burstein’s permutation conjecture, Hong and Li’s inversion sequence conjecture and restricted Eulerian distributions

Abstract

Recently, Hong and Li launched a systematic study of length-four pattern avoidance in inversion sequences, and in particular, they conjectured that the number of 0021-avoiding inversion sequences can be enumerated by the OEIS entry A218225. Meanwhile, Burstein suggested that the same sequence might also count three sets of pattern-restricted permutations. The objective of this paper is not only a confirmation of Hong and Li’s conjecture and Burstein’s first conjecture but also two more delicate generating function identities with the $\mathsf{ides}$ statistic concerned in the restricted permutation case and the $\mathsf{asc}$ statistic concerned in the restricted inversion sequence case, which yield a new equidistribution result.

1. Introduction

The history of the study of patterns in permutations dates back to the first volume of MacMahon’s 1915 magnum opus Combinatory Analysis [17, Vol. I, Sect. III, Ch. V]. Meanwhile, modern treatment of permutation classes is commonly known to have its first appearance in Knuth’s Volume 1 of The Art of Computer Programming [12, Sect. 2.2.1], another masterpiece in discrete mathematics and computer science. See Kitaev’s monograph [11] and Vatter’s survey [22] for detailed accounts of this charming history.

Let $\mathfrak{S}_n$ be the set of permutations of $\{1,2,\ldots,n\}=:[n]$. We know that it has a natural coding using $\mathbf{I}_n:=\{(e_1,e_2,\ldots,e_n):0\le e_i \lt i\}$ given by

(1.1)\begin{align} \Theta:\pi=(\pi_1,\pi_2,\ldots,\pi_n)\mapsto (e_1,e_2,\ldots,e_n),\quad\text{where}\ e_i=|\{j \lt i:\pi_j \gt \pi_i\}|. \end{align}

Since the sum of the entries in $\Theta(\pi)$ gives the number of inversions (i.e., pairs (i, j) with i < j and $\pi_i \gt \pi_j$) of π, we usually call sequences in I_n inversion sequences of length n.

Given a sequence $W=w_1w_2\cdots w_n$, we say that W contains a fixed pattern $P=p_1p_2\cdots p_k$ if there is a subsequence of W that is order isomorphic to P. Otherwise, we say that W avoids the pattern P. For example, the sequence $w_1w_2\cdots w_6=315\,616$ contains the pattern 011 since the subsequence $w_1w_4w_6=366$ is order isomorphic to 011 but avoids 201 since none of the subsequences are order isomorphic to this pattern.

In general, for $P_1,\ldots,P_r$, a family of patterns, we denote by $\mathfrak{S}_n(P_1,\ldots,P_r)$ (respectively, $\mathbf{I}_n(P_1,\ldots,P_r)$) the set of permutations (respectively,  inversion sequences) that simultaneously avoid $P_1,\ldots,P_r$.

One of the most important questions in the prolific study of patterns in permutations or inversion sequences concerns the enumeration of sequences avoiding a certain family of patterns. As a well-known example [11, Proposition 2.1.3], one has $|\mathfrak{S}_n(231)|=\frac{1}{n+1}\binom{2n}{n}$, the nth Catalan number. This result is partly attributed to Knuth [12, pp. 242–243]. For pattern avoidance in inversion sequences, on the other hand, we witness the pioneering works of Corteel et al. [5] and Mansour–Shattuck [18]. For instance, $|\mathbf{I}_n(012)|$ equals the $(2n-1)$th Fibonacci number, while $|\mathbf{I}_n(000)|$ is the $(n+1)$th Euler number. Further intriguing connections between pattern avoiding permutations and pattern avoiding inversion sequences were investigated extensively in [13–16].

It is worth noting that for permutations, when the pattern family contains patterns of different lengths, their enumerations enjoy wide-ranging motivations and may lead to unexpected links. For instance, as a byproduct from their combinatorial study of Schubert polynomials, Billey et al. [1] showed that

\begin{equation*}|\mathfrak{S}_n(321,2143)|=2^{n+1}-\binom{n+1}{3}-2n-1. \end{equation*}

A result involving patterns of lengths 4 and 6, which was first conjectured by Egge and later confirmed by Burstein and Pantone [3] and Bloom and Burstein [2], states that for each $\tau\in\{246135,254613,524361,546132,263514\}$, we have

\begin{equation*}|\mathfrak{S}_n(2143,3142,\tau)|=\sum_{d=0}^n\frac{1}{n-d+1}\binom{2n-d}{n-d,n-d,d},\end{equation*}

the nth large Schröder number. Quite recently, during his systematic investigation of West’s ‘stack-sorting map’, Defant [6] enumerated $\mathfrak{S}_n(2341,3241,45231)$ by recognizing it as the set of preimages of $\mathfrak{S}_n(231,321)$.

As the study of such enumerations continues, many open problems also emerge in an endless stream. Let

\begin{equation*}\mathcal{A}(x)=\sum_{n\ge 1}a(n)x^n:=x+2x^2+6x^3+23x^4+101x^5+480x^6+\cdots \end{equation*}

be the unique formal power series solution to the functional equation:

(1.2)\begin{align} \mathcal{A}(x)=\big(1+\mathcal{A}(x)\big)\big(x+\mathcal{A}(x)^2-x\mathcal{A}(x)^2\big). \end{align}

By the Lagrange inversion formula, we have

\begin{align*} a(n)&=\frac{1}{n}[x^{n-1}]\biggl(\frac{1}{1-x-x^2}+x\biggr)^n\\ &=\frac{1}{n}\sum_{k=0}^{n-1}\binom{n}{k+1}[x^k](1-x-x^2)^{-(k+1)}\\ &=\frac{1}{n}\sum_{k=0}^{n-1}\binom{n}{k+1}\sum_{j=0}^k\binom{k+j}{j}\binom{j}{k-j}. \end{align*}

The coefficients of $\mathcal{A}(x)$ are registered as sequence A218225¹ in the OEIS [21]. On 20 December 2017, Burstein posed in [21, A218225] the following conjecture.

Conjecture 1.1. (Burstein)

The value a(n) counts the number of permutations of length n that avoid one of the following sets of patterns:

\begin{equation*}(3124, 42153, 24153),\quad (2134, 42153, 24153),\quad (2143, 42135, 24135).\end{equation*}

On the other hand, following Chern’s work [4] on 0012-avoiding inversion sequences, Hong and Li [10] recently presented a systematic study of other length-four pattern restricted cases. In particular, they conjectured that the series $\mathcal{A}(x)$ also generates $|\mathbf{I}_n(0021)|$; see [10, Conjecture 23].

Conjecture 1.2. (Hong–Li)

The value a(n) counts the number of inversion sequences of length n that avoid the pattern 0021.

Yet another topic of substantial significance is the investigation of various statistics for permutations or inversion sequences. Here, we list a few of them that are commonly used: for w a permutation or an inversion sequence of length n,

• ▹ the number of ascents: $\mathsf{asc}(w):=|\{i\in[n-1]:w_i \lt w_{i+1}\}|$;

• ▹ the number of descents: $\mathsf{des}(w):=|\{i\in[n-1]:w_i \gt w_{i+1}\}|$;

for π a permutation of length n,

• ▹ the number of inverse descents: $\mathsf{ides}(\pi):=\mathsf{des}(\pi^{-1})$, where π ⁻¹ is the inverse permutation of π;

• ▹ the number of excedances: $\mathsf{exc}(\pi):=|\{i\in[n]:\pi_i \gt i\}|$;

for e an inversion sequence of length n,

• ▹ the number of distinct positive entries: $\mathsf{dist}(e):=|\{e_i:i\in[n]\ \text{and}\ e_i \gt 0\}|$.

Recall that for $n\ge 1, k\ge 0$, the Eulerian numbers are defined by

\begin{equation*}\left \langle \begin{matrix} n \\ k \end{matrix} \right \rangle :=\sum_{j=0}^{k+1} (-1)^j \binom{n+1}{j} (k-j+1)^n.\end{equation*}

We may also define the Eulerian polynomials by

\begin{equation*}E_n(t):=\sum_{k=0}^{n-1}\left \langle \begin{matrix} n \\ k \end{matrix} \right \rangle t^k.\end{equation*}

It is known (see, e.g. [19, Sect. 1.4]) that

\begin{equation*}\sum_{\pi\in\mathfrak{S}_n}t^{\mathsf{des}(\pi)} = E_n(t).\end{equation*}

Usually, we say that a statistic is Eulerian if its distribution gives $E_n(t)$. Thus, $\mathsf{des}$, and equivalently, $\mathsf{asc}$ and $\mathsf{ides}$ are Eulerian over permutations. Also, a direct implication of the natural coding Θ in Equation (1.1) is that for any $\pi\in\mathfrak{S}_n$, $\mathsf{des}(\pi)=\mathsf{asc}(\Theta(\pi))$. Hence, $\mathsf{asc}$ is also Eulerian over inversion sequences. For some nontrivial examples, Foata and Schützenberger [8] showed by a bijection called the ‘transformation fondamentale’ from $\mathfrak{S}_n$ to itself that $\mathsf{exc}$ is Eulerian over permutations, and Dumont [7] proved that $\mathsf{dist}$ is Eulerian over inversion sequences.

In general, two statistics that are equidistributed over permutations and/or inversion sequences are a priori no longer equidistributed when the two sets are restricted by certain pattern avoidance conditions, even if the two restricted subsets are already known to be equinumerous. However, there are still a few exceptions. For example, by the works of Corteel et al. [5] and Fu et al. [9],

(1.3)\begin{align} \sum_{\pi\in\mathfrak{S}_n(2413,3142)}t^{\mathsf{des}(\pi)} = \sum_{e\in\mathbf{I}_n(021)} t^{\mathsf{asc}(e)}. \end{align}

Inspired by the above relation, Lin and Kim [14] constructed a bijection between $\mathfrak{S}_n(2413,4213)$ and $\mathbf{I}_n(021)$, which proves a surprising sextuple equidistribution, including the set-valued statistics of the positions of descents and ascents.

In this paper, we will focus our attention on Burstein’s first conjecture and Hong and Li’s conjecture, but also with statistics considered. To begin with, we generalize the series $\mathcal{A}(x)$ as

(1.4)\begin{align} \mathcal{A}(x,t):=x + (1 + t) x^2 + (1 + 4 t + t^2) x^3 + (1 + 10 t + 11 t^2 + t^3) x^4 + \cdots, \end{align}

which is the unique formal power series solution to the functional equation:

(1.5)\begin{align} \mathcal{A}(x,t)=\big(1+\mathcal{A}(x,t)\big)\big(x+t \mathcal{A}(x,t)^2 - xt^2 \mathcal{A}(x,t)^2\big). \end{align}

Note that $\mathcal{A}(x,1)=\mathcal{A}(x)$.

The main result of this paper is the following theorem, which affords us two combinatorial interpretations of $\mathcal{A}(x,t)$ in terms of the Eulerian distributions over pattern restricted permutations and inversion sequences, respectively.

Theorem 1.1. Let $\mathcal{A}(x,t)$ be as in Equation (1.4). Then

(1.6)\begin{align} \sum_{n\ge 1}x^n\sum_{\pi\in\mathfrak{S}_n(3124, 42153, 24153)}t^{\mathsf{ides}(\pi)} = \mathcal{A}(x,t) \end{align}

and

(1.7)\begin{align} \sum_{n\ge 1}x^n\sum_{e\in\mathbf{I}_n(0021)}t^{\mathsf{asc}(e)} = \mathcal{A}(x,t). \end{align}

Hence, $\mathsf{ides}$ over $\mathfrak{S}_n(3124, 42153, 24153)$ is equidistributed with $\mathsf{asc}$ over $\mathbf{I}_n(0021)$.

The following is a quick consequence of our main result by setting t = 1.

Corollary 1.2. (i). Burstein’s First Conjecture is true, i.e. Conjecture 1.1 is true for $(3124, 42153, 24153)$; (ii). Hong and Li’s Conjecture 1.2 is true.

2. Burstein’s first conjecture with inverse descents

For convenience, we write $I:=\{3124,42153,24153\}$, the set of patterns in Burstein’s first conjecture. Let us define

(2.1)\begin{align} \mathcal{P}(x,t):=\sum_{n\ge 1}x^n\sum_{\pi\in \mathfrak{S}_{n}(I)}t^{\mathsf{ides}(\pi)}. \end{align}

We begin with some useful definitions and initial observations.

We associate with each permutation $\pi\in\mathfrak{S}_{n+1}$ a unique word w_π of length n consisting of letters $\mathrm{L}$ and $\mathrm{R}$ as follows. Suppose $\pi_k=1$, we let

\begin{equation*} w_{\pi}=w_1w_2\cdots w_n,\quad \text{where}\ w_i:=\begin{cases} \mathrm{L}, & \text{if}\ \pi_j=i+1\ \text{for a certain}\ j \lt k,\\ \mathrm{R}, & \text{if}\ \pi_j=i+1\ \text{for a certain}\ j \gt k. \end{cases} \end{equation*}

Intuitively, as we scan the entries of π from 2 to n + 1, the word w_π simply records whether we are at a position that is to the left or right of the entry 1. We introduce the length of the longest alternating subword of any word w on the alphabet $\{\mathrm{L},\mathrm{R}\}$:

\begin{equation*}\mathsf{alt}(w):=\max\{|u|:u\ \text{is a subword of}\ w\ \text{ with no consecutively repeated letters}\}.\end{equation*}

For a permutation $\pi\in\mathfrak{S}_n$, we define

• ▹ the alternating length: $\mathsf{alt}(\pi):=0$ for n = 1, and $\mathsf{alt}(\pi):=\mathsf{alt}(w_{\pi})$ for $n\ge 2$.

Denote $\mathfrak{S}_{n,k}$ the set of permutations in $\mathfrak{S}_n$ with alternating length equal to k.

Example 2.1. The permutation π = 547912683 corresponds to the word $w_{\pi}=\mathrm{R}\mathrm{R}\mathrm{L}\mathrm{L}\mathrm{R}\mathrm{L}\mathrm{R}\mathrm{L}$ (for $2,3$ are to the Right of 1; 4 is to the Left of 1; etc.). Thus, $\mathsf{alt}(\pi)=6$ and $\pi\in\mathfrak{S}_{9,6}$.

The next lemma explains why it might be a good idea to refine $\mathfrak{S}_n$ as $\mathfrak{S}_{n,k}$ when we deal with $\mathfrak{S}_n(I)$.

Lemma 2.1. For each permutation $\pi\in\mathfrak{S}_n(I)$, there is no subword of w_π of the form $\mathrm{L}\mathrm{R}\mathrm{L}\mathrm{R}$. Consequently, we have $\mathsf{alt}(\pi)\le 4$, and in particular, if w_π starts with $\mathrm{L}$ (i.e. $\pi^{-1}_2 \lt \pi^{-1}_1$), we have $\mathsf{alt}(\pi)\le 3$.

Proof. Taking any permutation $\pi\in\mathfrak{S}_n(I)$ with $\pi_k=1$, suppose on the contrary that $\mathrm{L}\mathrm{R}\mathrm{L}\mathrm{R}$ is a subword of w_π. Then it is always possible to find four indices $a,b,c,d$, such that

1. (1) a < k, b < k and c > k, d > k;

2. (2) $\pi_a \lt \pi_c \lt \pi_b \lt \pi_d$.

Furthermore, since π avoids the pattern 3124, we must have d < c. But then if a < b, we see

\begin{equation*}\pi_a,\pi_b,\pi_k=1,\pi_d,\pi_c\end{equation*}

matches the pattern 24153; while if a > b, we get from

\begin{equation*}\pi_b,\pi_a,\pi_k=1,\pi_d,\pi_c\end{equation*}

the pattern 42153. Either case contradicts with the fact that $\pi\in\mathfrak{S}_n(I)$.

Throughout, we make the following decomposition

\begin{align*} \mathfrak{S}_n(I) &= \biguplus_{i=0}^4 \mathfrak{S}_{n,i}(I). \end{align*}

Note that if $\mathsf{alt}(\pi)=t$, then the longest alternating subword of w_π could be either

\begin{equation*}u=\underbrace{\mathrm{L}\mathrm{R}\mathrm{L}\ldots}_{t}\quad\text{or}\quad u=\underbrace{\mathrm{R}\mathrm{L}\mathrm{R}\ldots}_{t}.\end{equation*}

Fortunately, according to the next lemma, it suffices to investigate the first case. For $k\ge 1$, we decompose $\mathfrak{S}_{n,k}$ further into two disjoint subsets (with $\pi_i^{-1}$ the ith entry of π ⁻¹):

\begin{align*} \mathfrak{S}_{n,k}^{L}&:=\{\pi\in\mathfrak{S}_{n,k}: \pi^{-1}_2 \lt \pi^{-1}_1\},\\ \mathfrak{S}_{n,k}^{R}&:=\{\pi\in\mathfrak{S}_{n,k}: \pi^{-1}_2 \gt \pi^{-1}_1\}. \end{align*}

We then denote the corresponding generating functions for those permutations avoiding the pattern set I as

\begin{align*} \mathcal{P}_k^L(x,t) &:=\sum_{n\ge 2}x^n\sum_{\pi\in \mathfrak{S}_{n,k}^L(I)}t^{\mathsf{ides}(\pi)},\\ \mathcal{P}_k^R(x,t) &:=\sum_{n\ge 2}x^n\sum_{\pi\in \mathfrak{S}_{n,k}^R(I)}t^{\mathsf{ides}(\pi)}, \end{align*}

respectively.

Lemma 2.2. We have

(2.2)\begin{align} \mathcal{P}_1^R(x,t)=x\mathcal{P}(x,t), \end{align}

and for $1\le k\le 3$,

(2.3)\begin{align} \mathcal{P}_{k+1}^R(x,t)=\mathcal{P}_{k}^L(x,t)\mathcal{P}(x,t). \end{align}

Proof. Given any permutation $\pi=\pi_1\cdots\pi_n\in\mathfrak{S}_n(I)$, we see that $\hat{\pi}=1(\pi_1+1)\cdots(\pi_n+1)$ is a permutation in $\mathfrak{S}_{n+1,1}^R(I)$. Conversely, every permutation in $\mathfrak{S}_{n+1,1}^R(I)$ must begin with 1 and recovers uniquely a permutation in $\mathfrak{S}_n(I)$ once the 1 is removed and all remaining entries decrease by 1. Noting that this correspondence also preserves the $\mathsf{ides}$ statistic, we arrive at Equation (2.2).

Similarly, for $1\le k\le 3$, we can construct a bijection

\begin{align*} \begin{array}{cccc} \phi: & \bigcup_{n\ge 2}\mathfrak{S}_{n,k}^L(I)\times\bigcup_{n\ge 1}\mathfrak{S}_{n}(I) & \to & \bigcup_{n\ge 2}\mathfrak{S}_{n,k+1}^R(I),\\[6pt] & (\sigma,\mu) & \mapsto & \pi, \end{array} \end{align*}

where the image π is obtained from the pair $(\sigma,\mu)$ by first concatenating σ with µ, then increasing each entry of σ larger than 1 by $|\mu|$ and each entry of µ by 1. For instance,

\begin{equation*}\phi(6271435,3142)=10\:6\:11\:1\:8\:7\:9\:4\:2\:5\:3.\end{equation*}

A moment of reflection should reveal that regardless of k = 1, 2 or 3, ϕ is well-defined and indeed a bijection satisfying that $|\phi(\sigma,\mu)|=|\sigma|+|\mu|$. In terms of generating function, we see that Equation (2.3) holds by further noting that $\mathsf{ides}(\pi)=\mathsf{ides}(\sigma)+\mathsf{ides}(\mu)$, since the eliminated inverse descent from $\sigma_1^{-1} \gt \sigma_2^{-1}$ is compensated by $\pi_{|\mu|+1}^{-1} \gt \pi_{|\mu|+2}^{-1}$.

Noting from Lemma 2.1 that $\mathfrak{S}_{n,4}^L(I)=\varnothing$ for all $n\ge 1$, we have

(2.4)\begin{equation} \mathcal{P}_{4}^L(x,t)=0. \end{equation}

Now, it remains to compute $\mathcal{P}_1^L(x,t)$, $\mathcal{P}_2^L(x,t)$ and $\mathcal{P}_3^L(x,t)$. We collect them in the next lemma.

Lemma 2.3. We have

(2.5)\begin{align} \mathcal{P}_1^L(x,t) &= xt\mathcal{P}(x,t), \end{align}

(2.6)\begin{align} \mathcal{P}_2^L(x,t) &= xt\mathcal{C}(x,t)\mathcal{P}(x,t), \end{align}

(2.7)\begin{align} \mathcal{P}_3^L(x,t) &= t\big(\mathcal{P}(x,t)-x-xt\mathcal{P}(x,t)-x\mathcal{C}(x,t)\big)\mathcal{P}(x,t), \end{align}

where

\begin{equation*}\mathcal{C}(x,t)=\sum_{n\ge 1}x^n\sum_{\pi\in \mathfrak{S}_n(312)}t^{\mathsf{ides}(\pi)}.\end{equation*}

Proof. First, Equation (2.5) can be derived bijectively in the same way as we prove Equation (2.2), except that now we append 1 at the right end, thereby increasing the $\mathsf{ides}$ statistic by 1.

For Equation (2.6), suppose that $\pi\in\mathfrak{S}_{n,2}^L(I)$ decomposes as $\pi=u 1 v$ with $\max(u) \lt \min(v)$. Now as two subwords of π, u and v each should avoid the three patterns contained in I. More precisely, we see that u actually avoids the pattern 312, since any occurrence of 312 in u together with one entry from v outputs the pattern 3124. Conversely, by concatenating a permutation $\sigma\in\mathfrak{S}_m(312)$ with 1 and a permutation $\mu\in\mathfrak{S}_l(I)$, then increasing every entry in σ by 1 and every entry in µ by m + 1, we get a permutation $\pi\in\mathfrak{S}_{m+l+1,2}^L(I)$. This bijection gives us Equation (2.6) by noting that $\mathsf{ides}(\pi)=\mathsf{ides}(\sigma)+\mathsf{ides}(\mu)+1$ for the inverse descent from $\pi_1^{-1} \gt \pi_2^{-1}$ gives the additional ‘plus one’.

The proof of Equation (2.7) requires a bijection that is less obvious. We begin with any permutation $\sigma=\sigma_1\cdots\sigma_n\in\mathfrak{S}_n(I)$. Increasing all entries by 1 and inserting 1 at the penultimate position yield

\begin{equation*}\tilde{\sigma}=(\sigma_1+1)\cdots(\sigma_{n-1}+1)1(\sigma_n+1).\end{equation*}

Let us decide under what conditions $\tilde{\sigma}$ would be a permutation in $\mathfrak{S}_{n+1,3}^L(I)$.

1. (1) $n\ge 2$. This explains the term ‘−x’.

2. (2) $\sigma_n \gt 1$. Otherwise, $\sigma_n=1$ and $\sigma\in\mathfrak{S}_{n,1}^L(I)$. So by Equation (2.5), this explains the term ‘$-xt\mathcal{P}(x,t)$’.

3. (3) $\sigma_n \lt n$. Otherwise, $\sigma_n=n$ and $\sigma_1\cdots\sigma_{n-1}\in\mathfrak{S}_{n-1}(312)$. So this explains the term ‘$-x\mathcal{C}(x,t)$’.

If conditions (1), (2) and (3) are all satisfied, we see that $\tilde{\sigma}$ is indeed a permutation in $\mathfrak{S}_{n+1,3}^L(I)$ with 1 being at the penultimate position. To reach all permutations in $\bigcup_{i\ge 4}\mathfrak{S}_{i,3}^L(I)$, we simply ‘inflate’ the last entry of $\tilde{\sigma}$ into any permutation $\mu\in\mathfrak{S}(I)$ (i.e., increase each entry in µ by σ_n to get $\tilde{\mu}$ and then replace the last entry of $\tilde{\sigma}$ with $\tilde{\mu}$) and then adjust the remaining entries of $\tilde{\sigma}$ if necessary (i.e., increase by an appropriate amount and preserve their original relative order relations). Denote the output permutation as π. Now, this final step of ‘inflation’ corresponds to multiplying by $t\mathcal{P}(x,t)$, by further noting that $\mathsf{ides}(\pi)=\mathsf{ides}(\tilde{\sigma})+\mathsf{ides}(\mu)=1+\mathsf{ides}(\sigma)+\mathsf{ides}(\mu)$. For example, if

\begin{equation*}\sigma=4213 \quad\text{and}\quad \mu=41523,\end{equation*}

we follow the above steps to produce

\begin{equation*}\tilde{\sigma}=532\:1\:4 \quad{and}\quad \tilde{\mu}=74856 \quad{and}\quad \pi=932\:1\:74856.\end{equation*}

It is not hard to see that the whole process is invertible. Namely, we take any permutation from $\bigcup_{n\ge 4}\mathfrak{S}_{n,3}^L(I)$, ‘concentrate’ all the entries to the right of 1 into its minimum to recover $\tilde{\sigma}$ after standardization and then remove 1 and decrease other entries by 1 to further recover σ, which must be a permutation in $\mathfrak{S}_n(I)$ that satisfies conditions (1), (2) and (3). In summary, $(\sigma,\mu)\mapsto \pi$ is a bijection and (2.7) is now proved.

Finally, we are in a position to conclude the proof of Equation (1.6).

Proof of Equation (1.6)

Putting together these generating function relations, we can deduce the following functional equation:

\begin{align*} \mathcal{P}(x,t) &= \left(x+\mathcal{P}_1^R(x,t)\right)+\left(\mathcal{P}_1^L(x,t)+\mathcal{P}_2^R(x,t)\right)+\left(\mathcal{P}_2^L(x,t)+\mathcal{P}_3^R(x,t)\right)\\ &\quad+\left(\mathcal{P}_3^L(x,t)+\mathcal{P}_4^R(x,t)\right)+\mathcal{P}_4^L(x,t)\\ &= \left(1+\mathcal{P}(x,t)\right)\left[x+xt \mathcal{P}(x,t)+xt \mathcal{C}(x,t)\mathcal{P}(x,t)\right.\\ &\left.\quad+t\left(\mathcal{P}(x,t)-x-xt\mathcal{P}(x,t)-x\mathcal{C}(x,t)\right)\mathcal{P}(x,t)\right]\\ &= \left(1+\mathcal{P}(x,t)\right)\left(x+t\mathcal{P}(x,t)^2-xt^2\mathcal{P}(x,t)^2\right), \end{align*}

which simplifies to an identical equation as Equation (1.5). Hence, we arrive at Equation (1.6).

3. Hong and Li’s conjecture

For any inversion sequence $e\in\mathbf{I}_n$, it is always possible to find a unique index p such that $e_i=i-1$ for $1\le i\le p$ and $e_{p+1}\le p-1$. Note that here p may take the value n, in which case, we shall view the entry $e_{n+1}$, which does not exist, as $-\infty$. We define

• ▹ the initial ascending run: $\mathsf{iar}(e):=p$, the aforementioned index.

Now, we consider a generalization of inversion sequences introduced by Savage and Schuster [20].

Definition 3.1. Let $\mathbf{s}=(s_1,s_2,\ldots,s_n)$ be a fixed sequence of positive integers. A sequence $e=(e_1,e_2,\ldots,e_n)$ is an s-inversion sequence if $0\le e_i \lt s_i$ for all $1\le i\le n$. Further, an entry e_i is tight if $e_i=s_i-1$.

For e an s-inversion sequence of length n, we define

• ▹ the number of tight entries: $\mathsf{tig}(e):=|\{i\in[n]:e_i=s_i-1\}|$.

From the concept of the initial ascending runs, we are naturally led to the set of $(p,p+2,p+3,\ldots,p+n)$-inversion sequences, denoted by $\mathbf{I}_{n,p}$, for n and p positive integers. The following lemma is easy but crucial.

Lemma 3.1. Fix positive integers p and n. There is a natural one-to-one correspondence between

\begin{equation*} \{e\in\mathbf{I}_{n+p}(0021):\mathsf{iar}(e)=p\}\quad\text{and}\quad \mathbf{I}_{n,p}(021). \end{equation*}

Proof. As every sequence $e\in\mathbf{I}_{n+p}(0021)$ with $\mathsf{iar}(e)=p$ is of the form $(0,1,2,\ldots,p-1,e_{p+1},e_{p+2},\ldots,e_{p+n})$ such that $0\leq e_{p+1}\leq p-1$, deleting the first p entries of e produces the sequence $\hat{e}=(e_{p+1},e_{p+2},\ldots,e_{p+n})\in\mathbf{I}_{n,p}$. It is routine to check that $\hat{e}$ is a sequence in $\mathbf{I}_{n,p}(021)$ and this correspondence is one-to-one.

Let

(3.1)\begin{align} \mathcal{I}(x):=\sum_{n\geq1}|\mathbf{I}_n(0021)|x^n. \end{align}

The objective of this section is a short proof of Hong and Li’s conjecture, without considering the $\mathsf{asc}$ statistic. To begin with, we introduce the generating function

\begin{equation*} \mathcal{H}(x,s,q):=\sum_{n,p\geq1}x^ns^p\sum_{e\in\mathbf{I}_{n,p}(021)}q^{\mathsf{tig}(e)}. \end{equation*}

We also write the coefficients as

\begin{align*} h_p(x,q)&:=[s^p]\mathcal{H}(x,s,q),\\ h_{p,k}(x)&:=[s^pq^k]\mathcal{H}(x,s,q). \end{align*}

First proof of Hong and Li’s conjecture

Let $e=(e_1,\ldots,e_n)\in\mathbf{I}_{n,p}(021)$. We decompose e by considering its rightmost tight entry. There are two cases:

(1). e has no tight entry. Such sequences are in one-to-one correspondence with the sequences in $\mathbf{I}_{n,p-1}(021)$ and thus contribute the generating function

\begin{equation*} \sum_{p\geq2}h_{p-1}(x,1)s^p=s\mathcal{H}(x,s,1). \end{equation*}

(2). e has at least one tight entry. Suppose that $e_{\ell}$ is the rightmost tight entry of e. There are four subcases:

(2a). $\it{\ell=n}$. Every such sequence can be obtained from a (possibly empty) sequence in $\mathbf{I}_{n-1,p}(021)$ by adding a tight entry at the end. Thus, this case contributes the generating function

\begin{equation*} \sum_{p\geq1}xq\left(1+h_p(x,q)\right)s^p=xq\left(\frac{s}{1-s}+\mathcal{H}(x,s,q)\right). \end{equation*}

(2b). $\it{1\leq\ell \lt n}$ and $\it{e_{\ell+1}=e_{\ell}}$. Each sequence in this case can be obtained from a sequence in $\mathbf{I}_{n-1,p}(021)$ with at least one tight entry by inserting exactly to the right of any tight entry a new entry of equal size. Note that this construction is in general one-to-multiple, and if it is executed at the jth tight entry, then the resulting sequence has precisely j tight entries. Therefore, this case contributes the generating function

\begin{align*} x\sum_{p,k\geq1}h_{p,k}(x)\left(q+q^2+\cdots+q^k\right)s^p&=x\sum_{p\geq1,k\geq0}h_{p,k}(x)\left(\frac{q-q^{k+1}}{1-q}\right)s^p\\ &=\frac{xq}{1-q}\left(\mathcal{H}(x,s,1)-\mathcal{H}(x,s,q)\right). \end{align*}

(2c). $\it{\ell=1 \lt n}$ and either $\it{e_{\ell+1} \lt e_{\ell}}$ or $\it{e_{\ell+1}=e_{\ell}+1}$. In this case, $e_1=p-1$, and in the latter situation $e_2=p$. Also, the $\mathsf{tig}$ statistic equals 1. Such sequences are in one-to-one correspondence with $\mathbf{I}_{n-1,p}(021)$ by first deleting e ₁, and if $e_2=p$, changing this entry to p − 1. It follows that the sequences in this case contribute the generating function

\begin{equation*} xq\sum_{p\geq1}h_{p}(x,1)s^p=xq\mathcal{H}(x,s,1). \end{equation*}

(2d). $\it{1 \lt \ell \lt n}$ and $\it{e_{\ell+1} \lt e_{\ell}}$. In this case, if we denote $\min\{e_i: 1\leq i \lt \ell\}$ by m, then e can be decomposed into two shorter sequences:

\begin{equation*} \tilde{e}:=(e_1,e_2,\ldots,e_{\ell-1})\in\mathbf{I}_{\ell-1,p,m}(021) \end{equation*}

and

\begin{equation*}\bar{e}:=(\bar e_{\ell+1},\bar e_{\ell+2},\ldots,\bar{e}_n)\in\mathbf{I}_{n-\ell,m+1}(021),\end{equation*}

where $\mathbf{I}_{\ell-1,p,m}(021):=\{e\in\mathbf{I}_{\ell-1,p}(021):\ \text{the minimal entry of}\ e\ \text{is}\ m\}$ and

\begin{equation*} \bar e_i:= \begin{cases} e_i&\text{if}\ e_i \lt e_{\ell}\ (\text{one has}\ e_i\leq m\ \text{since}\ e\ \text{avoids}\ 021)\\ e_i-e_{\ell}+m+1&\text{if}\ e_i\geq e_{\ell}, \end{cases} \end{equation*}

for $\ell+1\leq i\leq n$. This decomposition is reversible. The key observation is that for fixed $p\geq1$ and $0\leq m\leq p-1$, a member in $\mathbf{I}_{\ell,p,m}(021)$ can be obtained from a member $e\in\mathbf{I}_{\ell,p-m}(021)$, provided that e has 0 as its minimal entry. It follows that the generating function $\sum_{\ell\geq1}x^{\ell}\sum_{e\in\mathbf{I}_{\ell,p,m}(021)}q^{\mathsf{tig}(e)}$ equals $h_{p-m}(x,q)-h_{p-m-1}(x,q)$, where by convention $h_0(x,q)=0$. Therefore, this case contributes the generating function

\begin{align*} &\sum_{p\geq1}xqs^p\sum_{m=0}^{p-1}\left(h_{p-m}(x,q)-h_{p-m-1}(x,q)\right) h_{m+1}(x,1)\\ &\quad=\frac{xq}{s}\sum_{p\geq1}\sum_{m=0}^{p-1}h_{p-m}(x,q)h_{m+1}(x,1)s^{p+1}-xq\sum_{p\geq1}\sum_{m=0}^{p-1}h_{p-m-1}(x,q)h_{m+1}(x,1)s^p\\ &\quad=xq(1/s-1)\mathcal{H}(x,s,q)\mathcal{H}(x,s,1). \end{align*}

Summing over all the above cases yields the functional equation for $\mathcal{H}(q):=\mathcal{H}(x,s,q)$:

(3.2)\begin{equation} \left(\frac{1-q+xq^2}{1-q}-xq\left(1/s-1\right)\mathcal{H}(1)\right)\mathcal{H}(q)=\left(s+xq+\frac{xq}{1-q}\right)\mathcal{H}(1)+\frac{xqs}{1-s}. \end{equation}

We apply the kernel method to solve Equation (3.2) by setting the kernel polynomial

\begin{equation*}\frac{1-q+xq^2}{1-q}-xq(1/s-1)\mathcal{H}(1)\end{equation*}

to be zero. Then, the right-hand side of Equation (3.2) vanishes. Therefore, $\mathcal{H}(1)$ satisfies the system of equations

(3.3)\begin{equation} \begin{cases} \dfrac{1-q+xq^2}{1-q}-xq(1/s-1)\mathcal{H}(1)=0,\\[12pt] \left(s+xq+\dfrac{xq}{1-q}\right)\mathcal{H}(1)+\dfrac{xqs}{1-s}=0. \end{cases} \end{equation}

Finally, we recall that any inversion sequence in $\mathbf{I}_n(0021)$ is either in correspondence with a sequence in $\mathbf{I}_{n-p,p}(021)$ for some p by Lemma 3.1 or a sequence with only tight entries, which is generated by

\begin{equation*}x+ x^2+ x^3+\cdots = \frac{x}{1-x}.\end{equation*}

Hence,

\begin{equation*} \mathcal{I}(x)=\frac{x}{1-x}+\mathcal{H}(x,x,1). \end{equation*}

Equivalently,

\begin{equation*} \mathcal{H}(x,x,1)=\mathcal{I}(x)-\frac{x}{1-x}. \end{equation*}

Substituting this expression into Equation (3.3) gives the functional equation for $\mathcal{I}(x)$

\begin{equation*} \begin{cases} \dfrac{1-q+xq^2}{1-q}-(1-x)q\left(\mathcal{I}(x)-\dfrac{x}{1-x}\right)=0,\\[12pt] \dfrac{x(1+q-q^2)}{1-q}\left(\mathcal{I}(x)-\dfrac{x}{1-x}\right)+\dfrac{x^2q}{1-x}=0. \end{cases} \end{equation*}

Cancelling q in this system gives

\begin{equation*}\mathcal{I}(x)=\left(1+\mathcal{I}(x)\right)\left(x+\mathcal{I}(x)^2-x\mathcal{I}(x)^2\right),\end{equation*}

which is identical to Equation (1.2).

Remark 3.1. The above analysis does not work well if the $\mathsf{asc}$ statistic is taken into account. The main trouble occurs in Case (2c). Recall that in this case, for $e=(e_1,\ldots,e_n)\in\mathbf{I}_{n,p}(021)$, we have $e_1=p-1$ and either $e_2 \lt p-1$ or $e_2=p$. When $e_2 \lt p-1$, the $\mathsf{asc}$ statistic remains the same after applying the correspondence. However, when $e_2=p$, we find that in the resulting sequence, the $\mathsf{asc}$ statistic decreases by 1 if $e_3\le p-1$ or $e_3=p+1$ and remains the same value if $e_3=p$. Such a bifurcating behaviour of the $\mathsf{asc}$ statistic keeps us away from a neat generating function for this case.

4. Generic 021-avoiding sequences

To attach the $\mathsf{asc}$ statistic to the generating function $\mathcal{I}(x)=\sum_{n\ge 1}|\mathbf{I}_n(0021)|x^n$, we have to undertake a more subtle analysis for $\mathbf{I}_{n,p}$. This propels us to look at generic 021-avoiding sequences. Let N denote the set of sequences of non-negative integers, and let N_n denote the set of sequences of length n in N for $n\ge 1$. For a sequence $w=w_1w_2\cdots w_n\in\mathbf{N}_n$, we define

• ▹ the largest entry: $\mathsf{lar}(w):=\max\{w_i:1\le i\le n\}$;

• ▹ the smallest entry: $\mathsf{sma}(w):=\min\{w_i:1\le i\le n\}$;

• ▹ the rightmost position of the largest entry: $\mathsf{R}_{\mathsf{lar}}(w):=\max\{i:w_i=\mathsf{lar}(w)\}$;

• ▹ the rightmost position of the smallest entry: $\mathsf{R}_{\mathsf{sma}}(w):=\max\{i:w_i=\mathsf{sma}(w)\}$.

Now, we split N into two disjoint types:

\begin{align*} \mathbf{SL}&:=\{w\in\mathbf{N}:\mathsf{R}_{\mathsf{lar}}(w)\ge \mathsf{R}_{\mathsf{sma}}(w)\},\\ \mathbf{LS}&:=\{w\in\mathbf{N}:\mathsf{R}_{\mathsf{lar}}(w) \lt \mathsf{R}_{\mathsf{sma}}(w)\}. \end{align*}

We also write $\mathbf{SL}_n=\mathbf{SL}\cap\mathbf{N}_n$ and $\mathbf{LS}_n=\mathbf{LS}\cap\mathbf{N}_n$.

Define trivariate generating functions:

\begin{align*} \mathcal{N}(x,u)=\mathcal{N}(x,u,t)&:=\sum_{n\ge 1}x^n\sum_{w\in\mathbf{N}_n(021)}u^{\mathsf{lar}(w)}t^{\mathsf{asc}(w)},\\ \mathcal{S}(x,u)=\mathcal{S}(x,u,t)&:=\sum_{n\ge 1}x^n\sum_{w\in\mathbf{SL}_n(021)}u^{\mathsf{lar}(w)}t^{\mathsf{asc}(w)},\\ \mathcal{L}(x,u)=\mathcal{L}(x,u,t)&:=\sum_{n\ge 1}x^n\sum_{w\in\mathbf{LS}_n(021)}u^{\mathsf{lar}(w)}t^{\mathsf{asc}(w)}. \end{align*}

Note that

(4.1)\begin{align} \mathcal{N}(x,u)=\mathcal{S}(x,u)+\mathcal{L}(x,u). \end{align}

Let us write the coefficients as

\begin{align*} N_{[-,\ell]}(x)=N_{[-,\ell]}(x,t)&:=[u^\ell]\mathcal{N}(x,u),\\ S_{[-,\ell]}(x)=S_{[-,\ell]}(x,t)&:=[u^\ell]\mathcal{S}(x,u),\\ L_{[-,\ell]}(x)=L_{[-,\ell]}(x,t)&:=[u^\ell]\mathcal{L}(x,u). \end{align*}

Lemma 4.1. For any $w\in\mathbf{SL}_n(021)$, we have $\mathsf{R}_{\mathsf{lar}}(w)=n$. Namely, the last entry in w is the largest.

Proof. Assume that $\mathsf{R}_{\mathsf{lar}}(w)=j \lt n$. Then for any k with $j \lt k\le n$, we have $w_k \lt \mathsf{lar}(w)$. We also claim that $w_k \gt \mathsf{sma}(w)$. Otherwise, $\mathsf{R}_{\mathsf{lar}}(w) \lt \mathsf{R}_{\mathsf{sma}}(w)$ and thus $w\not\in \mathbf{SL}_n(021)$. The above also indicates that $\mathsf{sma}(w) \lt \mathsf{lar}(w)$. Now we assume that $w_i=\mathsf{sma}(w)$ for some i. Since $\mathsf{R}_{\mathsf{lar}}(w)\ge \mathsf{R}_{\mathsf{sma}}(w)$ and $\mathsf{sma}(w)\ne\mathsf{lar}(w)$, we must have i < j. However, the subsequence $w_iw_jw_k$ satisfies $\mathsf{lar}(w)=w_j \gt w_k \gt w_i=\mathsf{sma}(w)$ with $i \lt j \lt k$ and is therefore order isomorphic to 021, thereby leading to a contradiction.

Lemma 4.2. We have

(4.2)\begin{align} \mathcal{S}(x,u)=\frac{x}{(1-u)(1-x+xt)}+\frac{xt}{(1-u)(1-x+xt)} \mathcal{N}(x,u). \end{align}

Proof. Assume that $n\ge 2$. Let $w=w_1\cdots w_n\in \mathbf{SL}_n(021)$. By Lemma 4.1, we have $w_n=\mathsf{lar}(w)$. Also, we note that the subsequence $w^{\prime}=w_1\cdots w_{n-1}$ is in $\mathbf{N}_{n-1}(021)$. Further, $\mathsf{lar}(w^{\prime})\le w_n$. Hence, any $w\in \mathbf{SL}_n(021)$ can be uniquely generated by a $w^{\prime}\in\mathbf{N}_{n-1}(021)$ appended by an entry $\ell$ no smaller than $\ell^{\prime}:=\mathsf{lar}(w^{\prime})$. To keep track of the ascent statistic, we need to distinguish wʹ depending on whether it is in $\mathbf{LS}_{n-1}(021)$ or $\mathbf{SL}_{n-1}(021)$.

If $w^{\prime}\in \mathbf{LS}_{n-1}(021)$, then the last entry of wʹ is not the largest by the definition of LS, and thus it is smaller than $\ell^{\prime}$. Therefore, $\mathsf{asc}(w)=\mathsf{asc}(w^{\prime})+1$. If $w^{\prime}\in \mathbf{SL}_{n-1}(021)$, then the last entry of wʹ is the largest by Lemma 4.1, and thus it equals $\ell^{\prime}$. Therefore, if $\ell \gt \ell^{\prime}$, we have $\mathsf{asc}(w)=\mathsf{asc}(w^{\prime})+1$; if $\ell=\ell^{\prime}$, we have $\mathsf{asc}(w)=\mathsf{asc}(w^{\prime})$.

Noting that sequences in $\mathbf{SL}_1(021)$ are generated by

\begin{align*} x\sum_{\ell\ge 0}u^\ell = \frac{x}{1-u}, \end{align*}

we have

\begin{align*} \mathcal{S}(x,u)&=\frac{x}{1-u}+\sum_{\ell^{\prime}\ge 0}L_{[-,\ell^{\prime}]}(x)\sum_{\ell\ge \ell^{\prime}}xu^{\ell}t + \sum_{\ell^{\prime}\ge 0}S_{[-,\ell^{\prime}]}(x)\left(xu^{\ell^{\prime}}+\sum_{\ell \gt \ell^{\prime}}xu^{\ell}t\right)\\ &=\frac{x}{1-u}+ \sum_{\ell^{\prime}\ge 0}S_{[-,\ell^{\prime}]}(x)u^{\ell^{\prime}}(x-xt) +\sum_{\ell^{\prime}\ge 0}\left(L_{[-,\ell^{\prime}]}(x)+S_{[-,\ell^{\prime}]}(x)\right)\sum_{\ell\ge \ell^{\prime}}xu^{\ell}t\\ &=\frac{x}{1-u}+ (x-xt)\mathcal{S}(x,u)+\frac{xt}{1-u} \mathcal{N}(x,u). \end{align*}

This gives the desired relation.

Lemma 4.3. We have

(4.3)\begin{align} \mathcal{L}(x,u)=\mathcal{N}(x,u)\left(\mathcal{S}(x,u)-\frac{x}{1-x}\right). \end{align}

Proof. Let $w=w_1\cdots w_n\in \mathbf{LS}_n(021)$. Here $n\ge 2$ by the definition of LS. We first write $\ell=\mathsf{lar}(w)$ and assume that $j=\mathsf{R}_{\mathsf{lar}}(w)$. Since $\mathsf{R}_{\mathsf{lar}}(w) \lt \mathsf{R}_{\mathsf{sma}}(w)$, we have j < n. Also, for any k with $j+1\le k\le n$, we have

(4.4)\begin{align} w_k \lt w_j=\ell. \end{align}

Now, we split w into two subsequences: $w^{\prime}=w_1\cdots w_j$ and $w^{\prime\prime}=w_{j+1}\cdots w_n$. Then both wʹ and wʹʹ are non-empty and avoid the pattern 021. We also note that the last entry in wʹ is also the largest, and thus $w^{\prime}\in\mathbf{SL}(021)$.

Let $s^{\prime}=\mathsf{sma}(w^{\prime})$ and assume that $w_i=s^{\prime}$ for some i with $1\le i\le j$. Then for any k with $j+1\le k\le n$, we have

(4.5)\begin{align} w_k\le s^{\prime}. \end{align}

Otherwise, if $w_k \gt s^{\prime}$, then i < j and the subsequence $w_iw_jw_k$ satisfies $\ell=w_j \gt w_k \gt w_i=s^{\prime}$ and is therefore order isomorphic to 021, which is prohibited.

By Equations (4.4) and (4.5), we know that $\mathsf{lar}(w^{\prime}) \gt \mathsf{lar}(w^{\prime\prime})$ and $\mathsf{sma}(w^{\prime})\ge \mathsf{lar}(w^{\prime\prime})$. For any sequence in $\mathbf{SL}(021)$ with $\mathsf{lar}\ge 1$ (i.e., aside from those sequences consisted of purely 0’s), we add $\mathsf{lar}(w^{\prime\prime})$ to each entry of this sequence. Then the above wʹ is uniquely generated. This process also preserves the ascent statistic. If we write $\mathsf{lar}(w^{\prime\prime})=\ell^{\prime\prime}$, then these wʹ are generated by

\begin{align*} \sum_{\ell^{\prime}\ge 1}S_{[-,\ell^{\prime}]}(x) u^{\ell^{\prime}+\ell^{\prime\prime}}&=u^{\ell^{\prime\prime}}\sum_{\ell^{\prime}\ge 1}S_{[-,\ell^{\prime}]}(x) u^{\ell^{\prime}}\\ &=u^{\ell^{\prime\prime}}\left(\mathcal{S}(x,u)-\sum_{n\ge 1}x^nu^0t^0\right)\\ &=u^{\ell^{\prime\prime}}\left(\mathcal{S}(x,u)-\frac{x}{1-x}\right). \end{align*}

Therefore, noting that $\mathsf{asc}(w)=\mathsf{asc}(w^{\prime})+\mathsf{asc}(w^{\prime\prime})$, we have

\begin{align*} \mathcal{L}(x,u)&=\sum_{\ell^{\prime\prime}\ge 0}N_{[-,\ell^{\prime\prime}]}(x)u^{\ell^{\prime\prime}}\left(\mathcal{S}(x,u)-\frac{x}{1-x}\right)\\ &=\mathcal{N}(x,u)\left(\mathcal{S}(x,u)-\frac{x}{1-x}\right), \end{align*}

which is our required result.

Theorem 4.4. We have

(4.6)\begin{align} \mathcal{N}(x,u)=\frac{1-u-2x+ux(1-t)+x^2(1+t)}{2x(1-x)t}-\frac{\sqrt{\Delta}}{2x(1-x)t}, \end{align}

where

(4.7)\begin{align} \Delta=\big(1-u-2x+ux(1-t)+x^2(1+t)\big)^2-4(1-x)^2 x^2 t. \end{align}

Proof. Joining Equation (4.1) with Equation (4.2) gives

\begin{equation*} \left\{ \begin{aligned} \mathcal{S}&=\dfrac{xt}{(1-u)(1-x+xt)} \mathcal{N}+\dfrac{x}{(1-u)(1-x+xt)},\\[12pt] \mathcal{L}&=\dfrac{1-u-x+ux-uxt}{(1-u)(1-x+xt)}\mathcal{N}-\dfrac{x}{(1-u)(1-x+xt)}. \end{aligned} \right. \end{equation*}

Substituting the above into Equation (4.3) yields the following quadratic equation of $\mathcal{N}$:

(4.8)\begin{align} tx(1-x)\mathcal{N}^2-\big((t+1)x^2-(ut-u+2)x-u+1\big)\mathcal{N}+x(1-x)=0. \end{align}

Recalling that $\mathcal{N}$ is a formal power series in x, u and t, with initial condition $\mathcal{N}(x,0,t)=x/(1-x)$, we only have one admissible solution of Equation (4.8), as given in Equation (4.6).

5. Hong and Li’s conjecture with ascents

We still start with $\mathbf{I}_{n,p}$, the set of $(p,p+2,\ldots,p+n)$-inversion sequences. Let us split $\mathbf{I}_{n,p}$ into two disjoint types:

\begin{align*} \mathbf{SL}_{n,p}&:=\{e\in\mathbf{I}_{n,p}:\mathsf{R}_{\mathsf{lar}}(e)\ge \mathsf{R}_{\mathsf{sma}}(e)\},\\ \mathbf{LS}_{n,p}&:=\{e\in\mathbf{I}_{n,p}:\mathsf{R}_{\mathsf{lar}}(e) \lt \mathsf{R}_{\mathsf{sma}}(e)\}. \end{align*}

Define quadvariate generating functions

\begin{align*} \mathcal{G}(x,s,u)=\mathcal{G}(x,s,u,t)&:=\sum_{p\ge 1}\sum_{n\ge 1}x^ns^p \sum_{e\in\mathbf{I}_{n,p}(021)}u^{\mathsf{lar}(e)}t^{\mathsf{asc}(e)},\\ \mathcal{G}^*(x,s,u)=\mathcal{G}^*(x,s,u,t)&:=\sum_{p\ge 1}\sum_{n\ge 1}x^ns^p \sum_{e\in\mathbf{SL}_{n,p}(021)}u^{\mathsf{lar}(e)}t^{\mathsf{asc}(e)},\\ \mathcal{G}^{**}(x,s,u)=\mathcal{G}^{**}(x,s,u,t)&:=\sum_{p\ge 1}\sum_{n\ge 1}x^ns^p \sum_{e\in\mathbf{LS}_{n,p}(021)}u^{\mathsf{lar}(e)}t^{\mathsf{asc}(e)}. \end{align*}

Note that

(5.1)\begin{align} \mathcal{G}(x,s,u)=\mathcal{G}^*(x,s,u)+\mathcal{G}^{**}(x,s,u). \end{align}

We also write the coefficients as

\begin{align*} g^*_{[n,p,\ell]}=g^*_{[n,p,\ell]}(t)&:=[x^n s^p u^\ell]\mathcal{G}^*(x,s,u),\\ g^{**}_{[n,p,\ell]}=g^{**}_{[n,p,\ell]}(t)&:=[x^n s^p u^\ell]\mathcal{G}^{**}(x,s,u),\\ g^*_{[-,p,\ell]}(x)=g^*_{[-,p,\ell]}(x,t)&:=[s^p u^\ell]\mathcal{G}^*(x,s,u),\\ g^{**}_{[-,p,\ell]}(x)=g^{**}_{[-,p,\ell]}(x,t)&:=[s^p u^\ell]\mathcal{G}^{**}(x,s,u). \end{align*}

Lemma 5.1. We have

(5.2)\begin{align} \mathcal{G}^*(x,s,u) &= \frac{xs}{(1-s)(1-us)(1-x+xt)}\notag\\ &\quad+\frac{xt}{(1-u)(1-x+xt)}\left(\mathcal{G}(x,s,u)-u\mathcal{G}(ux,us,1)\right). \end{align}

Proof. We proceed in an analogous way to the proof of Lemma 4.2. For $n\ge 1$, each sequence e in $\mathbf{SL}_{n+1,p}(021)$ is uniquely generated by appending to a sequence eʹ in $\mathbf{I}_{n,p}(021)$ by a number $\ell$ with $\ell^{\prime}=:\mathsf{lar}(e^{\prime})\le \ell\le n+p$. If $e^{\prime}\in \mathbf{LS}_{n,p}(021)$, then $\mathsf{asc}(e)=\mathsf{asc}(e^{\prime})+1$. If $e^{\prime}\in \mathbf{SL}_{n,p}(021)$, we have two subcases: if $\ell \gt \ell^{\prime}$, then $\mathsf{asc}(e)=\mathsf{asc}(e^{\prime})+1$; if $\ell=\ell^{\prime}$, then $\mathsf{asc}(e)=\mathsf{asc}(e^{\prime})$.

Noting that sequences in $\mathbf{SL}_{1,p}(021)$ are generated by

\begin{align*} x\sum_{\ell=0}^{p-1}u^\ell=\frac{x(1-u^p)}{1-u}, \end{align*}

we have

\begin{align*} \mathcal{G}^*(x,s,u)&=\sum_{p\ge 1}s^p\frac{x(1-u^p)}{1-u}+\sum_{p\ge 1}s^p\sum_{n\ge 1}x^n\sum_{\ell^{\prime}\ge 0}g^{**}_{[n,p,\ell^{\prime}]}\sum_{\ell=\ell^{\prime}}^{n+p}xu^{\ell}t\\ &\quad+\sum_{p\ge 1}s^p\sum_{n\ge 1}x^n\sum_{\ell^{\prime}\ge 0}g^{*}_{[n,p,\ell^{\prime}]}\left(xu^{\ell^{\prime}}+\sum_{\ell=\ell^{\prime}+1}^{n+p}xu^{\ell}t\right)\\ &=\sum_{p\ge 1}s^p\frac{x(1-u^p)}{1-u}+\sum_{p\ge 1}s^p\sum_{n\ge 1}x^n\sum_{\ell^{\prime}\ge 0}g^{*}_{[n,p,\ell^{\prime}]}u^{\ell^{\prime}}(x-xt)\\ &\quad+\sum_{p\ge 1}s^p\sum_{n\ge 1}x^n\sum_{\ell^{\prime}\ge 0}\left(g^{*}_{[n,p,\ell^{\prime}]}+g^{**}_{[n,p,\ell^{\prime}]}\right)\sum_{\ell=\ell^{\prime}}^{n+p}xu^{\ell}t\\ &=\frac{x}{1-u}\left(\frac{s}{1-s}-\frac{us}{1-us}\right)+(x-xt)\mathcal{G}^*(x,s,u)\\ &\quad +\frac{xt}{1-u}\left(\mathcal{G}(x,s,u)-u\mathcal{G}(ux,us,1)\right). \end{align*}

This gives the desired relation.

Lemma 5.2. We have

(5.3)\begin{align} \mathcal{G}^{**}(x,s,u) = \mathcal{N}(x,us)\left(\mathcal{G}^*(x,s,u)-\frac{x}{1-x}\frac{s}{1-s}\right). \end{align}

Proof. We proceed in an analogous way to the proof of Lemma 4.3. For $n\ge 2$, each sequence in $\mathbf{LS}_{n,p}(021)$ is uniquely generated by appending to a sequence eʹ in $\mathbf{SL}_{n^{\prime},p}(021)$ (with $1\le n^{\prime}\le n-1$) by a sequence eʹʹ in $\mathbf{N}_{n-n^{\prime}}(021)$ such that $\mathsf{lar}(e^{\prime}) \gt \mathsf{lar}(e^{\prime\prime})$ and $\mathsf{sma}(e^{\prime})\ge \mathsf{lar}(e^{\prime\prime})$. Such eʹ can be obtained by adding $\mathsf{lar}(e^{\prime\prime})$ to each entry of a sequence in $\mathbf{SL}_{n^{\prime},p-\mathsf{lar}(e^{\prime\prime})}(021)$ with $\mathsf{lar}\ge 1$. If we write $\mathsf{lar}(e^{\prime\prime})=\ell^{\prime\prime}$, then these eʹ are generated by

\begin{align*} \sum_{p\ge \ell^{\prime\prime}+1}s^p\sum_{\ell^{\prime}\ge 1}g^*_{[-,p-\ell^{\prime\prime},\ell^{\prime}]}(x)u^{\ell^{\prime}+\ell^{\prime\prime}}&=u^{\ell^{\prime\prime}}s^{\ell^{\prime\prime}}\sum_{p^{\prime}\ge 1}\sum_{\ell^{\prime}\ge 1}g^*_{[-,p^{\prime},\ell^{\prime}]}(x)u^{\ell^{\prime}}s^{p^{\prime}}\\ &=u^{\ell^{\prime\prime}}s^{\ell^{\prime\prime}}\left(\mathcal{G}^*(x,s,u)-\frac{x}{1-x}\frac{s}{1-s}\right). \end{align*}

Therefore, noting that $\mathsf{asc}(e)=\mathsf{asc}(e^{\prime})+\mathsf{asc}(e^{\prime\prime})$, we have

\begin{align*} \mathcal{G}^{**}(x,s,u)&=\sum_{\ell^{\prime\prime}\ge 0}N_{[-,\ell^{\prime\prime}]}(x)u^{\ell^{\prime\prime}}s^{\ell^{\prime\prime}}\left(\mathcal{G}^*(x,s,u)-\frac{x}{1-x}\frac{s}{1-s}\right)\\ &=\mathcal{N}(x,us)\left(\mathcal{G}^*(x,s,u)-\frac{x}{1-x}\frac{s}{1-s}\right), \end{align*}

which is our required result.

Theorem 5.3. We have

(5.4)\begin{align} \mathcal{G}(x,xt,1)=\frac{t\big((1+x-xt) r-x\big)}{(1-r)(1-xt)}, \end{align}

where

(5.5)\begin{align} r&=x + t x^2 + (t ^2+2 t) x^3 + (t ^3+8 t ^2+3 t) x^4\notag\\ &\quad + (t ^4+22 t ^3+27 t ^2+4 t) x^5+\cdots \end{align}

is the unique power series solution (with r → 0 as x → 0) to

(5.6)\begin{align} r^3-(2+x+t-xt^2)r^2+(1+2x)r-x=0. \end{align}

Proof. For convenience, we define

\begin{align*} \mathcal{F}(x,u)&:=\mathcal{G}(x,xt,u),\\ \mathcal{F}^*(x,u)&:=\mathcal{G}^*(x,xt,u),\\ \mathcal{F}^{**}(x,u)&:=\mathcal{G}^{**}(x,xt,u). \end{align*}

Combining Equations (5.1) and (5.2) with $s\mapsto xt$ gives

\begin{align*} \left\{\begin{aligned} \mathcal{F}^*(x,u)&=\dfrac{x^2t}{(1-xt)(1-uxt)(1-x+xt)}+\dfrac{xt}{(1-u)(1-x+xt)}\mathcal{F}(x,u)\\ &\quad-\dfrac{uxt}{(1-u)(1-x+xt)}\mathcal{F}(ux,1),\\[12pt] \mathcal{F}^{**}(x,u)&=-\dfrac{x^2t}{(1-xt)(1-uxt)(1-x+xt)}+\dfrac{1-u-x+ux-uxt}{(1-u)(1-x+xt)}\mathcal{F}(x,u)\\ &\quad+\dfrac{uxt}{(1-u)(1-x+xt)}\mathcal{F}(ux,1).\\ \end{aligned} \right. \end{align*}

Now, it follows by substituting the above into Equation (5.3) with $s\mapsto xt$ that

\begin{align*} &\left(\dfrac{1-u-x+ux-uxt}{(1-u)(1-x+xt)}-\dfrac{xt}{(1-u)(1-x+xt)}\mathcal{N}(x,uxt)\right)\mathcal{F}(x,u)\\ &\qquad=\dfrac{x^2t}{(1-xt)(1-uxt)(1-x+xt)}\left(1-\frac{xt(1-u+ux-uxt)}{1-x}\mathcal{N}(x,uxt)\right)\\ &\qquad\quad-\left(\dfrac{uxt}{(1-u)(1-x+xt)}+\dfrac{uxt}{(1-u)(1-x+xt)}\mathcal{N}(x,uxt)\right)\mathcal{F}(ux,1). \end{align*}

We then make the change of variables $u\mapsto w/x$. Therefore,

(5.7)\begin{align} K\cdot \mathcal{F}(x,x^{-1}w)=C_0-C_1\cdot \mathcal{F}(w,1), \end{align}

where

\begin{align*} K&=\dfrac{1-x^{-1}w-x+w-wt}{(1-x^{-1}w)(1-x+xt)}-\dfrac{xt}{(1-x^{-1}w)(1-x+xt)}\mathcal{N}(x,wt),\\ C_0&=\dfrac{x^2t}{(1-xt)(1-wt)(1-x+xt)}\left(1-\frac{xt(1-x^{-1}w+w-wt)}{1-x}\mathcal{N}(x,wt)\right),\\ C_1&=\dfrac{wt}{(1-x^{-1}w)(1-x+xt)}+\dfrac{wt}{(1-x^{-1}w)(1-x+xt)}\mathcal{N}(x,wt). \end{align*}

Also, we recall from Equation (4.6),

(5.8)\begin{align} \mathcal{N}(x,wt)=\frac{1-wt-2x+wxt(1-t)+x^2(1+t)}{2x(1-x)t}-\frac{\sqrt{\Delta^*}}{2x(1-x)t}, \end{align}

where

\begin{align*} \Delta^*=\big(1-wt-2x+wxt(1-t)+x^2(1+t)\big)^2-4(1-x)^2 x^2 t. \end{align*}

Applying the kernel method to Equation (5.7) by setting the kernel polynomial K to be zero, we have

\begin{align*} \dfrac{1-x^{-1}w-x+w-wt}{(1-x^{-1}w)(1-x+xt)}-\dfrac{xt}{(1-x^{-1}w)(1-x+xt)}\mathcal{N}(x,wt)=0, \end{align*}

or

(5.9)\begin{align} \mathcal{N}(x,wt) = \frac{1-x^{-1}w-x+w-wt}{xt}, \end{align}

or by recalling Equation (5.8),

(5.10)\begin{align} x^3-(2+w+t-wt^2)x^2+(1+2w)x-w=0. \end{align}

Our admissible solution $x=x(w)$ satisfies x → 0 as w → 0 and has the power series expansion

\begin{align*} x&=w + t w^2 + (t ^2+2 t) w^3 + (t ^3+8 t ^2+3 t) w^4\\ &\quad + (t ^4+22 t ^3+27 t ^2+4 t) w^5+\cdots. \end{align*}

On the other hand,

\begin{align*} \mathcal{F}(w,1)&=\frac{C_0}{C_1},\\ {\tiny (by\ Equation~5.9)} &=-\frac{t \big(x^3+(wt-w-2)x^2+w x\big)}{(1-x)(1-xt)(1-wt)},\\ {\tiny (by\ Equation~5.10)} &= \frac{t\big((1+w-wt) x-w\big)}{(1-x)(1-wt)}. \end{align*}

Finally, the desired result follows by renaming the variables $(w,x)\mapsto (x,r)$.

Let

(5.11)\begin{align} \mathcal{I}(x,t):=\sum_{n\ge 1}x^n\sum_{e\in\mathbf{I}_n(0021)}t^{\mathsf{asc}(e)}. \end{align}

We are in a position to establish the following ‘explicit’ expression for $\mathcal{I}(x,t)$.

Theorem 5.4. We have

(5.12)\begin{align} \mathcal{I}(x,t) = \frac{r}{1-r}, \end{align}

where r is as in Equation (5.5).

Proof. Recall that any inversion sequence e in $\mathbf{I}_n(0021)$ is either in correspondence with a sequence $\hat{e}$ in $\mathbf{I}_{n-p,p}(021)$ for some p by Lemma 3.1, in which case $\mathsf{asc}(e)=(p-1)+\mathsf{asc}(\hat{e})$, or a sequence with only tight entries, which is generated by

\begin{equation*}x+t x^2+t^2 x^3+\cdots = \frac{x}{1-xt}.\end{equation*}

Hence,

\begin{align*} \mathcal{I}(x,t)&=\frac{x}{1-xt}+\sum_{p\ge 1}\sum_{n\ge 1}x^{n+p}t^{p-1} \sum_{e\in\mathbf{I}_{n,p}(021)}t^{\mathsf{asc}(e)}\\ &=\frac{x}{1-xt}+t^{-1}\mathcal{G}(x,xt,1). \end{align*}

The desired result follows by recalling Equation (5.4).

Now, we conclude our proof of Equation (1.7).

Proof of Equation (1.7)

By Equation (5.12), we have

\begin{align*} r=\frac{\mathcal{I}(x,t)}{\mathcal{I}(x,t)+1}. \end{align*}

Substituting the above into Equation (5.6) gives

\begin{align*} 0&=\left(\frac{\mathcal{I}(x,t)}{\mathcal{I}(x,t)+1}\right)^3-(2+x+t-xt^2)\left(\frac{\mathcal{I}(x,t)}{\mathcal{I}(x,t)+1}\right)^2\\ &\quad+(1+2x)\left(\frac{\mathcal{I}(x,t)}{\mathcal{I}(x,t)+1}\right)-x, \end{align*}

which finally results in

\begin{align*} \mathcal{I}(x,t)=\big(1+\mathcal{I}(x,t)\big)\big(x+t \mathcal{I}(x,t)^2 - xt^2 \mathcal{I}(x,t)^2\big). \end{align*}

This functional equation is identical to Equation (1.5).

6. Conclusion

Burstein’s second and third conjectures remain open. It seems that the $\mathsf{alt}$ statistic may still be a key as one can easily modify the proof of Lemma 2.1 to obtain the following analogous result.

Lemma 6.1. For each permutation π in

\begin{equation*}\mathfrak{S}_n(2134, 42153, 24153)\quad\text{or}\quad\mathfrak{S}_n(2143, 42135, 24135),\end{equation*}

we have $\mathsf{alt}(\pi)\le 4$.

However, in these two cases, there is an obstacle to deducing parallel relations to those in Equation (2.3), especially for k = 2 and 3.

Finally, for π a permutation of length n, we define

• ▹ the number of inverse ascents: $\mathsf{iasc}(\pi):=\mathsf{asc}(\pi^{-1})$, where π ⁻¹ is the inverse permutation of π;

• ▹ the number of right-to-left maxima: $\mathsf{rma}(\pi):=|\{i\in[n]: \pi_j \lt \pi_i,\, \forall j \gt i\}|$;

• ▹ the set of positions of left-to-right minima: $\mathsf{LMI}(\pi):=\{i\in[n]: \pi_j \gt \pi_i,\, \forall j \lt i\}$.

Our numerical evidence supports the following equidistribution conjectures.

Conjecture 6.1.

The triple of statistics $(\mathsf{LMI},\mathsf{rma},\mathsf{ides})$ has the same distribution over $\mathfrak{S}_n(2134,42153,24153)$ and $\mathfrak{S}_n(3124,42153,24153)$.

Conjecture 6.2.

The pair of Eulerian statistics $(\mathsf{des},\mathsf{ides})$ over $\mathfrak{S}_n(2134,42153, 24153)$ has the same distribution as $(\mathsf{asc},\mathsf{iasc})$ over $\mathfrak{S}_n(2143,42135,24135)$.