# Further enumeration results concerning a recent equivalence of restricted inversion sequences

Toufik Mansour, Mark Shattuck

► To cite this version:

Toufik Mansour, Mark Shattuck. Further enumeration results concerning a recent equivalence of restricted inversion sequences. Discrete Mathematics and Theoretical Computer Science, 2022, vol. 24, no. 1, 10.46298/dmtcs.8330. hal-03295362v3

HAL Id: hal-03295362

https://hal.science/hal-03295362v3

Submitted on 31 Jan 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Further enumeration results concerning a recent equivalence of restricted inversion sequences

Toufik Mansour<fnref n="1" />*

Mark Shattuck<fnref n="2" />†

received 3rd Aug. 2021, revised 19th Jan. 2022, accepted 19th Jan. 2022.

Let asc and desc denote respectively the statistics recording the number of ascents or descents in a sequence having non-negative integer entries. In a recent paper by Andrews and Chern, it was shown that the distribution of asc on the inversion sequence avoidance class $I_n(\ge, \ne, >)$ is the same as that of $n-1$ asc on the class $I_n(> , \ne, \ge)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\ge, \ne, >)$ of asc and desc along with two other parameters, and do the same for $n-1$ desc and asc on $I_n(> , \ne, \ge)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result that the common cardinality of $I_n(\ge, \ne, >)$ and $I_n(> , \ne, \ge)$ is the same as that of $S_n(4231, 42513)$. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents.

**Keywords:** pattern avoidance, combinatorial statistic, kernel method, inversion sequence

## 1 Introduction

Let $S_n$ denote the set of permutations of $[n] = \{1, \dots, n\}$, written in one-line notation. An inversion within $\pi = \pi_1 \cdots \pi_n \in S_n$ is an ordered pair $(a, b)$ where $a, b \in [n]$ with $a < b$ and $\pi_a > \pi_b$. The inversion sequence of $\pi$ is defined by $x = x_1 \cdots x_n$, where $x_i$ for each $i \in [n]$ records the number of inversions for which $\pi_a = i$, that is, inversions caused by $i$ when its position relative to the elements in $[i-1]$ is decided. Note that such sequences $x$ are characterized by the property $0 \le x \le i-1$ for all $i$. For example, if $\pi = 451632 \in S_6$, then $x = 001332$. Let $I_n$ denote the set of all inversion sequences of length $n$. The systematic study of patterns in members of $I_n$ is a topic that has only recently been initiated in [4, 13], starting with the avoidance of a single pattern of length three.

<footnote n="1">¹ Department of Mathematics, University of Haifa, 3498838 Haifa, Israel</footnote>

<footnote n="2">² Department of Mathematics, University of Tennessee, 37996 Knoxville, TN</footnote>

<footnote>*Corresponding author. Email: tmansour@univ.haifa.ac.il</footnote>

<footnote>†Email: mshattuc@utk.edu</footnote>
Martinez and Savage [15] extended the notion of pattern avoidance by considering a fixed triple of relations $(\rho_1, \rho_2, \rho_3) \in \{<, >, \le, \ge, =, \ne, -\}$, where $-$ denotes the universal relation (i.e., $x - y$ for all $x, y \in [n]$). They studied the set $I_n(\rho_1, \rho_2, \rho_3)$ consisting of those $e = e_1 \cdots e_n \in I_n$ for which there exist no indices $1 \le i < j < k \le n$ such that $e_i\rho_1e_j, e_j\rho_2e_k$ and $e_i\rho_3e_k$. Note that sequences in $I_n(\rho_1, \rho_2, \rho_3)$ are synonymous with members of $I_n(\{\tau_1, \dots, \tau_r\})$ for some patterns $\tau_1, \dots, \tau_r$ of length three, where $I_n(\{\tau_1, \dots, \tau_r\})$ denotes the subset of $I_n$ whose members avoid each $\tau_i$ for $i \in [r]$ in the classical sense. For example, we have $I_n(>-, <, \ge) = I_n(\{101, 201\})$ and $I_n(<, -, <) = I_n(\{011, 012, 021\})$.

Since their introduction in [15], the problem of enumerating members of the class $I_n(\rho_1, \rho_2, \rho_3)$ is one that has been investigated extensively, with many connections having been made to sequences in the OEIS [16]. We refer the reader to [11] and references contained therein. Moreover, several equivalences among the 343 possible sets $I_n(\rho_1, \rho_2, \rho_3)$ were conjectured in [15] and later proven in [2, 6, 8, 10, 11, 18]. Paralleling the study of pattern avoidance on permutations represented in the one-line notation (see, e.g., [9]), analogous problems, such as avoidance of vincular [12] or multiple [17] patterns, have been considered on inversion sequences.

A further direction in the study of inversion sequences avoiding a pattern of relation triples is obtained by considering the distribution of a statistic on members of an avoidance class; see, e.g., [2, 8, 11, 14, 15]. In this paper, we consider the distribution of the number of ascents, descents and levels over certain avoidance classes of $I_n$ involving a pattern of relation triples. Recall that given a sequence $w = w_1 \cdots w_n$, an ascent is an index $i \in [n-1]$ such that $w_i < w_{i+1}$, a descent is one with $w_i > w_{i+1}$ and a level one with $w_i = w_{i+1}$. Let asc($w$), desc($w$) and lev($w$) denote respectively the number of ascents, descents and levels in the sequence $w$. Further, recall that within a descent $w_j > w_{j+1}$ for some $j \in [n-1]$, the entries $w_j$ and $w_{j+1}$ are referred to as a *descent top* and a *descent bottom*, respectively. Note that $\text{desc}(w) + \text{lev}(w) = n - 1 - \text{asc}(w)$ for all $w$ of length $n$.

Lin [11] conjectured the following equivalence involving the ascents statistic on the avoidance classes $I_n(\ge, \ne, >)$ and $I_n(>-, \ne, \ge)$:

$$ \sum_{e \in I_n(\ge, \ne, >)} q^{\text{asc}(e)} = \sum_{e \in I_n(>-, \ne, \ge)} q^{n-1-\text{asc}(e)}, \quad n \ge 1. \quad (1) $$

This equivalence was shown originally by Andrews and Chern [1] using a functional equation approach. For a combinatorial proof of (1), see [3]. Here, we consider some further combinatorial aspects of (1). In particular, we consider a refinement of both sides of (1) by introducing a variable $p$ which marks the number of descents in members of each class. We compute an explicit formula for the generating function of the joint distribution of $\text{desc}$ and $\text{asc}$ on $I_n(\ge, \ne, >)$, and also of $\text{desc}$ and $n-1-\text{asc}$ on $I_n(>-, \ne, \ge)$, using the kernel method [7].

Comparing the $p=1$ cases of our main results below (see Theorems 4 and 13), in addition to providing a new proof of (1), yields a formula for the generating function of both sides of (1). Such a formula was not given explicitly in [1]. Further, taking $p=q=1$ yields a new proof of the fact first shown by Lin [11] that

$$ |I_n(\ge, \ne, >)| = |I_n(>-, \ne, \ge)| = |S_n(4231, 42513)|, \quad n \ge 1, \quad (2) $$

which confirmed a conjecture made originally in [15]. Note that the sequence of cardinalities

$$ |S_n(4231, 42513)| $$
for $n \ge 1$ corresponding to the $q = 1$ case of (1) occurs as entry A098746 in [16]. To show (2), note that Lin did not enumerate either $I_n(\ge, \ne, >)$ or $I_n(> , \ne, \ge)$ directly, but rather defined a bijection between the two and enumerated instead the set $I_n(> , -, >)$, which had been shown in [15] to be equinumerous with $I_n(\ge, \ne, >)$ via a bijection. Thus, the method employed here allows for a unified proof of (1) and (2), which were shown previously by seemingly unrelated approaches, and leads to a refinement of these relations in terms of the descents statistic (and other parameters).

The organization of this paper is as follows. In the next section, we consider the joint distribution of desc and asc on $I_n(\ge, \ne, >)$ and find its generating function. To do so, a recurrence is found for a refinement of this distribution involving two additional parameters which is then converted to a system of functional equations involving the corresponding generating functions. Further, an algorithm is devised for finding the generating function for the distribution of asc on members of $I_n(\ge, \ne, >)$ having a prescribed number of descents. In the third section, we consider the distribution of desc and $n-1-asc$ on $I_n(> , \ne, \ge)$ and compute the generating function of this distribution. Comparable formulas are found and an algorithm is given for determining explicitly the coefficient of $p^m$ for a fixed $m$ in this generating function.

We remark further that in order to obtain recurrences for the joint distribution of (desc, asc) on the class $I_n(\ge, \ne, >)$ and of $(desc, n-1-asc)$ on $I_n(> , \ne, \ge)$, we must refine the cardinalities of these sets according to a pair of new parameters on each. In particular, to study members $e \in I_n(\ge, \ne, >)$, it is useful to consider a parameter which we call the *height* of $e$ and is defined as the maximum letter that starts either a descent or a level of $e$. On the other hand, for $e \in I_n(> , \ne, \ge)$, it is convenient to consider the statistic which tracks the smallest letter serving as a descent top for the largest descent bottom in $e$. These parameters (and variants thereof) may very well prove interesting to study in their own right on other types of discrete structures that are often represented as sequences, such as finite set partitions or functions between two finite sets of prescribed size.

## 2 The descents and ascents statistics on $I_n(\ge, \ne, >)$

We first define two new concepts related to the relative sizes of the non-ascent entries within an inversion sequence. Let the *height* of $e = e_1e_2 \cdots e_n \in I_n$ be given by

$$ \text{hgt}(e) = \max\{e_i : 1 \le i \le n-1 \text{ and } e_i \ge e_{i+1}\}. $$

If $a = \text{hgt}(e)$ with $j \in [n-1]$ minimal such that $e_j = a$, then let the *depth* of $e$ be defined as $\text{dep}(e) = e_{j+1}$. Here, and in the subsequent section, we find it more convenient notationally to represent members of $I_n$ using positive instead of non-negative integers, which is achieved by adding one to each entry of the standard representation.

Let $A_n = I_n(\ge, \ne, >)$ and suppose $e \in A_n$ has height and depth values of $a$ and $b$, respectively. If $a > b$, then there exists a single descent $ab$ and at most two runs of the letter $a$, the first of which has length one. On the other hand, if $a = b$ within $e$, there can exist only a single run of $a$. Within a (maximal) subsequence of the form $ab \cdots b$, any letter beyond the second will be referred to as a *redundant bottom*, regardless of whether or not $a$ and $b$ are distinct. For example, if $e = 123116333669 \in A_{12}$, then $\text{hgt}(e) = 6$ and $\text{dep}(e) = 3$, with the last two 3's redundant bottoms. If $e = 1132267779 \in A_{10}$, then $\text{hgt}(e) = \text{dep}(e) = 7$, with only the third 7 a redundant bottom.

We now decompose $A_n$ into disjoint subsets as follows. Given $1 \le i \le n-1$ and $1 \le j \le n$, let $B_n(i, j)$ denote the subset of $A_n$ whose members have height $i$ and last letter $j$, where the last letter is not a redundant bottom. Let $C_n(i, j)$ be defined the same as $B_n(i, j)$, but where the last letter is a redundant bottom.
bottom. Note that $C_n(i, j)$ can be nonempty only when $n \ge 3$ and $1 \le j \le i \le n-2$. Define the distribution polynomial $b_n(i, j) = b_n(i, j; p, q)$ by

$$b_n(i, j) = \sum_{\pi \in \mathcal{B}_n(i, j)} p^{\text{desc}(\pi)} q^{\text{asc}(\pi)},$$

and likewise for $c_n(i, j) = c_n(i, j; p, q)$. For example, we have

$$\mathcal{B}_5(3, 4) = \{11314, 11324, 11334, 12314, 12324, 12334\}$$

and $\mathcal{C}_5(3, 2) = \{11322, 12322\}$, which implies $b_5(3, 4) = q^2 + q^3 + 2pq^2 + 2pq^3$ and $c_5(3, 2) = pq + pq^2$. Assume $b_n(i, j)$ or $c_n(i, j)$ to be zero if the subset of $\mathcal{A}_n$ corresponding to $i$ and $j$ is empty.

Let

$$b_n = \sum_{i=1}^{n-1} \sum_{j=1}^{n} b_n(i, j), \quad n \ge 2,$$

and

$$c_n = \sum_{i=1}^{n-2} \sum_{j=1}^{i} c_n(i, j), \quad n \ge 3,$$

and put $b_1 = 0$ and $c_1 = c_2 = 0$. Note that $b_n$ and $c_n$ are polynomials in $p$ and $q$. Then we seek a formula for $a_n = a_n(p, q)$ defined as

$$a_n = b_n + c_n + q^{n-1}, \quad n \ge 1.$$

Note that $a_n$ gives the joint distribution of desc and asc on $\mathcal{A}_n$, where the $q^{n-1}$ term accounts for the sequence $12\cdots n$ which belongs to no subset $\mathcal{B}_n(i, j)$ or $\mathcal{C}_n(i, j)$.

The arrays $b_n(i, j)$ and $c_n(i, j)$ satisfy the following system of recurrences.

**Lemma 1.** We have

$$b_n(i, j) = \delta_{i,n-2} \cdot q^{n-2} + q c_{n-1}(i, i) + q \sum_{\ell=i+1}^{j-1} b_{n-1}(i, \ell) + q \sum_{k=1}^{i-1} b_{n-2}(k, i) + q \sum_{\ell=1}^{i-1} c_n(i, \ell) \\ + q^2 \sum_{\ell=1}^{i-1} \sum_{s=1}^{n-i-2} c_{n-s}(i, \ell), \quad 1 \le i \le n-2 \text{ and } i < j \le n, \quad (3)$$

with $b_n(n-1, n) = 0$ for $n \ge 2$,

$$b_n(i, i) = \delta_{i,n-1} \cdot q^{n-2} + \sum_{k=1}^{i-1} b_{n-1}(k, i) + q \sum_{\ell=1}^{i-1} \sum_{s=1}^{n-i-1} c_{n-s+1}(i, \ell), \quad 1 \le i \le n-1, \quad (4)$$

$$b_n(i, j) = \delta_{i,n-1} \cdot pq^{n-2} + p \sum_{k=1}^{j} b_{n-1}(k, i) + p \sum_{k=j+1}^{i-1} \sum_{s=0}^{i-k-1} \binom{i-k-1}{s} q^{s+1} c_{n-s-1}(k, j), \quad (5)$$
for $1 \le j < i \le n - 1$,

$$c_n(i, j) = b_{n-1}(i, j) + c_{n-1}(i, j), \quad 1 \le j < i \le n-2, \qquad (6)$$

$$c_n(i, i) = \delta_{i,n-2} \cdot q^{n-3} + c_{n-1}(i, i) + \sum_{k=1}^{i-1} b_{n-2}(k, i), \quad 1 \le i \le n-2. \qquad (7)$$

Furthermore, we have the following alternative recurrences to (3) and (5) when $i < j$ and $i > j$, respectively:

$$b_n(i, j) = \sum_{\ell=1}^{i} \sum_{t=0}^{j-i-1} \binom{j-i-1}{t} q^{t+1} c_{n-t}(i, \ell) + \sum_{\ell=1}^{i-1} \sum_{t=0}^{j-i-1} \sum_{s=1}^{n-i-t-2} \binom{j-i-1}{t} q^{t+2} c_{n-s-t}(i, \ell) \quad (8)$$

and

$$\frac{1}{pq}(b_n(i, j) - q \sum_{k=j+1}^{i-1} b_{n-1}(k, j)) = \delta_{j,n-2} \cdot q^{n-3} + \sum_{k=j+1}^{i-1} c_{n-1}(k, j) + \sum_{k=1}^{j} \sum_{\ell=1}^{k} c_{n-1}(k, \ell) \\ + \sum_{\ell=2}^{j} \sum_{k=1}^{\ell-1} b_{n-2}(k, \ell) + q \sum_{k=2}^{j} \sum_{\ell=1}^{k-1} \sum_{r=1}^{n-k-2} c_{n-r-1}(k, \ell). \quad (9)$$

**Proof:** To show (3), let $\pi \in \mathcal{B}_n(i, j)$ where $j > i$. Note that $1 \le i \le n - 2$ is required since the height cannot be achieved for the first time by the penultimate letter if $j > i$. Suppose that $\pi$ has depth $\ell$ for some $\ell \in [i]$. Then it may be verified that $\pi$ can be decomposed uniquely as

$$\pi = \pi' i \ell^r i^s \alpha,$$

where $s \ge 0$, $\alpha$ is a (strictly) increasing sequence in $[i+1, j]$ ending in $j$ and $\pi'$ contains only letters in $[i-1]$, with $r \ge 1$ if $\ell < i$ and $r = 1$ if $\ell = i$. To see this, note that $\pi'$ cannot contain any letters greater than $i$, for otherwise $i$ would fail to be the height of $\pi$. Further, if $\ell < i$, then $\pi'$ cannot contain $i$ either, for then $(\ge, \ne, >)$ would be realized by $ii\ell$. On the other hand, if $\ell = i$, one need only consider the leftmost occurrence of $i$ to obtain the stated decomposition.

If $|\alpha| > 1$, then the weight of all possible such $\pi$ is given by $q \sum_{\ell=i+1}^{j-1} b_{n-1}(i, \ell)$, upon deleting $j$ and considering the penultimate letter which belongs to $[i+1, j-1]$ in this case. So assume $\alpha$ consists of only the terminal $j$, i.e., $\pi = \pi' i \ell^r i^s j$, where $\ell, r$ and $s$ are as before. We consider then the following cases on $s$ and $\ell$: (i) $s = 0, \ell = i$; (ii) $s \ge 1, \ell = i$; (iii) $s = 0, \ell < i$; (iv) $s \ge 1, \ell < i$. One may verify that the respective contributions towards $b_n(i, j)$ in the four cases are given by (i) $\delta_{i,n-2} \cdot q^{n-2} + q \sum_{k=1}^{i-1} b_{n-2}(k, i)$, (ii) $qc_{n-1}(i, i)$, (iii) $q \sum_{i=1}^{\ell-1} (b_{n-1}(i, \ell) + c_{n-1}(i, \ell))$ and (iv) $q^2 \sum_{\ell=1}^{i-1} \sum_{s=1}^{n-i-2} (b_{n-s-1}(i, \ell) + c_{n-s-1}(i, \ell))$. Note that in (iii), deletion of the final $j$ results in an arbitrary member of $\mathcal{B}_{n-1}(i, \ell) \cup \mathcal{C}_{n-1}(i, \ell)$ for some $\ell \in [i-1]$, upon considering whether $r = 1$ or $r > 1$ in the decomposition of $\pi$ above, where the factor of $q$ accounts for the ascent arising due to $j$. In (iv), on the other hand, there are two extra ascents that arise since $j > i > \ell$ with $s \ge 1$ so that deletion of $i^s$ along with the terminal $j$ from $\pi$ results in a sequence enumerated by $b_{n-s-1}(i, \ell) + c_{n-s-1}(i, \ell)$.
Now observe that (6) follows from the definitions, upon removing the final letter which must be equal to its predecessor in this case. Formula (3) then follows from (6) and combining all the previous cases.

To show (4), let $\pi \in \mathcal{B}_n(i, i)$ where $1 \le i \le n-1$. First suppose that $\pi$ ends in $i, i$ with no other $i$'s occurring in $\pi$. If $i < n-1$, then deleting the final letter results in a member of $\mathcal{B}_{n-1}(k, i)$ for some $k \in [i-1]$, whereas if $i = n-1$, then in addition one can have $\pi = 12 \cdots (n-1)(n-1)$, which is accounted for by the extra term $\delta_{i,n-1} \cdot q^{n-2}$. So assume it is not the case that $\pi$ ends in $i, i$ with no other $i$'s occurring. Note that it is not possible for $\pi$ to have a single run of $i$'s which occurs at the end and has length three or more, for that would imply that the terminal $i$ is a redundant bottom with such $\pi$ not being enumerated by $b_n(i, i)$. Then we must have $\pi = \pi' i \ell^r i s^s$, where $\pi'$ has letters only in $[i-1]$, $r, s \ge 1$ and $\ell \in [i-1]$. Note that the first $i$ occurring in the $j$-th position for some $j \ge i$, together with $r \ge 1$, implies $s \le n-i-1$. Then deletion of $i^s$ from $\pi$ results in members of $\mathcal{B}_n(i, i)$ whose weight is given by the second sum in (4), upon applying (6). Combining the previous cases now yields (4).

To show (5), let $\pi \in \mathcal{B}_n(i, j)$ where $2 \le i \le n-1$ and $j \in [i-1]$. Then $j$ not a redundant bottom implies we must have $\pi = \pi'ij$ where $\max(\pi') < i$. If $i = n-1$, then $\pi' = 12 \cdots (n-2)$ is possible, which is accounted for by $\delta_{i,n-1} \cdot pq^{n-2}$, so assume $\pi'$ has height $k$ for some $k \in [n-2]$. Note that $k \ge i$ is impossible, for otherwise $kij$ would correspond to an occurrence of $(\ge, \ne, >)$. If $k \in [j]$, then the terminal $j$ may be deleted yielding $p \sum_{k=1}^j b_{n-1}(k, i)$ possibilities, where the factor of $p$ accounts for the descent between $i$ and $j$. So assume $k \in [j+1, i-1]$. Then $\pi$ must have the form $\pi = \alpha k j^r \beta j$, where $\max(\alpha) < k, r \ge 1$ and $\beta$ is increasing on $[k+1, i]$ with last letter $i$. If $|\beta| = s+1$, then there are $\binom{i-k-1}{s}$ ways in which to choose the members of $\beta$. Deleting $\beta$ from $\pi$ (keeping the terminal $j$) yields a member of $C_{n-s-1}(k, j)$, as the resulting sequence would end in a redundant (descent) bottom in this case. Considering all possible $k$ and $s$ then gives the weight of the remaining members of $\mathcal{B}_n(i, j)$ and implies (5), where the $pq^{s+1}$ factor in the final sum accounts for the ascents caused by the members of $\beta$ and the descent between the last two letters.

To show (7), first note that $\pi \in C_n(i, i)$ must end in a run of $i$'s of length at least three with all other letters outside of this run strictly less than $i$. Upon deleting the final $i$, there are $c_{n-1}(i, i)$ possibilities if $\pi$ ends in four or more $i$'s. Otherwise, $\pi = \pi'ii$, where $\pi' \in \mathcal{B}_{n-2}(k, i)$ for some $k < i$ or $\pi' = 12 \cdots (n-2)$, the latter applying only if $i = n-2$, which implies (7). To show (8), consider the same four cases (i)–(iv) used in the proof of (1) above, but where the single terminal $j$ is replaced with an increasing sequence $\beta$ in $[i+1, j]$ whose last letter is $j$. Then the first sum on the right side of (8) gives the contribution towards the overall weight of those members of $\mathcal{B}_n(i, j)$ in which cases (i)–(iii) apply. This is seen upon deleting all letters in $\beta$ where $|\beta| = t+1$ and adding back an extra copy of the letter $\ell$ to the end, which results in a member of $C_{n-t}(i, \ell)$. To find the weight of members of $\mathcal{B}_n(i, j)$ in case (iv), first delete from $\pi$ both $\beta$ and $i^s$ (which directly precedes $\beta$) and then add back a letter $\ell$ to the end. Note that the resulting sequence belongs to $C_{n-s-t}(i, \ell)$ for some $\ell < i$, with $i \le n-s-t-2$ implying $s \in [n-i-t-2]$. Considering all possible $\ell, t$ and $s$ then gives the second sum on the right side of (8).

To show (9), suppose $\pi \in \mathcal{B}_n(i, j)$ where $i > j$. Then we may write $\pi = \rho ij$, where $\max(\rho) < i$, and consider cases based on the last letter $t$ of $\rho$. If $t > j$, then deleting $i$ from $\pi$ results in a member of $\mathcal{B}_{n-1}(t, j)$ and considering all possible $t$ yields a contribution of $q \sum_{i=1}^{j-1} b_{n-1}(t, j)$ towards the weight in this case. Now suppose $t = j$. If $\rho = 12 \cdots (n-2)$, then $i = n-1, j = n-2$ and $\pi$ has weight $pq^{n-2}$. So assume $\rho \ne 12 \cdots (n-2)$ and let $\mathrm{hgt}(\rho) = k$. If $k < j$, then deleting $i$ and the terminal $j$ implies a contribution of $pq \sum_{k=1}^{j-1} b_{n-2}(k, j)$ towards the weight. If $k = j$, then either $\rho = \rho'j^{r+1}$ or $\rho = \rho'j^l s^j j^r$, where $r, s \ge 1, \ell \in [j-1]$ and $\max(\rho') < j$. Removing $i$ from $\pi$ in the first case and
removing the terminal section $j^r ij$ from $\pi$ and adding back a copy of $\ell$ in the second (so that the resulting sequence is $\rho'j\ell^{s+1}$) yields respective contributions of $pq c_{n-1}(j, j)$ and $pq^2 \sum_{\ell=1}^{j-1} \sum_{r=1}^{n-j-2} c_{n-r-1}(j, \ell)$, upon considering all possible $\ell$ and $r$ in the latter case. Note that $r, s \ge 1$ and $\ell < j$ implies two ascents (and a descent) are lost with the removal of $j^r ij$ from $\pi$. The remaining possibility when $t = j$ is for $j+1 \le k \le i-1$, in which case $\rho = \rho'k j^r$, where $\max(\rho') < k$ and $r \ge 1$. Deleting $i$ and considering all $k$ yields $pq \sum_{k=j+1}^{i-1} c_{n-1}(k, j)$, as the resulting sequence ends in $kj^{r+1}$ where $k > j$.

Now assume $t < j$, and again let $k = \text{hgt}(\rho)$. Note that $k > j$ is not possible in this case, for otherwise $ktj$ is an occurrence of $(\ge, \ne, >)$. If $k = j$, then $\rho = \rho'j\ell^r$, where $\ell \in [j-1]$ and $r \ge 1$, and thus there are $pq \sum_{\ell=1}^{j-1} c_{n-1}(j, \ell)$ possibilities, upon deleting $i$ and the terminal $j$ and putting back an $\ell$. So assume $k < j$. Considering whether $t \le k$ or $k < t < j$ implies $\rho$ must have one of the following four forms: (a) $\rho = \rho'k\ell^s k^r$, (b) $\rho = \rho'k^{r+2}$, (c) $\rho = \rho'k\ell^s k^r \alpha$ or (d) $\rho = \rho'k^{r+2}\alpha$, where $r \ge 0$, $s \ge 1$, $\ell \in [k-1]$, $\max(\rho') < k$ and $\alpha$ is a nonempty (strictly) increasing sequence in $[k+1, j-1]$. Deleting $i$ and $j$ from $\pi$ in (b) or in the $r=0$ case of (a), and adding a copy of the current final letter, yields a contribution of $pq \sum_{k=1}^{j-1} \sum_{\ell=1}^{k} c_{n-1}(k, \ell)$, upon considering all possible $k$ and $\ell$. If $r \ge 1$ in (a), then removal of the final $r+2$ letters of $\pi$, followed by adding an $\ell$, yields $pq^2 \sum_{k=2}^{j-1} \sum_{\ell=1}^{k-1} \sum_{r=1}^{n-k-2} c_{n-r-1}(k, \ell)$, as the resulting sequence is of the form $\rho'k\ell^{s+1}$ where $s \ge 1$. Further, it is seen that cases (c) and (d) combine to yield $pq \sum_{k=1}^{j-2} \sum_{t=k+1}^{j-1} b_{n-2}(k, t)$, where $t$ denotes the last letter of $\alpha$.

Finally, combining the ten contributions towards the weight coming from all the cases above, and observing the simplifications

$$c_{n-1}(j, j) + \sum_{\ell=1}^{j-1} c_{n-1}(j, \ell) + \sum_{k=1}^{j-1} \sum_{\ell=1}^{k} c_{n-1}(k, \ell) = \sum_{k=1}^{j} \sum_{\ell=1}^{k} c_{n-1}(k, \ell),$$

$$\sum_{k=1}^{j-1} b_{n-2}(k, j) + \sum_{k=1}^{j-2} \sum_{\ell=k+1}^{j-1} b_{n-2}(k, \ell) = \sum_{k=1}^{j-1} b_{n-2}(k, j) + \sum_{\ell=2}^{j-1} \sum_{k=1}^{\ell-1} b_{n-2}(k, \ell) = \sum_{\ell=2}^{j} \sum_{k=1}^{\ell-1} b_{n-2}(k, \ell)$$

and

$$\sum_{\ell=1}^{j-1} \sum_{r=1}^{n-j-2} c_{n-r-1}(j, \ell) + \sum_{k=2}^{j-1} \sum_{\ell=1}^{k-1} \sum_{r=1}^{n-k-2} c_{n-r-1}(k, \ell) = \sum_{k=2}^{j} \sum_{\ell=1}^{k-1} \sum_{r=1}^{n-k-2} c_{n-r-1}(k, \ell),$$

yields (9) and completes the proof. $\square$

From the recurrences in the prior lemma, we have that the nonzero values of $b_n(i, j)$ and $c_n(i, j)$ are given for $n=2$ by $b_2(1, 1) = 1$, for $n=3$ by $b_3(1, 2) = b_3(1, 3) = b_3(2, 2) = q$, $b_3(2, 1) = pq$, $c_3(1, 1) = 1$ and for $n=4$ by

$$b_4(1, 2) = q$$

$$b_4(1, 3) = q + q^2$$

$$b_4(1, 4) = q + 2q^2$$

$$b_4(2, 1) = pq$$

$$b_4(2, 2) = q + pq^2$$

$$b_4(2, 3) = q^2 + pq^2$$

$$b_4(2, 4) = q^2 + pq^2$$

$$b_4(3, 1) = pq + pq^2$$

$$b_4(3, 2) = pq + pq^2$$

$$b_4(3, 3) = q + q^2$$

$$c_4(1, 1) = 1$$

$$c_4(2, 1) = pq$$

$$c_4(2, 2) = q,$$

which may be verified directly using the definitions.
Define now the following generating functions: $A(x) = \sum_{n \ge 1} a_n x^n$, $B(x) = \sum_{n \ge 2} b_n x^n$ and $C(x) = \sum_{n \ge 3} c_n x^n$. Then clearly,

$$A(x) = B(x) + C(x) + \frac{x}{1 - qx}.$$

Note that $A(x)$ is the (ordinary) generating function for the joint distribution of the desc and asc statistics on $I_n(\ge, \ne, >)$ for $n \ge 1$. In order to study $B(x)$ and $C(x)$, we refine them as follows. Define

$$B_0(x, v) = \sum_{n \ge 2} \sum_{i=1}^{n-1} b_n(i, i) v^i x^n,$$
$$B^+(x, v, w) = \sum_{n \ge 2} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} b_n(i, j) v^i w^j x^n,$$
$$B^-(x, v, w) = \sum_{n \ge 3} \sum_{i=2}^{n-1} \sum_{j=1}^{i-1} b_n(i, j) v^i w^j x^n,$$
$$C_0(x, v) = \sum_{n \ge 3} \sum_{i=1}^{n-2} c_n(i, i) v^i x^n,$$
$$C^-(x, v, w) = \sum_{n \ge 4} \sum_{i=2}^{n-2} \sum_{j=1}^{i-1} c_n(i, j) v^i w^j x^n.$$

Translating (3)–(9) above in terms of these generating functions yields the following system of functional equations.

**Lemma 2.** We have $B(x) = B_0(x, 1) + B^+(x, 1, 1) + B^-(x, 1, 1)$ and $C(x) = C_0(x, 1) + C^-(x, 1, 1)$, where

$$B^+(x, v, w) = \frac{qvw^2x^3(w+1)}{1-qvwx} + \frac{qwx}{1-w}(C_0(x, vw) - wC_0(wx, v)) \\ + \frac{qwx}{1-w}(B^+(x, v, w) - wB^+(wx, v, 1)) + \frac{qwx^2}{1-w}(B^+(x, 1, vw) - w^2B^+(wx, 1, v)) \\ + \frac{qw}{1-w}(C^-(x, vw, 1) - C^-(wx, v, 1)) \\ + \frac{q^2w}{1-w}\left(\frac{x}{1-x}C^-(x, vw, 1) - \frac{wx}{1-wx}C^-(wx, v, 1)\right), \\ \\ B_0(x, v) = \frac{vx^2}{1-qvx} + xB^+(x, 1, v) + \frac{q}{1-x}C^-(x, v, 1), \\ \\ B^-(x, v, w) = \frac{pqv^2wx^3}{(1-qvx)(1-qvwx)} + \frac{px}{1-w}(B^+(x, w, v) - B^+(x, 1, vw)) \\ + \frac{pqvx}{1-v-qvx}\left(C^-(x, v, w) - C^-(\frac{vx}{1-qvx}, 1-qvx, w)\right),$$
$$C^{-}(x, v, w) = \frac{x}{1-x} B^{-}(x, v, w),$$

$$C_{0}(x, v) = \frac{vx^{3}}{(1-x)(1-qvx)} + \frac{x^{2}}{1-x} B^{+}(x, 1, v),$$

$$B^{+}(x, v, w) = \frac{qw}{1-w-qwx} \left( C_{0}(x, vw) - C_{0}\left(\frac{wx}{1-qwx}, v(1-qwx)\right) \right) \\ + \frac{qw}{1-w-qwx} \left( C^{-}(x, vw, 1) - C^{-}\left(\frac{wx}{1-qwx}, v(1-qwx), 1\right) \right) \\ + \frac{q^{2}wx}{1-w-qwx} \left( \frac{1}{1-x} C^{-}(x, vw, 1) - \frac{w}{1-wx-qwx} C^{-}\left(\frac{wx}{1-qwx}, v(1-qwx), 1\right) \right)$$

and

$$\frac{1}{pq} B^{-}(x, v, w) \\ = \frac{vx}{p(1-v)}(B^{-}(x, v, w) - B^{-}(vx, 1, w)) + \frac{v^2wx^3}{1-qvwx} + \frac{vx}{1-v}(C^{-}(x, v, w) - C^{-}(vx, 1, w)) \\ + \frac{x}{1-w}\left(\frac{v}{1-v}(C^{-}(x, vw, 1) + C_{0}(x, vw) - C^{-}(vx, w, 1) - C_{0}(vx, w))\right. \\ \left. - \frac{vw}{1-vw}(C^{-}(x, vw, 1) + C_{0}(x, vw) - C^{-}(vwx, 1, 1) - C_{0}(vwx, 1))\right) \\ + \frac{x^2}{1-w}\left(\frac{v}{1-v}(B^{+}(x, 1, vw) - vB^{+}(vx, 1, w)) - \frac{vw}{1-vw}(B^{+}(x, 1, vw) - vwB^{+}(vwx, 1, 1))\right) \\ + qx^2\left(\frac{v}{(1-v)(1-vw)(1-x)}C^{-}(x, vw, 1) - \frac{v^2w}{(1-v)(1-vw)(1-vwx)}C^{-}(vwx, 1, 1)\right. \\ \left. - \frac{v^2}{(1-v)(1-w)(1-vx)}C^{-}(vx, w, 1) + \frac{v^2w}{(1-v)(1-w)(1-vwx)}C^{-}(vwx, 1, 1)\right).$$

By use of the first, fourth and fifth equations in Lemma 2 with $v = 1$, we find a formula for $B^{+}(x, 1, w)$:

$$B^{+}(x, 1, w) = \frac{qw x(qx - x + 1)}{(qw x - wx + w + x - 1)(1-x)} B^{-}(x, w, 1) \\ + \frac{qw^2 x(1-x)(qw x - wx + 1)}{(qw x - wx + w + x - 1)(1 - wx)^2} B^{-}(wx, 1, 1) \\ + \frac{qw^2 x(1-x)}{(qw x - wx + w + x - 1)(1 - wx)} B^{+}(wx, 1, 1) \\ + \frac{qw^2 x^3(1-w)(wx - w - 1)}{(qw x - wx + w + x - 1)(1 - qwx)(1 - wx)}.$$

Using this last expression twice (both for $B^{+}(x, 1, vw)$ and $B^{+}(vx, 1, w)$), substituting into the final equation in Lemma 2 and replacing $x$ with $x/v$, we obtain the following result.
**Lemma 3.** The generating function $A(x)$ is given by

$$A(x) = \frac{1}{1-x} B^{+}(x, 1, 1) + \frac{1-x+qx}{(1-x)^2} B^{-}(x, 1, 1) + \frac{x}{(1-x)(1-qx)},$$

where

$$K(x, v)B^{-}(x/v, 1, v) = A_{1}(x, v)B^{-}(x, 1, 1) + A_{2}(x, v)B^{+}(x, 1, 1) + A_{3}(x, v),$$

with

$$K(x, v) = (x - v)(qx + v - 1)(qvx + v^2 - vx - v + x) - qx^2(qvx - qx + v^2 - vx - 2v + 2x)p,$$

$$A_1(x, v) = (x - v)(qvx + v^2 - vx - v + x)xq + \frac{(v - x)x^2((qv - q - v + 2)x^2 + (v^2 - v - 2)x - v^2 + 2v)qp}{(1 - x)^2},$$

$$A_2(x, v) = \frac{(x - v)(1 - v)(qx^2 + vx - x^2 - v + x)xp}{1 - x},$$

$$A_3(x, v) = \frac{(x - v)(qx^2 - qx + vx - x^2 - v + x + 1)(1 - v)pqx^3}{(1 - x)(1 - qx)}.$$

Note that the kernel equation $K(x, v) = 0$ (see prior lemma) has two power series solutions $v_1(x)$ and $v_2(x)$, where

$$v_1(x) = 1 + (\sqrt{pq} - q)x - \frac{q((2p + 1)\sqrt{pq} - 2pq - p)}{2\sqrt{pq}}x^2 - \frac{q(4(5pq + 3p + q + 1)\sqrt{pq} - 12p^2q - 8pq^2 - 16pq - 3p - q)}{8\sqrt{pq}}x^3 + \dots,$$

$$v_2(x) = 1 - (\sqrt{pq} + q)x - \frac{q((2p + 1)\sqrt{pq} + 2pq + p)}{2\sqrt{pq}}x^2 - \frac{q(4(5pq + 3p + q + 1)\sqrt{pq} + 12p^2q + 8pq^2 + 16pq + 3p + q)}{8\sqrt{pq}}x^3 + \dots.$$

Substituting $v = v_1(x)$ and $v = v_2(x)$ into

$$K(x, v)B^{-}(x/v, 1, v) = A_{1}(x, v)B^{-}(x, 1, 1) + A_{2}(x, v)B^{+}(x, 1, 1) + A_{3}(x, v),$$

and solving for $B^{-}(x, 1, 1)$ and $B^{+}(x, 1, 1)$, we obtain

$$B^{-}(x, 1, 1) = \frac{px(v_{1}(x) - 1)(v_{2}(x) - 1)}{((q - 1)x^2 - v_{1}(x)v_{2}(x) + xv_{1}(x) + xv_{2}(x))(p - q)},$$

$$B^{+}(x, 1, 1) = -\frac{qx(qx - x + 1)(v_{1}(x) - 1)(v_{2}(x) - 1)}{(1 - x)((q - 1)x^2 - v_{1}(x)v_{2}(x) + xv_{1}(x) + xv_{2}(x))(p - q)} \\ + \frac{q(q - 1)x^3(v_{1}(x)v_{2}(x) + x^2)}{(1 - x)(1 - qx)((q - 1)x^2 - v_{1}(x)v_{2}(x) + xv_{1}(x) + xv_{2}(x))} \\ + \frac{qx^2(x^2 - x + 1 - qx)(v_{1}(x) + v_{2}(x)) + q(1 - 2q)x^4 + q(1 + 2q)x^3 - 2qx^2}{(1 - x)(1 - qx)((q - 1)x^2 - v_{1}(x)v_{2}(x) + xv_{1}(x) + xv_{2}(x))}.$$
Hence, by Lemma 3, we have the following result.

**Theorem 4.** The generating function $A(x)$ is given by

$$A(x) = (1 - v_1(x) - v_2(x) - (q-1)x)x(q-1)x^2 - v_1(x)v_2(x) + x(v_1(x) + v_2(x)),$$

where $v_1(x)$ and $v_2(x)$ are the power series solutions to $K(x, v) = 0$ as defined above.

*Remark:* The equation $K(x, v) = 0$ actually has four roots, namely, $v_1(x)$, $v_2(x)$ and the two additional roots given by

$$v_3(x) = x + q\sqrt{p}x\sqrt{x} + \frac{q(2p+1)}{2}x^2 + \frac{q(4p^2 + 8pq + 8p + 1)}{8\sqrt{p}}x^2\sqrt{x} + \dots,$$

$$v_4(x) = x - q\sqrt{p}x\sqrt{x} + \frac{q(2p+1)}{2}x^2 - \frac{q(4p^2 + 8pq + 8p + 1)}{8\sqrt{p}}x^2\sqrt{x} + \dots,$$

where it is assumed $p, q, x > 0$. To determine which of these roots are to be used in obtaining an explicit formula for $B^{-}(x, 1, 1)$ as a Taylor series, we define

$$F(x, v, w) = \frac{px(v-1)(w-1)}{((q-1)x^2 - vw + xv + xw)(p-q)}.$$

Note that $F(x, v, w) = F(x, w, v)$ and so it suffices to consider the first terms in the expansion of $F(x, v_i(x), v_j(x))$ centered at $x = 0$ for $1 \le i < j \le 4$:

$$F(x, v_1(x), v_2(x)) = pqx^3 + (2q + 3)pqx^4 + \dots, \quad F(x, v_1(x), v_3(x)) = -\frac{\sqrt{p}(q - \sqrt{pq})}{q(p-q)}\sqrt{x} + \dots,$$

$$F(x, v_1(x), v_4(x)) = \frac{\sqrt{p}(q - \sqrt{pq})}{q(p-q)}\sqrt{x} + \dots, \quad F(x, v_2(x), v_3(x)) = -\frac{\sqrt{p}(q + \sqrt{pq})}{q(p-q)}\sqrt{x} + \dots,$$

$$F(x, v_2(x), v_4(x)) = \frac{\sqrt{p}(q + \sqrt{pq})}{q(p-q)}\sqrt{x} + \dots, \quad F(x, v_3(x), v_4(x)) = \frac{p}{q(p-q)}\frac{1}{x} + \dots.$$

Hence, we must take $v_1(x)$ and $v_2(x)$, as was done above.

## 2.1 Case $p = q = 1$

Letting $p = q = 1$ in Lemma 3 gives

$$K'(x, v)B^{-}(x/v, 1, v) = A'(x, v)B^{-}(x, 1, 1) + (1-x)A'(x, v)B^{+}(x, 1, 1) + A''(x, v),$$

where

$$K'(x, v) = v^3 - v^2 + 2vx - x^2,$$

$$A'(x, v) = \frac{x(v - x)(vx - v + x)}{(1 - x)^2},$$

$$A''(x, v) = \frac{x^3(v - x)(vx - v + 1)}{(1 - x)^3}.$$
Thus, by taking $v = 1$ or

$$v = v_3(x) = 1 + \frac{16}{9} \sin^4\left(\frac{1}{3} \arcsin\left(\frac{3\sqrt{3}x}{2}\right)\right) - \frac{8}{3} \sin^2\left(\frac{1}{3} \arcsin\left(\frac{3\sqrt{3}x}{2}\right)\right) = 1 - 2x - 3x^2 - 10x^3 + \dots,$$

the latter being a root of $K'(x, v) = 0$, we obtain

$$\frac{(2x-1)(x-1)B^{+}(x, 1, 1) - (x^2 - x + 1)B^{-}(x, 1, 1) - x^3}{(1-x)^2} = 0, \\ \frac{xv_3(x) - v_3(x) + x}{(1-x)^2}B^{-}(x, 1, 1) + \frac{xv_3(x) - v_3(x) + x}{1-x}B^{+}(x, 1, 1) + \frac{x^2(xv_3(x) - v_3(x) + 1)}{(1-x)^3} = 0.$$

**Theorem 5.** Let $y = \cos(\frac{1}{3}\arcsin(\frac{3\sqrt{3}x}{2}))$. Then the generating function $\sum_{n \ge 1} a_n(1, 1)x^n$ is given by

$$- \frac{(4y^2 - 1)^2 - 9x}{2A} \left( B + (64y^6 - 96y^4 + 36y^2 + 27x - 4)(64y^6 - 12y^2 - 27x + 2)\sqrt{1-4x} \right),$$

where $A = (256y^8 - 256y^6 - 48y^4 + 56y^2 + 81x - 8)(x(4y^2 - 1)^4 + (x-1)((4y^2 - 1)^2 - 9x)^2)$ and $B = (4y^2 - 1)^6 - 9(32y^4x + 16y^4 - 16y^2x - 8y^2 - 7x + 1)((4y^2 - 1)^2 - 9x)$.

## 2.2 Coefficient of $p^m$

Note that Lemma 2 implies the following formula.

**Lemma 6.** The generating function $A(x)$ is given by

$$A(x) = \frac{1}{1-x} B^{+}(x, 1, 1) + \frac{1-x+qx}{(1-x)^2} B^{-}(x, 1, 1) + \frac{x}{(1-x)(1-qx)},$$

where

$$\left(1 - \frac{p q v x^2}{(1 - x)(1 - v - q v x)}\right) B^{-}(x, v, w) \\ = \frac{p q v^2 w x^3}{(1 - q v w x)(1 - q v x)} + \frac{p x(B^{+}(x, w, v) - B^{+}(x, 1, vw))}{1 - w} \\ - \frac{p q v^2 x^2}{(1 - v - q v x)(1 - v x - q v x)} B^{-}\left(\frac{v x}{1 - q v x}, 1 - q v x, w\right)$$

and

$$(1 - w - qwx)B^{+}(x, v, w) \\ = \frac{qvw^2x^3(1 + w - wx)(1 - w)}{(1 - x)(1 - wx)(1 - qvwx)} + \frac{qwx^2}{1 - x}B^{+}(x, 1, vw) \\ - \frac{qw^3x^2}{1 - wx}B^{+}(wx, 1, v) - qw^2xB^{+}(wx, v, 1) + \frac{qwx(1 - x + qx)}{(1 - x)^2}B^{-}(x, vw, 1) \\ - \frac{qw^2x(1 - wx + qwx)}{(1 - wx)^2}B^{-}(wx, v, 1),$$
with

$$B^{+}(x, v, 1) = \frac{x}{(1 - qx)(1 - x - qx)} B^{+}\left(\frac{x}{1 - qx}, 1, v(1 - qx)\right) - \frac{x}{1 - x} B^{+}(x, 1, v) \\ - \frac{1 - x + qx}{(1 - x)^2} B^{-}(x, v, 1) + \frac{1 - x}{(1 - x - qx)^2} B^{-}\left(\frac{x}{1 - qx}, v(1 - qx), 1\right) \\ - \frac{(qx + x - 2)qvx^3}{(1 - x - qx)(1 - qx)(1 - x)(1 - qvx)}.$$

Given a generating function $f(x) = f(x,p)$, we denote its coefficient of $p^m$ by $f(x|m)$. From Lemma 6, one obtains the following result.

**Proposition 7.** We have

$$A(x|m) = \frac{1}{1-x} B^{+}(x, 1, 1|m) + \frac{1-x+qx}{(1-x)^2} B^{-}(x, 1, 1|m) + \frac{x}{(1-x)(1-qx)} \delta_{m,0},$$

where $B^{+}(x, v, w|m)$ and $B^{-}(x, v, w|m)$ satisfy

$$B^{-}(x, v, w|m) = \frac{qv x^2}{(1-x)(1-v-qvx)} B^{-}(x, v, w|m-1) + \frac{qv^2 w x^3}{(1-qvwx)(1-qvx)} \delta_{m,1} \\ + \frac{x(B^{+}(x, w, v|m-1) - B^{+}(x, 1, vw|m-1))}{1-w} \\ - \frac{qv^2 x^2}{(1-v-qvx)(1-vx-qvx)} B^{-}(\frac{vx}{1-qvx}, 1-qvx, w|m-1), \quad (10)$$

$$(1 - w - qwx) B^{+}(x, v, w|m) = \frac{qv w^2 x^3 (1 + w - wx)(1 - w)}{(1 - x)(1 - wx)(1 - qvwx)} \delta_{m,0} + \frac{qw x^2}{1 - x} B^{+}(x, 1, vw|m) \\ - \frac{qw^3 x^2}{1 - wx} B^{+}(wx, 1, v|m) - qw^2 x B^{+}(wx, v, 1|m) + \frac{qw x(1 - x + qx)}{(1 - x)^2} B^{-}(x, vw, 1|m) \\ - \frac{qw^2 x(1 - wx + qwx)}{(1 - wx)^2} B^{-}(wx, v, 1|m) \quad (11)$$

and

$$B^{+}(x, v, 1|m) = \frac{x}{(1 - qx)(1 - x - qx)} B^{+}\left(\frac{x}{1 - qx}, 1, v(1 - qx)|m\right) - \frac{x}{1 - x} B^{+}(x, 1, v|m) \\ - \frac{1 - x + qx}{(1 - x)^2} B^{-}(x, v, 1|m) + \frac{1 - x}{(1 - x - qx)^2} B^{-}\left(\frac{x}{1 - qx}, v(1 - qx), 1|m\right) \\ - \frac{(qx + x - 2)qvx^3}{(1 - x - qx)(1 - qx)(1 - x)(1 - qvx)} \delta_{m,0}, \quad (12)$$

with $B^{-}(x, v, w|m) = 0$ for $m < 0$.
### 2.2.1 Case $m = 0$

By Proposition 7, we see that $B^-(x, v, w|0) = 0$ and thus

$$ (1 - w - \frac{qw_x}{w-x})B^+(x/w, 1, w|0) = \frac{qw_x^3(1+w-x)(1-w)}{(w-x)(1-x)(1-qx)} - \frac{qw_x}{1-x}B^+(x, 1, 1|0). $$

Let $w = w_0(x) = \frac{1}{2}(1 + x - qx + \sqrt{(1 + x - qx)^2 - 4x})$. Then

$$ B^+(x, 1, 1|0) = \frac{(w_0(x) + 1 - x)(w_0(x) - 1)x^2}{w_0(x)(qx - 1)(w_0(x) - x)} $$

and

$$ B^+(x, 1, w|0) = \frac{(w_0 wx) - w(w + w_0 wx) - wx)qw^2 x^3}{w_0 wx(w_0 wx) - wx(qwx - 1)(qwx + w - wx - 1 + x)}. $$

Thus, by Lemma 2, we have $C^-(x, v, w|0) = B^-(x, v, w|0) = 0$, and then by Proposition 7, we get

$$ \begin{aligned} B^+(x, v, w|0) &= \frac{qw^2 x^2 (vwx - vw - v + 1) \sqrt{q^2 v^2 w^2 x^2 - 2qw^2 w^2 x^2 + v^2 w^2 x^2 - 2qvx - 2vwx + 1}}{2(qvw^2 x^2 - qvwx + qwx - vwx + wx + v - 1)(qvwx - vwx + vw + x - 1)} \\ &\quad + \frac{qw^2 x^2 (2qwx^2 - qwx + 2wx^2 - 2wx - 2x + 1)}{2(qvwx - vwx + vw + x - 1)(qwx - 1)(qv^2 x^2 - qvwx + qwx - vwx + wx + v - 1)} \\ &\quad + \frac{qv^2 w^2 x^2 (2x - 1 - w(2qx^2 + 2x^2 - 4x + 1) + xw^2(q^2 x + 2qx^2 - 2qx + q - 2x + 2))}{2(qvwx - vwx + vw + x - 1)(qwx - 1)(qv^2 x^2 - qvwx + qwx - vwx + wx + v - 1)} \\ &\quad + \frac{qv^3 w^3 x^3 (wx - w - 1)(q - 1)(qwx - 1)}{2(qvwx - vwx + vw + x - 1)(qwx - 1)(qv^2 x^2 - qvwx + qwx - vwx + wx + v - 1)}. \end{aligned} $$

Hence, Proposition 7 implies the following result.

**Theorem 8.** We have

$$ A(x|0) = \frac{2x}{1 - x - qx + \sqrt{(1 - x - qx)^2 - 4qx^2}}. $$

### 2.2.2 Case $m = 1$

By the $m = 0$ case and Proposition 7, we have

$$ \begin{aligned} B^-(x, v, w|1) &= \frac{qv^2 w x^3}{(1 - qvwx)(1 - qvx)} + \frac{x(B^+(x, w, v|0) - B^+(x, 1, vw|0))}{1 - w} \\ &= \frac{vwx(qvx - vx^2 + vx + x - 1)\sqrt{(1 - (1 + q)vwx)^2 - 4qv^2w^2x^2}}{2(qv^2wx^2 - qvwx + qvx - vwx + vx + w - 1)(qvwx - vwx + vw + x - 1)} \\ &\quad + \frac{vwx((1 - x)(1 - vx)(1 - vwx) + qvx(vwx^2 - wx - w + 2x - 1) + q^2v^2wx^2)}{2(qv^2wx^2 - qvwx + qvx - vwx + vx + w - 1)(qvwx - vwx + vw + x - 1)}. \end{aligned} $$
So the generating function $B^+(x/w, 1, w|1)$ satisfies

$$ (1 - w - \frac{qwx}{w-x})B^+(x/w, 1, w|1) = -\frac{qwx}{1-x}B^+(x, 1, 1|1) + \frac{qwx(w-x+qx)}{(w-x)^2}B^-(x/w, w, 1|1) - \frac{qwx(1-x+qx)}{(1-x)^2}B^-(x, 1, 1|1). $$

By substituting $w = w_0(x)$, we obtain

$$ B^+(x, 1, 1|1) = \frac{(w_0(x) - x + qx)(1-x)}{(w_0(x) - x)^2} B^-(x/w_0(x), w_0(x), 1|1) - \frac{1-x+qx}{1-x} B^-(x, 1, 1|1), $$

which implies that the expression of $B^+(x, 1, w|1)$ can be found from

$$ (1 - w - \frac{qwx}{1-x})B^+(x, 1, w|1) = -\frac{qw^2x}{1-wx}B^+(wx, 1, 1|1) + \frac{qwx(1-x+qx)}{(1-x)^2}B^-(x, w, 1|1) - \frac{qw^2x(1-wx+qwx)}{(1-wx)^2}B^-(wx, 1, 1|1). $$

Hence, by Proposition 7, one gets an explicit formula for $B^+(x, v, 1|1)$, and subsequently for $B^+(x, v, w|1)$, which implies the following result.

**Theorem 9.** We have

$$ A(x|1) = \frac{q^3(q-1)x^4 - (4q^3 + q^2 + q + 1)x^3 + (6q^2 + 5q + 3)x^2 - (4q + 3)x + 1}{2q^2x^4\sqrt{(1-x-qx)^2 - 4qx^2}} + \frac{q^3x^3 - (3q^2 + 2q + 1)x^2 + (3q + 2)x - 1}{2q^2x^4}. $$

### 2.2.3 General Case

Note that our calculation may be extended to any $m > 1$. More precisely, to find the generating function $A(x|m)$, we have the following algorithm:

* Let $m > 1$. Suppose we have found the generating functions $B^+(x, v, w|m-1)$ and $B^-(x, v, w|m-1)$.

* By (10), we have an explicit formula for the generating function $B^-(x, v, w|m)$.

* By (11), we have

$$ (1 - w - \frac{qwx}{w-x})B^+(x/w, 1, w|m) = -\frac{qwx}{1-x}B^+(x, 1, 1|m) + \frac{qwx(w-x+qx)}{(w-x)^2}B^-(x/w, w, 1|m) - \frac{qwx(1-x+qx)}{(1-x)^2}B^-(x, 1, 1|m). $$
Thus, by taking $w = w_0(x)$ and using the formula of $B^-(x/w, w, 1|m)$, we obtain an explicit formula for the generating function $B^+(x, 1, 1|m)$.

* By (11) with $v = 1$, we obtain an explicit formula for $B^+(x, 1, w|m)$.

* By (12), we derive a formula for $B^+(x, v, 1|m)$.

* Thus, by (11) and the results of the previous steps, we obtain a formula for $B^+(x, v, w|m)$.

* Hence, by Proposition 7, namely,

$$A(x|m) = \frac{1}{1-x} B^+(x, 1, 1|m) + \frac{1-x+qx}{(1-x)^2} B^-(x, 1, 1|m),$$

we derive a formula for the generating function $A(x|m)$.

Applying this algorithm for $m = 2, 3$ yields

$$A(x|m) = \frac{a_m}{2q^{m+1}x^{3m+1}(qx + x - 1)^{2m-3}\sqrt{(1 - x - qx)^2 - 4qx^2}^{2m-1}} + \frac{b_m}{2q^{m+1}x^{3m+1}(qx + x - 1)^{2m-3}},$$

where

$$a_2 = (x+1)(x-1)^7 + x(2x^3 - 5x^2 - 3x - 9)(x-1)^5q - 2x^2(x^4 + 6x^3 - 13x^2 + 9x - 18)(x-1)^3q^2 - 2x^3(x-1)(3x^4 - 30x^3 + 53x^2 - 63x + 42)q^3 - 2x^4(3x^4 - 36x^3 + 80x^2 - 105x + 63)q^4 + x^5(2x^5 + x^4 - 9x^3 + 64x^2 - 126x + 126)q^5 - 2x^6(3x^4 + 5x^3 + 10x^2 - 21x + 42)q^6 + 2x^7(3x^3 + 4x^2 - 3x + 18)q^7 - x^8(2x^2 + 9)q^8 + x^9q^9,$$

$$b_2 = (x+1)(x-1)^4 + x(2x^3 - 2x^2 + 3x - 6)(x-1)^2q + x^2(x-1)(4x^3 - 11x^2 + 15x - 15)q^2 + 2x^3(3x^3 - 10x^2 + 15x - 10)q^3 + x^4(8x^2 - 15x + 15)q^4 - x^5(2x^2 - 3x + 6)q^5 + x^6q^6,$$

$$a_3 = -(2x^2 + 2x + 1)(x-1)^{12} - x(4x^4 - 6x^3 - 25x^2 - 18x - 15)(x-1)^{10}q - x^2(3x^6 - 18x^5 - 15x^4 - 4x^3 + 147x^2 + 34x + 105)(x-1)^8q^2 + x^3(4x^7 + 29x^6 - 144x^5 + 74x^4 - 404x^3 + 692x^2 - 286x + 455)(x-1)^6q^3 + x^4(6x^8 - 40x^7 - 195x^6 + 714x^5 - 1325x^4 + 2944x^3 - 3211x^2 + 2262x - 1365)(x-1)^4q^4 - x^5(12x^8 + 15x^7 + 89x^6 - 1131x^5 + 2715x^4 - 5925x^3 + 7381x^2 - 5291x + 3003)(x-1)^3q^5 + x^6(5x^8 + 10x^7 - 65x^6 + 1320x^5 - 4210x^4 + 9650x^3 - 12837x^2 + 9724x - 5005)(x-1)^2q^6 - x^7(x-1)(5x^9 - 11x^8 - 15x^7 + 73x^6 - 1422x^5 + 5370x^4 - 13143x^3 + 17853x^2 - 14157x + 6435)q^7 + x^8(22x^9 - 25x^8 - 28x^7 - 112x^6 + 1448x^5 - 6076x^4 + 15192x^3 - 20526x^2 + 16302x - 6435)q^8 - x^9(35x^8 + 26x^6 + 214x^5 - 1130x^4 + 5170x^3 - 9878x^2 + 9724x - 5005))q^9 + x^{10}(20x^7 - 2x^6 + 20x^5 - 62x^4 + 1132x^3 - 3619x^2 + 4290x - 3003)q^{10} + x^{11}(5x^6 + 20x^5 - 4x^4 - 114x^3 + 1045x^2 - 1352x + 1365)q^{11} - x^{12}(10x^5 + 9x^4 + 12x^3 + 245x^2 - 286x + 455))q^{12} + x^{13}(3x^4 + 4x^3 + 43x^2 - 36x + 105)q^{13} - x^{14}(4x^2 - 2x + 15)q^{14} + x^{15}q^{15},$$
$$
\begin{align*}
b_3 = &-(2x^2 + 2x + 1)(x-1)^7 - x(2x^2 + x + 2)(2x^2 + x - 5)(x-1)^5q - x^2(3x^6 + 2x^5 + 5x^4 - 49x^3 \\
& + 57x^2 - 61x + 45)(x-1)^3q^2 - x^3(11x^6 - 33x^5 + 86x^4 - 218x^3 + 276x^2 - 236x + 120)(x-1)^2q^3 \\
& - x^4(x-1)(19x^6 - 97x^5 + 287x^4 - 588x^3 + 707x^2 - 532x + 210)q^4 - x^5(27x^6 - 166x^5 + 532x^4 \\
& - 1007x^3 + 1134x^2 - 770x + 252)q^5 - x^6(35x^5 - 181x^4 + 474x^3 - 665x^2 + 532x - 210)q^6 + x^7(5x^5 \\
& - 34x^4 + 128x^3 - 240x^2 + 236x - 120)q^7 + x^8(3x^4 - 16x^3 + 48x^2 - 61x + 45)q^8 - x^9(4x^2 \\
& - 7x + 10)q^9 + x^{10}q^{10}.
\end{align*}
$$

3 The desc and $n-1$-asc statistics on $I_n(>, \neq, \ge)$

We start by decomposing the set $\mathcal{T}_n = I_n(>, \neq, \ge)$ as follows. To do so, it is useful to consider the largest descent bottom $x$ of $e = e_1 e_2 \cdots e_n \in \mathcal{T}_n$ where $e$ contains at least one descent; that is, $x = \max\{e_{i+1} : 1 \le i \le n-1$ and $e_i > e_{i+1}\}$. If $w$ is the leftmost letter of $e$ forming a descent with $x$, then $w$ will be referred to as the leftmost top of $e$. Let $\mathcal{U}_n(i, j)$ for $i < j$ denote the subset of $\mathcal{T}_n$ consisting of those $e$ having leftmost top $i$ and largest letter $j$, where it is assumed further that $e$ ends in a $j$. Let $\mathcal{V}_n(i, j)$ for $i < j$ be the same as $\mathcal{U}_n(i, j)$ except that $j$ is not the last letter of $e$. Let $\mathcal{W}_n(i, j)$ for $i > j$ be the subset of $\mathcal{T}_n$ whose members $e$ have leftmost top $i$ and are expressible as $e = e'ij^s$ for some $s \ge 1$ where $\max(e') \le i$. Finally, let $\mathcal{Z}_n(i)$ be the subset of $\mathcal{T}_n$ whose members end in $i$ and are weakly increasing (i.e., contain no descents).

A few remarks are in order concerning these definitions. Note that the leftmost letter $i$ forming a descent with $x$ within any member of $\mathcal{T}_n$ is also the smallest such letter, for otherwise a $(> , \neq , \ge)$ would be present with $ixz$, where $z$ is the smallest. Further, no element greater than $i$ can occur anywhere to the left of the first $i$ due to avoidance of $(> , \neq , \ge)$, with all $i$'s occurring as a single run (directly preceding the first $x$). Similarly, $x$ is the only element less than $i$ occurring somewhere to the right of the run of $i$'s. Thus, members of $\mathcal{V}_n(i, j)$ must end in $x$, for otherwise there would be an occurrence of $(> , \neq , \ge)$ involving the last letter or a descent bottom that exceeds $x$ contradicting its maximality. Further, members of $\mathcal{W}_n(i, j)$ are seen to have largest descent bottom $j$. Finally, a common interpretation for the parameter $j$ which applies to all three of the subsets $\mathcal{U}_n(i, j)$, $\mathcal{V}_n(i, j)$ and $\mathcal{W}_n(i, j)$ is that it represents the largest element occurring anywhere to the right of the run of the letter $i$.

Define the distribution polynomial $u_n(i, j) = u_n(i, j; p, q)$ by

$$
u_n(i, j) = \sum_{\pi \in \mathcal{U}_n(i, j)} p^{\text{desc}(\pi)} q^{n-1-\text{asc}(\pi)},
$$

and likewise for $v_n(i, j)$, $w_n(i, j)$ and $z_n(i)$. For example, we have $\mathcal{V}_5(2, 4) = \{12141\}$,

$$
\mathcal{U}_5(2, 4) = \{11214, 12114, 12134, 12144, 12214\},
$$

$$
\mathcal{W}_5(3, 2) = \{11132, 11232, 11322, 11332, 12232, 12322, 12332\}
$$

and

$$
\mathcal{Z}_4(4) = \{1114, 1124, 1134, 1224, 1234\},
$$
which implies $v_5(2, 4) = p^2q^2$, $u_5(2, 4) = pq + 4pq^2$, $w_5(3, 2) = 4pq^2 + 3pq^3$ and $z_4(4) = 1 + 3q + q^2$. Put zero for any of these polynomial arrays if the subset of $\mathcal{T}_n$ corresponding to the parameters in question is empty. Thus, these arrays may be nonzero only for the following parameter values: (i) $u_n(i, j): n \ge 4$, $2 \le i \le n-2$ and $i < j \le n$, (ii) $v_n(i, j): n \ge 5$, $2 \le i \le n-3$ and $i < j \le n-1$, (iii) $w_n(i, j): n \ge 3$ and $1 \le j < i \le n-1$ and (iv) $z_n(i): n \ge 1$ and $1 \le i \le n$.

Define $u_n = \sum_{i=2}^{n-2} \sum_{j=i+1}^{n} u_n(i, j)$ for $n \ge 4$, and likewise $v_n$ for $n \ge 5$, $w_n$ for $n \ge 3$ and $z_n$ for $n \ge 1$. Then we seek a formula for $t_n = t_n(p, q)$ given by

$$t_n = u_n + v_n + w_n + z_n, \quad n \ge 1,$$

where we put zero for $u_n$, $v_n$ or $w_n$ if the corresponding subset of $\mathcal{T}_n$ is empty. Note that $t_n$ gives the joint distribution of the desc and $n-1$-asc statistics on all of $\mathcal{T}_n$. Recall that $n-1$-asc($\pi$) = desc($\pi$)+lev($\pi$) for all $\pi \in I_n$.

The arrays $u_n(i, j)$, $v_n(i, j)$, $w_n(i, j)$ and $z_n(i)$ satisfy the following system of intertwined recurrences.

**Lemma 10.** We have

$$u_n(i, j) = q u_{n-1}(i, j) + \sum_{\ell=1}^{i-1} w_{n-1}(i, \ell) + \sum_{\ell=i+1}^{j-1} (u_{n-1}(i, \ell) + v_{n-1}(i, \ell)), \quad (13)$$

for $2 \le i \le n-2$ and $i < j \le n$,

$$v_n(i, j) = q(p u_{n-1}(i, j) + v_{n-1}(i, j)), \quad (14)$$

for $2 \le i \le n-3$ and $i < j \le n-1$,

$$w_n(i, j) = pqz_{n-1}(i) + q(2w_{n-1}(i, j) - qw_{n-2}(i, j) - pqz_{n-2}(i)) + pq \sum_{k=2}^{j-1} u_{n-2}(k, j) \\ + pq \sum_{k=2}^{j-1} (u_{n-1}(k, j) - qw_{n-2}(k, j)) + \sum_{k=j+1}^{i-1} (w_{n-1}(k, j) - qw_{n-2}(k, j) - pqz_{n-2}(k)), \quad (15)$$

for $1 \le j < i \le n-1$,

$$z_n(i) = qz_{n-1}(i) + \sum_{j=1}^{i-1} z_{n-1}(j), \quad 1 \le i \le n-1, \quad (16)$$

$$z_n(n) = \sum_{j=1}^{n-1} z_{n-1}(j), \quad n \ge 2, \quad (17)$$

with the initial condition $z_1(1) = 1$.

**Proof:** To show (13), first suppose $\pi \in \mathcal{U}_n(i, j)$ where $i$ and $j$ are as given. If the penultimate letter of $\pi$ is also $j$, then there are clearly $qu_{n-1}(i, j)$ possibilities, so assume that this is not the case. Let $\ell$ be the
second largest letter of $\pi$ occurring to the right of the last $i$, $x$ be the maximum descent bottom and $y$ be the penultimate letter. Then $y < x$ is not possible, for otherwise $ixy$ would be an occurrence of $(>,$ $\neq,$ $\ge$). Further, $x < y < \ell$ is also not possible. To see this, suppose to the contrary that $x < y < \ell$ and let $w$ denote the rightmost letter in $\pi$ that is distinct from both $y$ and $j$. If $w > y$, then $y$ would be a descent bottom, contradicting that $x$ is the maximum descent bottom. If $w < y$, then an occurrence of $(>,$ $\neq,$ $\ge$) would be witnessed by $\ell wy$. Thus, we must have $y = \ell$ or $y = x$. If $y = \ell$ and $\ell \in [i+1, j-1]$, then there are $u_{n-1}(i, \ell)$ possibilities by definition, upon deleting $j$. If $y = x$ and $\ell \in [i+1, j-1]$, then $\pi$ is expressible as $\pi = \pi'\ell x^r j$ for some $r \ge 1$ where $\max(\pi') \le \ell$. Note that the letter directly preceding the run $x^r$ must be $\ell$, for otherwise membership in $\mathcal{T}_n$ would be violated. Removing $j$ from $\pi$ then gives $v_{n-1}(i, \ell)$ for the contribution towards the weight in this case. Thus, the total weight of the members of $\mathcal{U}_n(i, j)$ in question for which $i < \ell < j$ is given by $\sum_{\ell=i+1}^{j-1} (u_{n-1}(i, \ell) + v_{n-1}(i, \ell))$. On the other hand, only $\ell = x$ is possible if it is assumed that $\ell \le i$. In this case, all letters to the right of the last $i$ (except $j$) are $x$. Thus, removing $j$ and considering all possible values of $x$ yields the remaining sum on the right side of (13), which finishes the proof of (13).

To show (15), suppose $\pi \in W_n(i, j)$ where $1 \le j < i \le n-1$. If $\pi$ ends in two or more $j$'s or if it is of the form $\pi = \pi'ij$, where $\pi'$ has no descents, then there are contributions towards the weight of $qw_{n-1}(i, j)$ and $pqz_{n-1}(i)$, respectively. Note that the extra $q$ factor in the former case accounts for the level between the last two letters of $\pi$ which is lost when the final letter is deleted, whereas $pq$ in the latter case accounts for the descent between $i$ and $j$ which is lost. So assume henceforth $\pi = \pi'ij$, where $\pi'$ contains at least one descent; note that $\max(\pi') \le i$. Let $k$ denote the final letter of $\pi'$. If $k \in [j+1, i-1]$, then there are $w_{n-1}(k, j) - qw_{n-2}(k, j) - pqz_{n-2}(k)$ possibilities for each $k$ by subtraction, upon deleting $i$, and summing over all $k$ gives the last summation expression on the right side of (15). If $k=i$, then one gets $q(w_{n-1}(i, j) - qw_{n-2}(i, j) - pqz_{n-2}(i))$, where the $q$ factor accounts for the extra level occurring between the last two letters $i$.

Suppose now $k=j$ and let $z$ and $\ell$ denote the largest descent bottom and leftmost top of $\pi'$, respectively. Then $\ell=i$ is not possible, for otherwise $(>,$ $\neq,$ $\ge$) is realized with $iji$, so we must have $\ell < i$. If $j < \ell < i$ and $z \neq j$, then $\ell z j$ would not be allowed, whereas if $z=j$, then the resulting inversion sequence would be of a form not even enumerated by $w_n(i, j)$ since $\ell$, and not $i$, would be the leftmost top of $\pi$. If $\ell=j$, then $jzj$ would occur with $z < j$, which is again not allowed. Thus, we must have $2 \le \ell \le j-1$ and deleting $ij$ from $\pi$ yields a member of $\mathcal{U}_{n-2}(\ell, j)$. Considering all possible $\ell$ in this case then gives a contribution towards the weight of $pq \sum_{\ell=2}^{j-1} u_{n-2}(\ell, j)$. Finally, if $k < j$, then $\ell \ge j$ would imply $\ell k j$ is not permissible, whence $2 \le \ell \le j-1$. Then deleting $i$ from $\pi$ in this case results in a member of $\mathcal{U}_{n-1}(\ell, j)$ in which the next-to-last letter is not $j$. By subtraction, there is a contribution of $pq(u_{n-1}(\ell, j) - qw_{n-2}(\ell, j))$ for each $\ell$, which we then sum over $\ell$. Combining now all of the previous cases implies (15).

The remaining formulas can be shown quickly. To realize (14), consider cases based on whether the terminal run of the maximum descent bottom of $\pi \in V_n(i, j)$ is of length one or greater than one. Note that in the former case, the next-to-last letter must be $j$ resulting in a descent involving the final two letters. To show (16) and (17), we delete the final $i$ from $\pi \in \mathbb{Z}_n(i)$ and consider cases on whether the next-to-last letter equals $i$ or is less than $i$, noting that the first option is not possible in the case $i=n$ since $\pi \in I_n$. $\square$

From the recurrences, we have that the nonzero values of the arrays above are given for $n=2$ by $z_2(1)=q$, $z_2(2)=1$, for $n=3$ by $w_3(2, 1)=pq$, $z_3(1)=q^2$, $z_3(2)=2q$, $z_3(3)=1+q$ and for $n=4$
by

$$
\begin{align*}
& u_4(2, 3) = pq & u_4(2, 4) = pq & w_4(2, 1) = 3pq^2 \\
& w_4(3, 1) = pq + pq^2 & w_4(3, 2) = pq + pq^2 & z_4(1) = q^3 \\
& z_4(2) = 3q^2 & z_4(3) = 3q + 2q^2 & z_4(4) = 1 + 3q + q^2,
\end{align*}
$$

which may be verified directly.

Now define

$$
\begin{align*}
U(x, v, w) &= \sum_{n \ge 4} \sum_{i=2}^{n-2} \sum_{j=i+1}^{n} u_n(i, j) v^i w^j x^n, \\
V(x, v, w) &= \sum_{n \ge 5} \sum_{i=2}^{n-3} \sum_{j=i+1}^{n-1} v_n(i, j) v^i w^j x^n, \\
W(x, v, w) &= \sum_{n \ge 3} \sum_{i=2}^{n-1} \sum_{j=1}^{i-1} w_n(i, j) v^i w^j x^n, \\
Z(x, v) &= \sum_{n \ge 1} \sum_{i=1}^{n} z_n(i) v^i x^n.
\end{align*}
$$

By translating (13)–(17) above in terms of these generating functions, we obtain the following system of
functional equations.

**Lemma 11.** We have

$$
\begin{align*}
U(x, v, w) &= qxU(x, v, w) + \frac{wx}{1-w}(W(x, vw, 1) - wW(wx, v, 1)) \\
&\quad + \frac{wx}{1-w}(U(x, v, w) + V(x, v, w) - wU(wx, v, 1) - wV(wx, v, 1)), \\
V(x, v, w) &= pqxU(x, v, w) + qxV(x, v, w), \\
W(x, v, w) &= \frac{pqx}{1-w}(wZ(x, v) - Z(x, vw)) + 2qxW(x, v, w) - q^2x^2W(x, v, w) \\
&\quad - \frac{pq^2x^2}{1-w}(wZ(x, v) - Z(x, vw)) + \frac{pqvx^2}{1-v}(U(x, 1, vw) - vU(vx, 1, w)) \\
&\quad + \frac{pqvx}{1-v}(U(x, 1, vw) - U(vx, 1, w) - qxU(x, 1, vw) + qvxU(vx, 1, w)) \\
&\quad + \frac{v}{1-v}(xW(x, v, w) - qx^2W(x, v, w)) - \frac{pqvx^2}{(1-v)(1-w)}(wZ(x, v) - Z(x, vw)) \\
&\quad - \frac{vx}{1-v}(W(vx, 1, w) - qvxW(vx, 1, w)) + \frac{pqv^2x^2}{(1-v)(1-w)}(wZ(vx, 1) - Z(vx, w)), \\
Z(x, v) &= vxZ(vx, 1) + vx + qxZ(x, v) + \frac{vx}{1-v}(Z(x, v) - Z(vx, 1)).
\end{align*}
$$
The last equation in Lemma 11 implies

$$ \left(1 - \frac{qx}{v} - \frac{x}{1-v}\right) Z(x/v, v) = x + xZ(x, 1) - \frac{x}{1-v}Z(x, 1). $$

By taking $v = v_0(x) = \frac{1}{2}(1 - x + qx + \sqrt{(1 - x + qx)^2 - 4qx})$, we obtain

$$ Z(x, 1) = \frac{1 - v_0(x)}{v_0(x)}, $$

and hence

$$ Z(x, v) = \frac{vx(v_0(vx) - v)}{v_0(vx)((1-v)(1-qx) - vx)}. \qquad (18) $$

Further, Lemma 11 gives

$$ V(x, v, w) = \frac{qpx}{1 - qx} U(x, v, w). $$

Thus Lemma 11 implies that the generating functions $U(x, 1, v)$ and $W(x, v, 1)$ satisfy

$$ U(x, 1, v) = qxU(x, 1, v) + \frac{vx}{1-v}(W(x, v, 1) - vW(vx, 1, 1)) \\ + \frac{vx}{1-v}(U(x, 1, v) + \frac{pqx}{1-qx}U(x, 1, v) - vU(vx, 1, 1) - \frac{pqvx}{1-qx}U(vx, 1, 1)) $$

$$ W(x, v, 1) = 2qxW(x, v, 1) - q^2x^2W(x, v, 1) + \frac{pqvx^2}{1-v}(U(x, 1, v) - vU(vx, 1, 1)) \\ + \frac{pqvx}{1-v}(U(x, 1, v) - U(vx, 1, 1) - qxU(x, 1, v) + qvxU(vx, 1, 1)) \\ + \frac{v}{1-v}(xW(x, v, 1) - qx^2W(x, v, 1)) - \frac{vx}{1-v}(W(vx, 1, 1) - qvxW(vx, 1, 1)) \\ + F(x, v), $$

where

$$ F(x, v) = \lim_{w \to 1} \left( \frac{pqx(1-qx)}{1-w} (wZ(x,v) - Z(x,vw)) - \frac{pqvx^2}{(1-v)(1-w)} (wZ(x,v) - Z(x,vw)) \right. \\ \left. + \frac{pqv^2x^2}{(1-v)(1-w)} (wZ(vx,1) - Z(vx,w)) \right). $$

Hence, by finding $U(x, 1, v)$ in the first equation and substituting it into the second with use of (18), one obtains the following result.

**Lemma 12.** We have

$$ K(x, v)W(x, v, 1) = A(x, v)W(vx, 1, 1) + B(x, v)U(vx, 1, 1) + F(x, v), $$
where

$$K(x, v) = \frac{(qx - 1)^2((qx - 1)^2 - (pqx^2 + 2q^2x^2 - 2qx^2 - 4qx + 2x + 2)v + (qx - x - 1)^2v^2)}{(1 - v)((qx - 1)^2 - (pqx^2 + q^2x^2 - qx^2 - 2qx + x + 1)v)}$$

$$A(x, v) = -\frac{x(qx - 1)^2 v + x(q^3 x^3 + q(p - q - 1)x^2 - (q - 1)x + 1)v^2}{(1 - v)((qx - 1)^2 - (pqx^2 + q^2x^2 - qx^2 - 2qx + x + 1)v)} - \frac{qx^2(q(pq + q - 1)x^2 + (1 - 2q)(p + 1)x + p + 1)v^3}{(1 - v)((qx - 1)^2 - (pqx^2 + q^2x^2 - qx^2 - 2qx + x + 1)v)}$$

$$B(x, v) = -\frac{pqx(qx - 1)^2 v - pq^2 x^2 (q(2q - 1)x^2 + (p - 4q + 1)x + 2)v^2}{(1 - qvx)((qx - 1)^2 - (pqx^2 + q^2x^2 - qx^2 - 2qx + x + 1)v)} - \frac{pq^2 x^3 (q^2(q - 1)x^2 - (1 - 2q)(p - q)x - p + q)v^3}{(1 - qvx)((qx - 1)^2 - (pqx^2 + q^2x^2 - qx^2 - 2qx + x + 1)v)}$$

$$F(x, v) = \frac{p(qv(q - 1)x^2 - q(v + 1)x + 1)}{2((q - 1)vx - qx - v + 1)} \sqrt{(1 - vx + qvx)^2 - 4qvx} + \frac{(qv^2(q - 1)^2 x^3 - qv(qv - 2q + v)x^2 + (2qv + q + v)x - 1)}{2(qvx - qx - vx - v + 1)}$$

For the kernel equation $K(x/v, v) = 0$, namely,

$$pqvx^2 - ((qx - v)(v - 1) - vx)^2 = 0,$$

we have two different power series solutions $v(x) = f_1(x)$, $f_2(x)$ such that $v(0) = 1$ that are given by

$$f_1(x) = 1 - (1 - \sqrt{pq})x - \frac{q}{2\sqrt{pq}}(\sqrt{pq}(p + 2) - p(2q + 1))x^2 - \frac{q}{8\sqrt{pq}}(8\sqrt{pq}(2pq + q + p + 1) - p(5pq + 8q^2 + 24q + 3))x^3 + \dots$$

$$f_2(x) = 1 - (1 + \sqrt{pq})x - \frac{q}{2\sqrt{pq}}(\sqrt{pq}(p + 2) + p(2q + 1))x^2 - \frac{q}{8}(8\sqrt{pq}(2pq + p + q + 1) + p(5pq + 8q^2 + 24q + 3))x^3 + \dots$$

Replacing $x$ by $x/v$ in Lemma 12, we have

$$K(x/v, v)W(x/v, v, 1) = A(x/v, v)W(x, 1, 1) + B(x/v, v)U(x, 1, 1) + F(x/v, v).$$

By taking $v = f_1(x)$ and $v = f_2(x)$ in this last equation, we obtain the system

$$A(x/f_1(x), f_1(x))W(x, 1, 1) + B(x/f_1(x), f_1(x))U(x, 1, 1) + F(x/f_1(x), f_1(x)) = 0,$$

$$A(x/f_2(x), f_2(x))W(x, 1, 1) + B(x/f_2(x), f_2(x))U(x, 1, 1) + F(x/f_2(x), f_2(x)) = 0,$$

which leads to

$$U(x, 1, 1) = -\frac{A(x/f_1(x), f_1(x))F(x/f_2(x), f_2(x)) - A(x/f_2(x), f_2(x))F(x/f_1(x), f_1(x))}{A(x/f_1(x), f_1(x))B(x/f_2(x), f_2(x)) - A(x/f_2(x), f_2(x))B(x/f_1(x), f_1(x))} \quad (19)$$

$$W(x, 1, 1) = -\frac{F(x/f_1(x), f_1(x))B(x/f_2(x), f_2(x)) - F(x/f_2(x), f_2(x))B(x/f_1(x), f_1(x))}{A(x/f_1(x), f_1(x))B(x/f_2(x), f_2(x)) - A(x/f_2(x), f_2(x))B(x/f_1(x), f_1(x))} \quad (20)$$
Moreover, we have $V(x, 1, 1) = \frac{qpx}{1-qx}U(x, 1, 1)$.

Combining the results above yields the following generating function formula.

**Theorem 13.** The generating function $\sum_{n \ge 1} t_n(p, q)x^n$ is given by

$$ \frac{1 - qx + qpx}{1 - qx} U(x, 1, 1) + W(x, 1, 1) + Z(x, 1), $$

where $Z(x, 1)$, $U(x, 1, 1)$ and $W(x, 1, 1)$ are given by (18), (19) and (20), respectively.

*Remark:* The equation $K(x/v, v) = 0$ actually has six roots (counting multiplicities), namely, $v_1(x) = f_1(x)$, $v_2(x) = f_2(x)$, $v_3(x) = f_3(x) = qx$ and the following additional root of multiplicity two given by

$$ v_5(x) = v_6(x) = qx + q\sqrt{px}\sqrt{x} + \frac{q(p+2)}{2}x^2 + \frac{\sqrt{pq}(p+8q+12)}{8}x^2\sqrt{x} + \dots, $$

assuming $p, q, x > 0$. We must decide which roots to use in obtaining an explicit formula for $U(x, 1, 1)$ as a series, and in accordance with (19), we define

$$ G(x, v, w) = - \frac{A(x/v, v)F(x/w, w) - A(x/w, w)F(x/v, v)}{A(x/v, v)B(x/w, w) - A(x/w, w)B(x/v, v)}. $$

Since $G(x, v, w) = G(x, w, v)$, it suffices to consider the first few terms in the expansion of $G(x, v_i(x), v_j(x))$ about $x = 0$ for $(i, j) \in \{(1, 2), (1, 3), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5), (5, 6)\}$. From this, it is seen that $G(x, v_i(x), v_j(x))$ is a generating function in $x$ whose coefficients are polynomials in $p$ and $q$ only when $(i, j) = (1, 2)$.

### 3.1 Case $p = q = 1$

Then the kernel equation $K(x/v, v) = 0$ in this case has for two of its roots

$$ v = 1 \text{ and } v = 1 + \frac{16}{9} \sin^4\left(\frac{1}{3} \arcsin\left(\frac{3\sqrt{3}x}{2}\right)\right) - \frac{8}{3} \sin^2\left(\frac{1}{3} \arcsin\left(\frac{3\sqrt{3}x}{2}\right)\right). $$

Proceeding as in the proof of Theorem 13, we obtain the following result.

**Theorem 14.** Let $y = \cos(\frac{1}{3}\arcsin(\frac{3\sqrt{3}x}{2}))$. Then the generating function $\sum_{n \ge 0} t_n(1, 1)x^n$ is given by

$$ -\frac{(4y^2 - 1)^2 - 9x}{2A} \left( B + (64y^6 - 96y^4 + 36y^2 + 27x - 4)(64y^6 - 12y^2 - 27x + 2)\sqrt{1-4x} \right), $$

where $A = (256y^8 - 256y^6 - 48y^4 + 56y^2 + 81x - 8)(x(4y^2 - 1)^4 + (x-1)((4y^2 - 1)^2 - 9x)^2)$ and $B = (4y^2 - 1)^6 - 9(32y^4x + 16y^4 - 16y^2x - 8y^2 - 7x + 1)((4y^2 - 1)^2 - 9x)$.

*Remark:* Comparing Theorems 5 and 14 implies (2), which was originally shown in [11] by a different method.
## 3.2 Case $p = 1$

Comparing the formulas from Theorems 4 and 13 when $p = 1$, one can show with the aid of mathematical programming the following result which is equivalent to (1).

**Corollary 15.** We have $a_n(1, q) = t_n(1, q)$ for all $n \ge 1$.

*Remark:* The joint distributions $a_n(p, q)$ and $t_n(p, q)$ are seen however to differ for general $p$, where $p$ marks the number of descents (upon comparing the $n = 5$ terms of the corresponding generating functions).

## 3.3 Coefficient of $p^m$

Recall that we denote the coefficient of $p^m$ in a generating function $f(x)$ by $f(x|m)$. Note that by (18), we get

$$Z(x, v|0) = \frac{vx(v_0(vx) - v)}{v_0(vx)((1-v)(1-qx) - vx)},$$

with $Z(x, v|m) = 0$ for all $m \ge 1$.

By Lemma 12, we get

$$K'(x, v)W(x, v, 1) = A'(x, v)W(vx, 1, 1) + B'(x, v)U(vx, 1, 1) + F'(x, v),$$

where

$$K'(x, v) = \frac{(qx - 1)^2((q - 1)vx - qx - v + 1)^2}{1 - v} - \frac{(qx - 1)^2vx^2qp}{1 - v},$$

$$A'(x, v) = \frac{vx(qx - 1)(1 - qvx)((q - 1)vx - qx - v + 1)}{1 - v} - \frac{v^2x^2q(q^2vx^2 + (1 - 2q)vx + v - x)}{1 - v}p,$$

$$B'(x, v) = (qx - 1)(q(q - 1)vx^2 - qvx - qx + 1)qxvp + \frac{q^2x^3v^2((1 - 2q)vx + v + 1)}{1 - qvx}p^2,$$

$$F'(x, v) = (q(q - 1)vx^2 - qvx - qx + 1)\left(\frac{1}{2}(1 - qx)p - \frac{vx^2q}{2((q - 1)vx - qx - v + 1)}p^2\right)\sqrt{(1 - vx + qvx)^2 - 4qvx} + (vx(q(1 - 2q)vx^2 + qvx + 1) - (1 - qx)(1 - qvx)^2)\left(\frac{1}{2}(1 - qx)p - \frac{vx^2q}{2((q - 1)vx - qx - v + 1)}p^2\right).$$

Thus,

$$ \begin{aligned} & K'(x/v, v|0)W(x/v, v, 1|m) + K'(x/v, v|1)W(x/v, v, 1|m-1) \\ &= A'(x/v, v|0)W(x, 1, 1|m) + A'(x/v, v|1)W(x, 1, 1|m-1) \\ &\quad + B'(x/v, v|1)U(x, 1, 1|m-1) + B'(x/v, v|2)U(x, 1, 1|m-2) \\ &\quad + F'(x/v, v|1)\delta_{m,1} + F'(x/v, v|2)\delta_{m,2}. \end{aligned} \quad (21) $$

This equation performs a procedure which computes the coefficient of $p^m$ for all $m \ge 0$. Clearly,

$$V(x, v, w|m) = U(x, v, w|m) = W(x, v, w|m) = 0, \quad m \le 0.$$

Hence, by Theorem 13, we have that the coefficient of $p^0$ in the generating function $\sum_{n \ge 1} t_n x^n$ is given by $Z(x, 1) = \frac{1 - v_0(x)}{v_0(x)}$.
### 3.3.1 Case $m = 1$

Suppose $m = 1$. Clearly, $Z(x, v|1) = 0$. By Lemma 11, we have $V(x, v, w|1) = 0$. Then by (21), we get

$$ 
\begin{aligned}
& \frac{((q-1)vx - qx - v^2 + v)^2(qx - v)^2}{v^2(1-v)} W(x/v, v, 1|1) \\
& = -\frac{((q-1)vx - qx - v^2 + v)x(qx - 1)(qx - v)}{1-v} W(x, 1, 1) \\
& \quad -\frac{1}{2}(qx - v)(q(q-1)x^2 - qxv - qx + v)\sqrt{(q-1)^2x^2 - 2(q+1)x + 1} \\
& \quad +\frac{1}{2}(qx - v)(q(q-1)^2x^3 - q(q-1)vx^2 - 2q^2x^2 + (2q+1)vx + qx - v).
\end{aligned}
$$

Differentiating with respect to $v$ and then substituting $v = v_0(x)$, we obtain

$$ W(x, 1, 1|1) = \frac{q(q-1)^2x^3 - q(3q-1)x^2 + (3q+1)x - 1}{2x(qx-1)\sqrt{(q-1)^2x^2 - 2(q+1)x + 1}} + \frac{(qx-1)^2 - qx^2}{2x(qx-1)}, $$

which leads to an explicit formula for $W(x/v, v, 1)$ and hence for $W(x, v, 1)$.

To find $U(x, 1, 1|1)$, we use Lemma 11 to get

$$ (1 - \frac{qx}{w} - \frac{x}{1-w})U(x/w, 1, w|1) = \frac{x}{1-w}(W(x/w, w, 1|1) - wW(x, 1, 1|1)) - \frac{xw}{1-w}U(x, 1, 1|1). $$

By taking $w = v_0(x)$ and using the expressions for $W(x/w, w, 1|1)$ and $W(x, 1, 1|1)$ (from the previous step), we obtain explicit formulas for $U(x, 1, 1|1)$ and $U(x/w, 1, w|1)$. In particular,

$$ 
\begin{aligned}
U(x, 1, 1|1) = & \frac{q(q-1)^4 x^5 - q(q-1)(5q^2 - 3q - 1)x^4 + (10q^3 + 1)x^3 - 2(5q^2 + 4q + 2)x^2 + (5q + 4)x - 1}{2x(1-qx)\sqrt{((q-1)^2x^2 - (2q+1)x + 1)^3}} \\
& + \frac{(q(q-1)^3 x^4 - q^2(4q-3)x^3 + (6q^2 + 3q + 1)x^2 - (4q + 3)x + 1)}{2x(1-qx)((q-1)^2x^2 - (2q+1)x + 1)}.
\end{aligned}
$$

By Theorem 13, we have that the coefficient of $p^1$ in the generating function $\sum_{n \ge 1} t_n x^n$ is given by

$$ U(x, 1, 1|1) + W(x, 1, 1|1). $$

### 3.3.2 Case $m \ge 2$

Let $m \ge 2$ and suppose we have determined the generating functions $W(x, v, 1|m-1)$ and $U(x, 1, w|m-1)$. Now let us describe an algorithm for finding $W(x, v, 1|m)$ and $U(x, 1, w|m)$.

* By Lemma 11, we have $Z(x, v|m) = 0$ and $V(x, 1, w|m) = \frac{qx}{1-qx}U(x, 1, w|m-1)$. Hence, we know $V(x, 1, w|m)$.
• By Lemma 11, and noting $Z(x, v|m-1) = 0$, we have

$$ 
\begin{aligned}
& (1 - qx/v)(1 - \frac{qx}{v} - \frac{x}{1-v})W(x/v, v, 1|m) \\
& = \frac{qx^2}{v(1-v)}(U(x/v, 1, v|m-1) - vU(x, 1, 1|m-1)) \\
& + \frac{qx}{1-v}((1 - qx/v)U(x/v, 1, v|m-1) - (1 - qx)U(x, 1, 1|m-1)) \\
& - \frac{x(1 - qx)}{1 - v}W(x, 1, 1|m).
\end{aligned}
$$

Note that $v = v_0(x)$ is a solution to $1 - \frac{qx}{v} - \frac{x}{1-v} = 0$. Hence, by taking $v = v_0(x)$ and using the prior established results for $W(x, v, 1|m-1)$ and $U(x, 1, w|m-1)$, we obtain an explicit formula for $W(x, 1, 1|m)$, which leads to a formula for $W(x/v, v, 1|m)$ and thus $W(x, v, 1|m)$.

• By Lemma 11, we have

$$ 
\begin{aligned}
& (1 - \frac{qx}{w} - \frac{x}{1-w})U(x/w, 1, w|m) \\
& = \frac{x}{1-w}(W(x/w, w, 1|m) - wW(x, 1, 1|m)) \\
& + \frac{x}{1-w}(V(x/w, 1, w|m) - wU(x, 1, 1|m) - wV(x, 1, 1|m)).
\end{aligned}
$$

By taking $w = v_0(x)$ and using expressions of $W(x, v, 1|m)$ (see second step of the algorithm) and $V(x, 1, w|m)$ (see first step), we obtain $U(x, 1, 1|m)$, which leads to an explicit formula for $U(x, 1, w|m)$.

Hence, by applying the algorithm described above, one can find the generating functions $W(x, v, 1|m)$ and $U(x, 1, w|m)$ from $W(x, v, 1|m-1)$ and $U(x, 1, w|m-1)$. Then the coefficient of $p^m$ in the generating function $\sum_{n \ge 1} t_n x^n$ is given by

$$ U(x, 1, 1|m) + V(x, 1, 1|m) + W(x, 1, 1|m), \quad m \ge 2. $$

# 4 Concluding remarks

In this paper, we have discussed various computational aspects related to the joint distribution of desc and asc on $I_n(\ge, \ne, >)$ as well as of desc and $n-1$-asc on $I_n(> , \ne, \ge)$. As a consequence of our results, we obtained new proofs of (1) and (2) above in a unified way. As a first step in our proofs, we established, by combinatorial arguments, Lemmas 1 and 10, which we then rewrote in terms of generating functions thereby obtaining systems of functional equations. Note that we proceeded in this manner since the recurrences are intertwined and involve intricate relationships between multiple arrays and parameters. We leave it as a challenge for the reader to express the relations between the various generating functions directly using the symbolic enumeration approach described in [5], which appears more difficult to implement in this case than the method presented here in deriving these relations.

Let $A(x, v, w) = A(x, v, w; p, q)$ be given by

$$ A(x, v, w) = B^{+}(x, v, w) + B^{-}(x, v, w) + B_{0}(x, vw) + C^{-}(x, v, w) + C_{0}(x, vw) + \frac{wx}{1 - qwx}, $$
where the B and C functions are defined just prior to Lemma 2. By the definitions, the coefficient of $x^n$ in $A(x, v, w)$ is the joint distribution of the height, last letter, desc and asc statistics on $I_n(\ge, \ne, >)$, marked by $v, w, p$ and $q$, respectively. Note that $A(x, 1, 1)$ coincides with $A(x)$ defined above. Let $B(x, v, w) = B(x, v, w; p, q)$ be given by

$$B(x, v, w) = U(x, v, w) + V(x, v, w) + W(x, v, w) + Z(x, v),$$

where the $U, V, W$ and $Z$ functions are defined just prior to Lemma 11. Note that the coefficient of $x^n$ of $B(x, v, w)$ gives the joint distribution of the following four parameters considered on $I_n(>\ne, \ge)$: (i) leftmost top, (ii) largest letter occurring to right of leftmost top, (iii) desc and (iv) $n-1-\text{asc}$. Here, the leftmost top of an inversion sequence with no descents is defined as its last letter, with parameter (ii) assuming a value of zero in this case.

Then we have the following table of univariate distributions when $n = 6$ obtained by setting all but one of $\{v, w, p, q\}$ equal to unity in $A(x, v, w)$ or $B(x, v, w)$. Note that the only distributions that the A

<table><caption>Tab. 1: Distributions of different statistics on $I_6(\ge, \ne, >)$ and $I_6(>\ne, \ge)$.</caption><thead><tr><th>f(x; q)</th><th>[x<sup>6</sup>](f(x; q))</th></tr></thead><tbody><tr><td>A(x, q, 1; 1, 1)</td><td>102q<sup>5</sup> + 142q<sup>4</sup> + 131q<sup>3</sup> + 88q<sup>2</sup> + 31q + 1</td></tr><tr><td>A(x, 1, q; 1, 1)</td><td>102q<sup>6</sup> + 102q<sup>5</sup> + 102q<sup>4</sup> + 85q<sup>3</sup> + 62q<sup>2</sup> + 42q</td></tr><tr><td>A(x, 1, 1; q, 1)</td><td>77q<sup>2</sup> + 286q + 132</td></tr><tr><td>A(x, 1, 1; 1, q)</td><td>q<sup>5</sup> + 50q<sup>4</sup> + 220q<sup>3</sup> + 188q<sup>2</sup> + 35q + 1</td></tr><tr><td>B(x, q, 1; 1, 1)</td><td>42q<sup>6</sup> + 112q<sup>5</sup> + 123q<sup>4</sup> + 116q<sup>3</sup> + 101q<sup>2</sup> + q</td></tr><tr><td>B(x, 1, q; 1, 1)</td><td>60q<sup>6</sup> + 69q<sup>5</sup> + 67q<sup>4</sup> + 59q<sup>3</sup> + 49q<sup>2</sup> + 59q + 132</td></tr><tr><td>B(x, 1, 1; q, 1)</td><td>51q<sup>2</sup> + 312q + 132</td></tr><tr><td>B(x, 1, 1; 1, q)</td><td>q<sup>5</sup> + 50q<sup>4</sup> + 220q<sup>3</sup> + 188q<sup>2</sup> + 35q + 1</td></tr></tbody></table>

and B groups have in common when $n = 6$ are the respective last ones, with these being equal due to (1). In particular, the descents statistic distribution is different on $I_n(\ge, \ne, >)$ and $I_n(>\ne, \ge)$. Consider replacing $Z(x, v)$ with $Z(x, t)$, where $t \in \{1, w, vw\}$, in the definition of $B(x, v, w)$ above keeping all other terms the same. Such replacements would correspond to different definitions of the leftmost top statistic in the case of a (weakly) increasing inversion sequence. Three other similar tables can be obtained when $n = 6$, using $Z(x, t)$ instead of $Z(x, v)$ as described in the definition of $B(x, v, w)$, and in each case, there is no other commonality between the A and B groups of distributions outside of the one correlating to (1). We thus leave as an open problem the question of finding other equally distributed, naturally defined statistics on $I_n(\ge, \ne, >)$ and $I_n(>\ne, \ge)$ and further, if possible, a generalization of (1) in terms of joint distributions of two or more statistics defined on the respective classes.

## References

[1] G. E. Andrews and S. Chern, A proof of Lin's conjecture on inversion sequences avoiding patterns of relation triples, *J. Combin. Theory Ser. A* **179** (2021), Art. 105388.

[2] W. Cao, E. Y. Jin and Z. Lin, Enumeration of inversion sequences avoiding triples of relations, *Discrete Appl. Math.* **260** (2019), 86–97.
[3] J. N. Chen and Z. Lin, Combinatorics of the symmetries of ascents in restricted inversion sequences, arXiv:2112.04115v1, 2021.

[4] S. Corteel, M. Martinez, C. D. Savage and M. Weselcouch, Patterns in inversion sequences I, *Discrete Math. Theor. Comput. Sci.* **18** (2016), #2.

[5] P. Flajolet and R. Sedgewick, *Analytic Combinatorics*, Cambridge University Press, Cambridge, UK, 2009.

[6] V. Guerrini, On enumeration sequences generalising Catalan and Baxter numbers, Ph.D. Thesis, Università di Siena, 2017.

[7] Q. Hou and T. Mansour, Kernel method and linear recurrence system, *J. Comput. Appl. Math.* **216**(1) (2008), 227-242.

[8] D. Kim and Z. Lin, Refined restricted inversion sequences, *Sémin. Lothar. Comb.* **78B** (2017), 52.

[9] S. Kitaev, *Patterns in Permutations and Words*, Springer-Verlag, Berlin, 2011.

[10] Z. Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, *European J. Combin.* **70** (2018), 202–211.

[11] Z. Lin, Patterns of relation triples in inversion and ascent sequences, *Theoret. Comput. Sci.* **804** (2020), 115–125.

[12] Z. Lin and S. H. F. Yan, Vincular patterns in inversion sequences, *Appl. Math. Comput.* **364** (2020), Art. 124672.

[13] T. Mansour and M. Shattuck, Pattern avoidance in inversion sequences, *Pure Math. Appl. (PU.M.A.)* **25** (2015), 157–176.

[14] T. Mansour and M. Shattuck, On a conjecture of Lin and Kim concerning a refinement of Schröder numbers, arXiv:2104.04491v1, 2021.

[15] M. A. Martinez and C. D. Savage, Patterns in inversion sequences II: Inversion sequences avoiding triples of relations, *J. Integer Seq.* **21** (2018), Art. 18.2.2.

[16] N. J. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org, 2010.

[17] C. Yan and Z. Lin, Inversion sequences avoiding pairs of patterns, *Discrete Math. Theor. Comput. Sci.* **22**(1) (2020), Art. 23.

[18] S. H. F. Yan, Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions, *Appl. Math. Comput.* **325** (2018), 24–30.