Refined Wilf-equivalences by Comtet statistics

1.   Introduction

Let $[n]: = \{1, 2, \ldots, n\}$ be the set of the first $n$ positive integers, and denote ${\mathfrak{S}}_n$ the symmetric group consisting of all bijections from $[n]$ to itself. A permutation $\pi = \pi(1)\cdots\pi(n)\in{\mathfrak{S}}_n$ is said to avoid the permutation (or pattern) $\sigma = \sigma(1)\cdots \sigma(k)\in{\mathfrak{S}}_k$, $k\le n$, if and only if there is no subsequence $\pi(j_1)\pi(j_2)\cdots\pi(j_k)$ with $j_1<j_2<\cdots<j_k$, such that $\pi(j_a)<\pi(j_b)$ if and only if $\sigma(a)<\sigma(b)$ for all $1\le a<b\le k$. Otherwise, we say that the permutation $\pi$ contains the pattern $\sigma$.

The notion of permutation pattern was introduced by Knuth [21,pp. 242-243] in 1968, but studied intensively and systematically for the first time by Simion and Schmidt [28] in 1985. Ever since then, it has become an active and prosperous research subject. The reader is referred to two book expositions, [5,Chapters 4 and 5] and [20], on this topic, as well as the numerous references therein. In the early 1980s, Herbert Wilf posed the problem of identifying equirestrictive sets of forbidden patterns. Let $P$ be a (finite) collection of patterns and $\mathcal{W}$ a set of permutations, we write $\mathcal{W}(P)$ for the set of all permutations in $\mathcal{W}$ that avoid simultaneously every pattern contained in $P$. We will say, as it has become a standard terminology, that two sets of patterns, $P$ and $Q$, are Wilf-equivalent, denoted by $P\sim Q$, if $|{\mathfrak{S}}_n(P)| = |{\mathfrak{S}}_n(Q)|$ for all positive integers $n$.

In this paper, we will restrict ourselves to the case where $|P| = |Q|\le 2$, and the lengths of the patterns in $P$ and $Q$ are no greater than $4$. Once two sets of patterns $P$ and $Q$ are known to be Wilf-equivalent, a natural direction to go deeper, is to make further restrictions on these $P$- or $Q$-avoiding permutations, and to see if the equinumerosity still holds. One such restriction is to consider the enumeration refined by various permutation statistics. In general, a statistic on a set of objects $S$ is simply a function from $S$ to $\mathbb{N}: = \{0, 1, 2, \ldots\}$. A set-valued statistic on $S$ is a function from $S$ to the set of finite subsets of $\mathbb{N}$. Given a permutation $\pi\in{\mathfrak{S}}_n$, we mainly consider the set-valued statistic

called the descent set of $\pi$, and two statistics

called the ${\boldsymbol des}$cent number and the ${\boldsymbol i}$nitial ${\boldsymbol a}$scending ${\boldsymbol r}$un of $\pi$, respectively. Clearly, ${\mathsf{iar}}(\pi)$ can also be interpreted as the position of the leftmost descent of $\pi$, which indicates that ${\mathsf{iar}}$ is determined by ${\mathrm{DES}}$. It should be noted that ${\mathsf{iar}}$ was also called ${\mathsf{lir}}$, meaning "leftmost increasing run", in the literature (see e.g. [7]). The statistic ${\mathsf{des}}$ is known as an Eulerian statistic since its distribution over ${\mathfrak{S}}_n$ is the $n$-th Eulerian polynomial

Another statistic highlighted in our study is ${\mathsf{comp}}(\pi)$, which can be introduced as

It is equal to the maximum number of components (see [1,7,8]) in an expression of $\pi$ as a direct sum of permutations. For instance, ${\mathsf{comp}}(312465) = 3$, the three components being $312$, $4$, and $65$ and $312465 = 312\oplus1\oplus 21$ (see Sect. 2.2 for the definition of direct sum $\oplus$). The statistic ${\mathsf{comp}}$ dates back at least to Comtet [9,Ex. VI.14], who proved the generating function for the number $f(n)$ of permutations of length $n$ with one component, also known as indecomposable permutations, to be

Thus, any statistic equidistributed with ${\mathsf{comp}}$ over a class of restricted permutations will be called by us a Comtet statistic over such class. The enumeration of pattern avoiding indecomposable permutations was carried out by Gao, Kitaev and Zhang [19]. It should be noted that ${\mathsf{iar}}$ and ${\mathsf{comp}}$ are not equidistributed over ${\mathfrak{S}}_4$. Nonetheless, two of the authors [18] proved that ${\mathsf{iar}}$ is a Comtet statistic over separable permutations, the class of $(2413, 3142)$-avoiding permutations. It is this result that motivates us to investigate systematically the refined Wilf-equivalences by these two Comtet statistics, and sometimes jointly with other statistics.

For a (possibly set-valued) statistic ${\mathsf{st}}$ on ${\mathfrak{S}}_n$, we say two sets of patterns $P$ and $Q$ are ${\mathsf{st}}$-Wilf-equivalent, denoted as $P\sim_{{\mathsf{st}}}Q$, if for all positive integers $n$, we have

meaning that for a fixed value of ${\mathsf{st}}$, there are as many preimages in ${\mathfrak{S}}_n(P)$ as those in ${\mathfrak{S}}_n(Q)$. Note that by their definitions, $P\sim_{{\mathrm{DES}}}Q$ immediately implies $P\sim_{{\mathsf{iar}}}Q$ and $P\sim_{{\mathsf{des}}}Q$, but not conversely. The above refined Wilf-equivalence by one statistic can be naturally extended to the joint distribution of several permutation statistics, regardless of numerical or set-valued types. So expression like $P\sim_{({\mathrm{DES}}, {\mathsf{comp}})}Q$ and $|{\mathfrak{S}}_n(P)^{{\mathrm{DES}}, {\mathsf{comp}}}| = |{\mathfrak{S}}_n(Q)^{{\mathrm{DES}}, {\mathsf{comp}}}|$ should be understood well. It should be noted that refined Wilf-equivalences have already been extensively studied during the last two decades (see e.g. [7,11,13,20,24]). Especially, the focus of Dokos, Dwyer, Johnson, Sagan and Selsor [11] was on the refined Wilf-equivalences by Eulerian and Mahonian statistics. Hopefully with the results we present in this paper, one is convinced that considering the refinements by Comtet statistics is equally meaningful.

Some highlights of our results will be outlined below. Before stating them, we need to recall some classical permutation statistics. For a permutation $\pi\in{\mathfrak{S}}_n$, we introduce

the set of values and positions of the left-to-right maxima of $\pi$, respectively. The sets of values/positions of the left-to-right minima, the right-to-left maxima and the right-to-left minima of $\pi$ can be defined and denoted similarly if needed. We use lowercase letters to denote the cardinality of these sets, so for example, ${\mathrm{LMIN}}(\pi)$ is the set of values of the left-to-right minima of $\pi$ and ${\mathsf{lmin}}(\pi)$ is the corresponding numerical statistic. We will also consider the set of descent bottoms of $\pi$

which is another set-valued extension of ${\mathsf{des}}$ different from ${\mathrm{DES}}$.

The first one of our main results concerns a single pattern of length $3$.

Theorem 1.1. For every $n\ge 1$,

(i) the two triples $({\mathrm{LMAX}}, {\mathsf{iar}}, {\mathsf{comp}})$ and $({\mathrm{LMAX}}, {\mathsf{comp}}, {\mathsf{iar}})$ have the same distribution over ${\mathfrak{S}}_n(321)$;

(ii) the two quadruples $({\mathrm{LMAX}}, {\mathrm{DESB}}, {\mathsf{iar}}, {\mathsf{comp}})$ and $({\mathrm{LMAX}}, {\mathrm{DESB}}, {\mathsf{comp}}, {\mathsf{iar}})$ have the same distribution over ${\mathfrak{S}}_n(312)$;

(iii) the quadruples $({\mathrm{LMAX}}, {\mathrm{LMIN}}, {\mathsf{iar}}, {\mathsf{comp}})$ and $({\mathrm{LMAX}}, {\mathrm{LMIN}}, {\mathsf{comp}}, {\mathsf{iar}})$ have the same distribution over ${\mathfrak{S}}_n(132)$.

The result on the symmetry of $({\mathsf{comp}}, {\mathsf{iar}})$ was inspired by several works in the literature. First of all, Theorem 1.1 (i) is essentially equivalent to a result of Rubey [27] up to some elementary transformations on permutations. Details will be given in Sect. 3.1. Furthermore, Rubey's result is a symmetric generalization of an equidistribution due to Adin, Bagno and Roichman [1], which implies the Schur-positivity of the class of $321$-avoiding permutations with a prescribed number of components.

Next, Claesson, Kitaev and Steingrímsson [20,Thm 2.2.48] constructed a bijection between separable permutations of length $n+1$ with $k+1$ components and Schröder paths of order $n$ with $k$ horizontals at $x$-axis. Combining this bijection with the work in [18] justifies ${\mathsf{iar}}$ being a Comtet statistic on separable permutations. It then follows from our Lemma 2.5, a general lemma proved in Sect. 2.2, that we have the following symmetric double Comtet distribution.

Corollary 1.2. The double Comtet statistics $({\mathsf{comp}}, {\mathsf{iar}})$ is symmetric on separable permutations.

We take the opportunity to announce the following refinement of Corollary 1.2, which appears in a separate article.

Theorem 1.3 ([16]). There exists an involution on ${\mathfrak{S}}_n(2413, 3142)$ that preserves the pair of set-valued statistics $({\mathrm{LMAX}}, {\mathrm{DESB}})$ but exchanges the pair $({\mathsf{comp}}, {\mathsf{iar}})$. Consequently,

where ${\bf x}^S: = \prod_{i\in S}x_i$ and ${\bf y}^S: = \prod_{i\in S}y_i$ for any subset $S\subseteq[n]$.

The proof of Theorem 1.1 provided in Sect. 3 is via two involutions on permutations that actually imply the even stronger symmetric phenomenon, namely the corresponding distribution matrices are Hankel; see Theorems 3.13 and 4.2. The proof of Theorem 1.3 is based on a combinatorial bijection on the so-called di-sk trees introduced in [17]. This bijection will also provide an alternative approach to Theorem 1.1(ii). The details will be given in [16].

Remark 1. Rubey's bijective proof of a slight modification (see Theorem 3.1) of Theorem 1.1(i) is via Dyck paths and the proof of Theorem 1.3 that will appear in [16] is based on di-sk trees. Our bijective and unified proof of Theorem 1.1(i)(ii), constructed directly on permutations, provides more insights into the symmetry of the double Comtet statistics, and therefore, it seems more likely to be extended to deal with such equidistributions over other classes of pattern-avoiding permutations.

Our third main result shows how ${\mathsf{iar}}$, combined with ${\mathsf{des}}$ and the number of double descents would refine known results and imply new ones concerning separable and $(2413, 4213)$-avoiding permutations. Interestingly, it does refine a nice $\gamma$-positivity interpretation for separable permutations [17,23] due to Zeng and the first two authors that we review below.

Recall that a polynomial in $\mathbb{R}[t]$ of degree $n$ is said to be $\gamma$-positive if it can be written as a linear combination of

with non-negative coefficients. Many polynomials arising from combinatorics and discrete geometry have been shown to be $\gamma$-positive; see the comprehensive survey by Athanasiadis [2]. One typical example is the Eulerian polynomials

where $\Gamma_{n, k}$ is the set of permutations in ${\mathfrak{S}}_n$ with $k$ descents and without double descents. Here an index $i\in[n]$ is called a double descent of a permutation $\pi\in{\mathfrak{S}}_n$ if $\pi(i-1)>\pi(i)>\pi(i+1)$, where we use the convention $\pi(0) = \pi(n+1) = 0$. The number of double descents of $\pi$ will be denoted as ${\mathsf{dd}}(\pi)$. This classical result is due to Foata and Schützenberger [14,Theorem 5.6] and has been extended in several different directions (cf. [2]) in recent years. In particular, the first two authors together with Zeng [17,23] proved an analog for the descent polynomial over separable permutations

In a recent work [24] of Lin and Kim, they proved that $(2413, 3142)\sim_{{\mathsf{des}}}(2413, 4213)$ (see [24,Thm. 5.1]), and that the $\gamma$-coefficient of the descent polynomial over $(2413, 4213)$-avoiding permutations is similarly given by $|\Gamma_{n, k}(2413, 4213)|$ (see [24,Eq. (4.10)]). In view of (1), we see that the number of separable permutations of $[n]$ with $k$ descents and without double descents is the same as that of $(2413, 4213)$-avoiding permutations of $[n]$ with $k$ descents and without double descents. With this in mind, our third main result given below can be viewed as a refinement.

Theorem 1.4. For $n\geq1$,

Theorem 1.4 refines Wang's equidistribution [30,Thm. 1.5] by the Comtet statistic ${\mathsf{iar}}$ and has many interesting consequences which can be found in Sections 5 and 6. More detailed motivation that led us to discover Theorem 1.4 will also be provided in Section 6. Our proof of Theorem 1.4 in Section 6 is algebraic and finding a bijective proof remains open.

Besides the above three main results, we will also calculate the joint distribution of $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$ over permutations avoiding a set $P$ of patterns, where $P$ is taken to be a single pattern of length $3$, a pair of patterns of length $3$, as well as the three pairs $(2413, 3142)$, $(2413, 4213)$, and $(3412, 4312)$, respectively. All the generating functions for these patterns turn out to be either algebraic or rational (see Tables 1 and 2), and as applications, complete classification of the ${\mathsf{iar}}$- or ${\mathsf{comp}}$-Wilf equivalences for these patterns is given. Moreover, our attempt to characterize the pattern pairs of length $4$ which are $({\mathsf{iar}}, {\mathsf{comp}})$-Wilf-equivalent to $(2413, 3142)$ leads to Conjecture 1, which we have verified in some important cases.

The rest of this paper is organized as follows. In Section 2, we review some notation and terminology and prove two general lemmas concerning the direct sum operation of permutations. The classification of refined Wilf-equivalences for a single pattern of length $3$ is carried out in Section 3, where the proof of Theorem 1.1 is provided as well. Section 4 is devoted to the investigation of pattern pairs of length $3$, while Section 5 aims to characterize the pattern pairs of length $4$ that are $({\mathsf{iar}}, {\mathsf{comp}})$-Wilf-equivalent to $(2413, 3142)$. The proof of Theorem 1.4 is given in Section 6, where a new recurrence for the $021$-avoiding inversion sequences is also proved.

2.   Notations and preliminaries

2.1.   Elementary operations

For a given permutation $\pi\in{\mathfrak{S}}_n$, there are three fundamental symmetry operations on $\pi$:

● its reversal $\pi^{\mathrm{r}}\in{\mathfrak{S}}_n$ is given by $\pi^{\mathrm{r}}(i) = \pi(n+1-i)$;

● its complement $\pi^{\mathrm{c}}\in{\mathfrak{S}}_n$ is given by $\pi^{\mathrm{c}}(i) = n+1-\pi(i)$;

● its inverse $\pi^{-1}\in{\mathfrak{S}}_n$, is the usual group theoretic inverse permutation.

One thing we would like to point out, before we barge into classifying ${\mathsf{iar}}$-Wilf-equivalences for various patterns, is that by taking ${\mathsf{iar}}$ into consideration, we can no longer utilize the above three standard symmetries for permutations, since none of them preserves the length of the initial ascending run of $\pi$, when $n\ge 2$. For the classical Wilf-equivalence, these symmetries reduce the number of possible equivalence classes considerably, since for example, $\pi$ avoids $213$ if and only if $\pi^{\mathrm{r}}$ avoids $312$. This fact about the statistic ${\mathsf{iar}}$ explains, at least partially, the following observations.

Observation 1. $1.$ The ${\mathsf{iar}}$-Wilf-equivalence is less likely to be found than the Wilf-equivalence.

$2.$ When ${\mathsf{iar}}$-Wilf-equivalence does hold, we cannot prove it using the three standard symmetries or their combinations. Usually we need to use new ideas in constructing bijective proofs, or prove the equivalence recursively using recurrence relations.

On the other hand, the statistic ${\mathsf{comp}}$ behaves better under these three elementary operations.

Observation 2. The two mappings $\pi\mapsto (\pi^r)^c$ and $\pi\mapsto \pi^{-1}$ both preserve the statistic ${\mathsf{comp}}$.

Let $P$ be a collection of patterns. The following trivariate generating function will be the focal point of our study.

Most of the time we suppress the superindices ${\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}$, and variable $z$, and when the pattern set $P$ is clear from the context, we also suppress $P$ to write ${\mathfrak{S}}(t, r, p)$. In most cases the variant $\tilde{\mathfrak{S}}(t, r, p): = ({\mathfrak{S}}(t, r, p)-1)/rpz$ of this generating function yields more compact expressions (see Tables 1 and 2). Let $M_n(P): = M_n(P;{\mathsf{iar}}, {\mathsf{comp}})$ be the $n\times n$ matrix, whose entry at the $k$-th row and the $\ell$-th column is the number of permutations $\pi$ in ${\mathfrak{S}}_n(P)$ with ${\mathsf{iar}}(\pi) = k$ and ${\mathsf{comp}}(\pi) = \ell$. Let ${\mathsf{st}}$ be a permutation statistic, we can then refine $M_n(P)$ as $M_n(P) = \sum_{i}M_n^{{\mathsf{st}} = i}(P)$, so that the $(k, \ell)$-entry of $M_n^{{\mathsf{st}} = i}(P)$ counts permutations $\pi$ such that ${\mathsf{st}}(\pi) = i$ for a fixed integer $i$. This definition extends to set-valued statistics and multiple statistics in a natural way. So for instance, $M_n^{{\mathrm{LMAX}} = S, {\mathsf{des}} = i}(P)$ is the $n\times n$ matrix, whose $(k, \ell)$-entry is the number of permutations $\pi$ in ${\mathfrak{S}}_n(P)$ with ${\mathrm{LMAX}}(\pi) = S$, ${\mathsf{des}}(\pi) = i$, ${\mathsf{iar}}(\pi) = k$ and ${\mathsf{comp}}(\pi) = \ell$.

We also need the following operations on permutations.

Definition 2.1. For a word $w$ over $\mathbb{Z}$ consisting of distinct letters, denote $red(w)$ the reduction of $w$ (also called the "standardization" of $w$ in the literature), which is obtained from $w$ by replacing the $j$-th smallest positive letter by $j$. For a given permutation $\pi\in{\mathfrak{S}}_n$, the deletion of $i$, for each $i\in[n]$, is the map that deletes $i$ from $\pi$, and reduces the derived word to a permutation, denoted as ${\operatorname{del}}_i(\pi)\in{\mathfrak{S}}_{n-1}$. Similarly, the insertion of $i$ at place $k$, for each $i, k\in [n+1]$, is defined to be the map that increases all letters $j\ge i$ in $\pi$ by $1$, and inserts $i$ between $\pi(k-1)$ and $\pi(k)$ to get a new permutation, denoted as ${\operatorname{ins}}_{i, k}(\pi)\in{\mathfrak{S}}_{n+1}$.

2.2.   The direct/skew sum operation and fundamental lemmas

There are two fundamental operations, called direct sum and skew sum, to construct a bigger permutation from two smaller ones. The direct sum $\pi\oplus\sigma$ and the skew sum $\pi\ominus\sigma$, of $\pi\in{\mathfrak{S}}_k$ and $\sigma\in{\mathfrak{S}}_l$, are permutations in ${\mathfrak{S}}_{k+l}$ defined respectively as

and

For instance, we have $123\oplus 21 = 12354$ and $123\ominus 21 = 34521$. The following characterization of separable permutations is folkloric (see [20,pp. 57]) in pattern avoidance.

Proposition 2.2. A permutation is separable if and only if it can be built from the permutation $1$ by applying the operations $\oplus$ and $\ominus$ repeatedly.

Definition 2.3. A nonempty permutation which is not the direct sum of two nonempty permutations is called indecomposable. Let $\mathcal{I}_n$ denote the set of all indecomposable permutations of length $n$. Any permutation $\pi$ with ${\mathsf{comp}}(\pi) = k$ can be written uniquely as $\pi = \tau_1\oplus\tau_2\oplus\cdots\oplus\tau_k$, where each $\tau_i$ is indecomposable. We call this decomposition the direct sum decomposition of $\pi$. Let ${\mathrm{id}}_n$ denote the identity permutation of length $n$. A statistic ${\mathsf{st}}$ is called totally $\oplus$-compatible if ${\mathsf{st}}(\pi) = \sum_{i = 1}^k{\mathsf{st}}(\tau_i)$ and is called partially $\oplus$-compatible if ${\mathsf{st}}(\pi) = \sum_{i = 1}^l{\mathsf{st}}(\tau_i)$, where $l = \min(\{i:\tau_i\neq {\mathrm{id}}_1\}\cup\{k\})$.

For instance, ${\mathsf{des}}$ and ${\mathsf{comp}}$ are totally $\oplus$-compatible, while ${\mathsf{iar}}$ is partially $\oplus$-compatible. We emphasize here that total $\oplus$-compatibility does not imply partial $\oplus$-compatibility.

Let $P$ be a collection of patterns and $({\mathsf{st}}_1, {\mathsf{st}}_2, \ldots)$ be a sequence of permutation statistics. Let us introduce two generating functions with respect to $({\mathsf{st}}_1, {\mathsf{st}}_2, \ldots)$ as

and

We have the following general lemma regarding the direct sum decomposition of permutations, which is useful when considering the refinement of Wilf-equivalence by ${\mathsf{comp}}$.

Lemma 2.4. Let $({\mathsf{st}}_1, {\mathsf{st}}_2, \ldots, {\mathsf{st}}'_1, {\mathsf{st}}'_2, \ldots)$ be a sequence of statistics such that ${\mathsf{st}}_i$ is totally $\oplus$-compatible and ${\mathsf{st}}'_i$ is partially $\oplus$-compatible for each $i$. Let $P$ and $Q$ be two collections of indecomposable patterns.

1. We have the following functional equation:

where $w = zt_1^{{\mathsf{st}}_1({\mathrm{id}}_1)}t_2^{{\mathsf{st}}_2({\mathrm{id}}_1)}\cdots {t'_1}^{{\mathsf{st}}'_1({\mathrm{id}}_1)}{t'_2}^{{\mathsf{st}}'_2({\mathrm{id}}_1)}\cdots$ is the generating function for ${\mathrm{id}}_1$, and

are the generating functions with respect to $({\mathsf{comp}}, {\mathsf{st}}_1, \ldots, {\mathsf{st}}'_1, \ldots)$ and $({\mathsf{st}}_1, \ldots, {\mathsf{st}}'_1, \ldots)$, respectively. In particular, $I_P({\bf t}, {\bf 1}): = I_P(t_1, \ldots, 1, \ldots;z)$.

2. If $P\sim_{({\mathsf{st}}_1, {\mathsf{st}}_2, \ldots, {\mathsf{st}}'_1, {\mathsf{st}}'_2, \ldots)}Q$, then $P\sim_{({\mathsf{comp}}, {\mathsf{st}}_1, {\mathsf{st}}_2, \ldots, {\mathsf{st}}'_1, {\mathsf{st}}'_2, \ldots)}Q$ holds as well. In particular, if $P\sim Q$, then $P\sim_{{\mathsf{comp}}} Q$.

Proof. Note that if $\sigma$ is an indecomposable pattern and $\pi = \tau_1\oplus\tau_2\oplus\cdots\oplus\tau_k$, then

Therefore, with respect to totally $\oplus$-compatible statistics t, the weight of $\pi$ that contributes to the generating function $F_P(q)$ is the product of the weights of $\tau_1, \ldots, \tau_k$. But when partially $\oplus$-compatible statistics ${\bf t'}$ are involved, further analysis is needed. Among these $k$ indecomposable components, suppose the first $i$ are trivial (i.e., ${\mathrm{id}}_1$) with weight $w$, the $(i+1)$-th component is nontrivial thus generated by $I_P({\bf t}, {\bf t'})-w$, and the remaining $k-i-1$ components do not affect those partially $\oplus$-compatible statistics ${\bf t'}$, thus each is generated by $I_P({\bf t}, {\bf 1})$. The discussion above amounts to

which becomes 4 after simplification.

In view of 4, the following three statements are equivalent:

(i) $F_P(1) = F_Q(1)$, namely $P\sim_{({\mathsf{st}}_1, {\mathsf{st}}_2, \ldots, {\mathsf{st}}'_1, {\mathsf{st}}'_2, \ldots)}Q$.

(ii) $I_P({\bf t}, {\bf t'}) = I_Q({\bf t}, {\bf t'})$.

(iii) $F_P(q) = F_Q(q)$.

For example, to see that (i) implies (ii), we first set $t_i' = 1$ for all $i$ to obtain that $F_P(1) = F_Q(1)$ implies $I_P({\bf t}, {\bf 1}) = I_Q({\bf t}, {\bf 1})$, which in turn implies (ii) via 4. Thus, statement (i) is equivalent to its seemingly stronger form (iii), as desired.

The following general lemma indicates that for a collection of indecomposable patterns, say $P$, the equidistribution of certain statistic ${\mathsf{st}}$ with ${\mathsf{comp}}$ over ${\mathfrak{S}}_n(P)$, implies the seemingly stronger result that the joint distribution $({\mathsf{st}}, {\mathsf{comp}})$ is symmetric over ${\mathfrak{S}}_n(P)$. This result is somewhat surprising.

Lemma 2.5. Let $P$ be a collection of indecomposable patterns. Let ${\mathsf{st}}'$ be a partially $\oplus$-compatible statistic such that ${\mathsf{st}}'({\mathrm{id}}_1) = 1$ and $({\mathsf{st}}_1, {\mathsf{st}}_2, \ldots)$ be a sequence of totally $\oplus$-compatible statistics. If $|{\mathfrak{S}}_n(P)^{{\mathsf{st}}', {\mathsf{st}}_1, {\mathsf{st}}_2, \ldots}| = |{\mathfrak{S}}_n(P)^{{\mathsf{comp}}, {\mathsf{st}}_1, {\mathsf{st}}_2, \ldots}|$, then

In particular, if ${\mathsf{st}}'$ is a Comtet statistic over ${\mathfrak{S}}_n(P)$, then $({\mathsf{st}}', {\mathsf{comp}})$ is a symmetric pair of Comtet statistics over ${\mathfrak{S}}_n(P)$.

Proof. Let $F_P(r, s): = F_P(r, s, t_1, t_2, \ldots;z)$ and $I_P(s): = I_P(s, t_1, t_2, \ldots;z)$ be the generating functions with respect to $({\mathsf{comp}}, {\mathsf{st}}', {\mathsf{st}}_1, {\mathsf{st}}_2, \ldots)$ and $({\mathsf{st}}', {\mathsf{st}}_1, {\mathsf{st}}_2, \ldots)$, respectively. By the relationship 4, we have

where $w = zt_1^{{\mathsf{st}}_1({\mathrm{id}}_1)}t_2^{{\mathsf{st}}_2({\mathrm{id}}_1)}\cdots$. Since $F_P(1, s) = F_P(s, 1)$, it follows from the above identity that

Solving this equation gives

Plugging this into 5 results in

which is symmetric in $r$ and $s$. This completes the proof of the lemma.

3.   A single pattern of length 3

In this section, we deal with all patterns $\tau$ of length $3$ and complete two tasks:

$1)$ Show the symmetry of the Comtet pair $({\mathsf{iar}}, {\mathsf{comp}})$, jointly with some other (set-valued) statistics, over certain class of pattern-avoiding permutations or admissible words (see Theorem 3.6). In all cases the proofs are combinatorial. We collect all the bijections here for easy reference: $\xi$ (Theorem 3.2), $\alpha$ and $\beta$ (Theorem 3.4), $\psi$ (Theorem 3.6), $\varphi$ (Theorem 3.12), and $\theta$ (Theorem 3.14).

$2)$ Compute the trivariate generating function ${\mathfrak{S}}(\tau)^{{\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}}(t, r, p)$, which leads to the full ${\mathsf{iar}}$- and ${\mathsf{comp}}$-Wilf-equivalence classification. A snapshot of these results is presented in Table 1, where $M^T$ stands for the transpose of the matrix $M$. Putting $t = 1$, and $p = 1$ (or $r = 1$) in the generating functions listed in Table 1 and comparing the results, we can conclude that there are three ${\mathsf{iar}}$-Wilf-equivalence classes:

While the ${\mathsf{comp}}$-Wilf-equivalence classes are:

3.1.   Symmetric classes

For the three patterns $312$, $321$ and $132$, the distributions of ${\mathsf{iar}}$ and ${\mathsf{comp}}$ are not only identical, but also jointly symmetric. For the two indecomposable patterns $312$ and $321$, this stronger property can be deduced from Lemma 2.5. But for the pattern $132 = 1\oplus 21$, we need to construct an involution $\varphi$ on ${\mathfrak{S}}_n(132)$, which actually enables us to derive a more refined equidistribution (see Theorem 3.12). We begin with the patterns $321$ and $312$.

Patterns $312$ and $321$

The pattern $321$ seems to attract more attention than the other patterns in ${\mathfrak{S}}_3$, perhaps because of its role in Deodhar's combinatorial framework for determining the Kazhdan-Lusztig polynomials (see for instance [4]). Rubey [27] obtained an equidistribution result over ${\mathfrak{S}}_n(321)$ by first mapping each $321$-avoiding permutation, along with the statistics involved, to a Dyck path via Krattenthaler's bijection [22], and then constructing an involution on Dyck paths. We restate his result here using $321$-avoiding permutations rather than Dyck paths. For each $\pi\in{\mathfrak{S}}_n$, let

be the position of the ${\boldsymbol l}$ast ${\boldsymbol des}$cent of $\pi$. Recall the boldface notation ${\bf x}^S$ defined in Theorem 1.3.

Theorem 3.1 (Rubey [27]). There exists an involution on ${\mathfrak{S}}_n(321)$ which proves the equidistribution

We explain here why Theorem 3.1 is equivalent to our Theorem 1.1 (i) up to the elementary transformation $\pi\mapsto (\pi^{-1})^{\mathrm{rc}}$. Notice that for each $\pi\in{\mathfrak{S}}_n$, we have the relationships

where $\bar{S}: = \{n+1-i: i\in S\}$ for any subset $S\subseteq[n]$. In view of these relationships and Observation 2, we have

Therefore, equidistribution (7) is equivalent to Theorem 1.1 (i).

In Corollary 3.7 we present a bijection, say $\omega$, on ${\mathfrak{S}}_n(321)$ that proves Theorem 1.1 (i) directly. On the other hand, as we have explained above, when Rubey's bijection that proves (7) is composed with the map $\pi\mapsto(\pi^{-1})^{\mathrm{rc}}$, we obtain another bijection on ${\mathfrak{S}}_n(321)$, say $\tilde{\omega}$, that yields Theorem 1.1 (i) as well. Interestingly, these two bijections $\omega$ and $\tilde{\omega}$ turn out to be different from each other, although they do agree for permutations in ${\mathfrak{S}}_n(321)$ when $n\le 5$. The reader can check the following example once he or she is familiar with both bijections.

In view of Lemma 2.4 (2), $321\sim_{{\mathsf{comp}}}312$ since $321\sim 312$. We have the following refinement.

Theorem 3.2. For each $n\ge 1$, there exists a bijection $\xi$, mapping each $\pi\in{\mathfrak{S}}_n(321)$ onto $\sigma: = \xi(\pi)\in{\mathfrak{S}}_n(312)$, such that

Sitting in the heart of our proof of Theorem 3.2, is a certain word composed of positive integers and a symbol $\diamond$ that stands for an empty slot, which we introduce now.

Definition 3.3. Given a nonempty set $S = \{s_1, \ldots, s_k\}\subseteq \mathbb{Z}_{>0}$ with $s_1<\cdots<s_k$, and a weak composition $c = (c_1, \ldots, c_k)$ of $s_k-k$, we form the word

It is said to be an admissible word with respect to $S$ and $c$, if for $1\le i \le k$,

Let ${\mathcal{AW}}_n$ denote the set of all admissible words of length $n$.

We also need to introduce the counterparts on ${\mathcal{AW}}_n$ of the quadruple statistics in (8). For each $w: = w_{S, c}\in{\mathcal{AW}}_n$, let ${\mathsf{ics}}(w)$ denote the number of ${\boldsymbol i}$nitial ${\boldsymbol c}$onsecutive letters from $S$ in $w$, ${\mathsf{equ}}(w)$ denote the number of times the condition (*) is satisfied with an ${\boldsymbol equ}$al sign, and ${\mathrm{SP}}(w)$ denote the set of positions (in $w$) of letters from $S$. For example, if $w = 2\:3\:5\diamond7\diamond \diamond 10\:12\diamond 13\diamond\diamond$ with $S = \{2, 3, 5, 7, 10, 12, 13\}$, then ${\mathsf{ics}}(w) = 3$, ${\mathsf{equ}}(w) = 2$, ${\mathrm{SP}}(w) = \{1, 2, 3, 5, 8, 9, 11\}$.

Theorem 3.4. There exist two bijections $\alpha:{\mathfrak{S}}_n(321)\rightarrow {\mathcal{AW}}_n$ and $\beta:{\mathfrak{S}}_n(312)\rightarrow {\mathcal{AW}}_n$, such that for any $\pi\in{\mathfrak{S}}_n(321)$ and $\sigma\in{\mathfrak{S}}_n(312)$, we have

where $w_{S, c} = \alpha(\pi)$ and $w_{T, d} = \beta(\sigma)$.

Proof. Since the constructions for the two bijections $\alpha$ and $\beta$ are almost the same (the only difference lies in their inverses), we will give details mainly for $\alpha$. For each $\pi\in{\mathfrak{S}}_n(321)$, suppose

Let $c = (c_1, \ldots, c_k)$, with $c_h = i_{h+1}-i_h-1$, for $1\le h\le k-1$, $c_k = n-i_k$. In other words, each part of the composition $c$ records the number of letters between two left-to-right maxima, after having appended $n+1$ to the permutation $\pi$. Now we define $\alpha(\pi): = w_{S, c}.$ Note that $\pi(i_1), \ldots, \pi(i_k)$ are the left-to-right maxima of $\pi$, so we can verify the condition (*) holds for $S$ and $c$, therefore $\alpha$ is a well-defined map from ${\mathfrak{S}}_n(321)$ to ${\mathcal{AW}}_n$. The map $\beta$ is defined analogously, only that now the preimage is a $312$-avoiding, rather than $321$-avoiding permutation. Now we show both $\alpha$ and $\beta$ are bijections by constructing their inverses. Take a word $w_{S, c}\in{\mathcal{AW}}_n$, we replace all the $\diamond$'s from left to right with the smallest unused letter in $[n]\setminus S$. This results in a $321$-avoiding permutation, say $\hat{\pi}$. On the other hand, if we replace all the $\diamond$'s from left to right with the largest unused letter in $[n]\setminus S$, keeping letters from $S$ the left-to-right maxima, we will end up with a $312$-avoiding permutation, say $\hat{\sigma}$.

It should be clear that

Now set $\alpha^{-1}(w_{S, c}) = \hat\pi$ (resp. $\beta^{-1}(w_{S, c}) = \hat\sigma$). Evidently,

so $\alpha$ and $\beta$ are indeed bijections that transform the quadruple statistics as shown in (9) and (10).

Proof of Theorem 3.2. Simply set $\xi = \beta^{-1}\circ \alpha$, and (8) follows immediately from (9) and (10).

Remark 2. When composed with the complement map, our bijection $\xi$ is equivalent to Simion and Schmidt's [28] bijection from ${\mathfrak{S}}_n(123)$ to ${\mathfrak{S}}_n(132)$. This bijection is also called the Knuth–Richards bijection by Claesson and Kitaev [7], see also [12].

In view of (9), the pair $({\mathsf{ics}}, {\mathsf{equ}})$ on admissible words corresponds to the pair $({\mathsf{iar}}, {\mathsf{comp}})$ on $321$-avoiding permutations, so Rubey's Theorem 3.1 tells us that their distributions are jointly symmetric over ${\mathcal{AW}}_n$. Note that Rubey's proof was via an involution on Dyck paths. We are able to construct an invertible map $\psi$ over the set of admissible words. To facilitate the description of $\psi$, we need the following definition.

Definition 3.5. Given an admissible word $w_{S, c}$ with $S = \{s_1, \ldots, s_k\}$ and $c = (c_1, \ldots, c_k)$, the index $i$, $1\le i< k$ is said to be critical for $w$, if

For the previous example $w = 2\:3\:5\diamond7\diamond \diamond 10\:12\diamond 13\diamond\diamond$, we see the indices $2, 3$ and $6$ are critical for $w$. Let ${\mathcal{AW}}_{n, a, b}$ denote the set of admissible words $w: = w_{S, c}\in{\mathcal{AW}}_n$ such that ${\mathsf{ics}}(w) = a$, ${\mathsf{equ}}(w) = b$ and $s_1>1$, where $s_1$ is the smallest letter in $S$.

Theorem 3.6. For $1< a\le n$ and $1\le b< n$, there exists a bijection $\psi$ from ${\mathcal{AW}}_{n, a, b}$ to ${\mathcal{AW}}_{n, a-1, b+1}$, such that for each $w_{S, c}\in{\mathcal{AW}}_{n, a, b}$, if $\psi(w_{S, c}) = v_{T, d}$, then we have $S = T$.

Proof. Take any $w: = w_{S, c}\in{\mathcal{AW}}_{n, a, b}$ with $S = \{s_1, \ldots, s_k\}$ and $c = (c_1, \ldots, c_k)$, we explain how to produce an admissible word $v: = v_{S, d}$ such that ${\mathsf{ics}}(v) = {\mathsf{ics}}(w)-1$ and ${\mathsf{equ}}(v) = {\mathsf{equ}}(w)+1$. Since ${\mathsf{ics}}(w) = a\ge 2$, we see $c_1 = c_2 = \cdots = c_{a-1} = 0$ and $c_a>0$. Find the smallest $\ell\ge a-1$ such that the index $\ell$ is critical for $w$. Note that $s_1>1$ guarantees the existence of such an $\ell$. Let $d = (d_1, \cdots, d_k)$ be defined as

We denote $v: = v_{S, d}$ the admissible word with respect to $S$ and $d$, and set $\psi(w) = v$. It can be checked that $\sum_{i = 1}^k c_i = \sum_{i = 1}^k d_i = s_k-k$ and $\sum_{i = 1}^{\ell} d_i = s_{\ell}-\ell$, hence ${\mathsf{equ}}(v) = {\mathsf{equ}}(w)+1$ as desired. Also ${\mathsf{ics}}(v) = {\mathsf{ics}}(w)-1 = a-1$ since now $d_1 = \cdots = d_{a-2} = 0$ and $d_{a-1} = c_a>0$.

All it remains is to show that $\psi$ is invertible. To this end, for each $v: = v_{S, d}\in{\mathcal{AW}}_{n, a-1, b+1}$, find the smallest integer $\ell$ such that $\sum_{i = 1}^{\ell} d_i = s_{\ell}-\ell$. Note that since ${\mathsf{equ}}(v) = b+1\ge 2$, $s_1>1$ and $d_1 = \cdots = d_{a-2} = 0$, we must have $a-1\le \ell <k$, and $\ell$ being the smallest means $d_{\ell}>0$. Now let $c = (c_1, \ldots, c_k)$ be defined as

It is routine to check that $w: = w_{S, c}$ is the desired preimage so that $\psi(w) = v$, ${\mathsf{ics}}(w) = {\mathsf{ics}}(v)+1$, and ${\mathsf{equ}}(w) = {\mathsf{equ}}(v)-1$.

The following result is the restatement of Theorem 1.1 (i) and (ii).

Corollary 3.7. For $n\ge 1$, the two triples $({\mathrm{LMAX}}, {\mathsf{iar}}, {\mathsf{comp}})$ and $({\mathrm{LMAX}}, {\mathsf{comp}}, {\mathsf{iar}})$ have the same distribution over ${\mathfrak{S}}_n(321)$; while over ${\mathfrak{S}}_n(312)$, the two quadruples $({\mathrm{LMAX}}, {\mathrm{DESB}}, {\mathsf{iar}}, {\mathsf{comp}})$ and $({\mathrm{LMAX}}, {\mathrm{DESB}}, {\mathsf{comp}}, {\mathsf{iar}})$ have the same distribution.

Proof. For each permutation $\pi\in{\mathfrak{S}}_n(321)$ with $\pi(1)>1$, we find a unique permutation $\rho\in{\mathfrak{S}}_n(321)$ such that

If ${\mathsf{iar}}(\pi) = {\mathsf{comp}}(\pi)$, then simply take $\rho = \pi$. Otherwise we assume ${\mathsf{iar}}(\pi) = {\mathsf{comp}}(\pi)+k$ for some $k\neq 0$, let

Combining Theorem 3.6 with (9), we verify that

as desired. Now both $\alpha$ and $\psi$ are bijections, so $\pi$ and $\rho$ are in one-to-one correspondence. On the other hand, for each $\pi\in{\mathfrak{S}}_n(321)$ with $\pi(1) = 1$, we see $\nu: = {\operatorname{del}}_1(\pi)\in{\mathfrak{S}}_{n-1}(321)$ satisfies ${\mathsf{iar}}(\nu) = {\mathsf{iar}}(\pi)-1$, ${\mathsf{comp}}(\nu) = {\mathsf{comp}}(\pi)-1$, and ${\mathrm{LMAX}}(\nu)$ is the set obtained from decreasing each number in ${\mathrm{LMAX}}(\pi)\setminus\{1\}$ by $1$. This means we can use induction to finish the proof of the result for ${\mathfrak{S}}_n(321)$.

Finally, applying the bijection $\beta$ instead of $\alpha$ gives us the result for ${\mathfrak{S}}_n(312)$. To see why we can include ${\mathrm{DESB}}$ to have a quadruple in this case, simply observe that for each permutation $\sigma\in{\mathfrak{S}}_n(312)$, ${\mathrm{LMAX}}(\sigma)\cup{\mathrm{DESB}}(\sigma) = [n]$.

For most of our calculations of the generating function ${\mathfrak{S}}(P)(t, r, p)$ in this and later sections, we use some kind of decomposition by considering the largest (resp. smallest) letter $n$ (resp. $1$) in a permutation $\sigma\in{\mathfrak{S}}_n$. A maximal consecutive subset of $[n]$, all of whose elements appear on the same side of $n$ (resp. $1$) in $\sigma$, is called a block with respect to $n$ (resp. $1$). For example, the blocks with respect to $9$ in $251986743$ are $\{1, 2\}$, $\{3, 4\}$, $\{5\}$ and $\{6, 7, 8\}$. For two blocks (or sets) $A$ and $B$, we write $A<B$ if the maximal element of $A$ is smaller than the minimal element of $B$. As usual, we use $\chi(\mathsf{S}) = 1$ if the statement $\mathsf{S}$ is true, and $\chi(\mathsf{S}) = 0$ otherwise.

A square matrix is said to be Hankel if it has constant skew-diagonals. For the next theorem and Theorems 3.13 and 4.2, a key fact utilized by us is that $M_n(P)$ or $M_n^{{\mathsf{st}} = i}(P)$ is a Hankel matrix. This not only implies that $({\mathsf{iar}}, {\mathsf{comp}})$ is symmetric over ${\mathfrak{S}}_n(P)$, but also facilitates our calculation of the generating function ${\mathfrak{S}}(P)^{{\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}}(t, r, p;z)$. We elaborate on the latter point with the next lemma.

Lemma 3.8. Suppose $M = (m_{ij})_{1\le i, j\le n}$ is a Hankel matrix such that $m_{ij} = 0$ when $i+j\ge n+2$. Let $\mathcal{M}(x, y): = \sum_{1\le i, j\le n}m_{ij}x^iy^j$ and $\mathcal{N}(x): = \frac{\partial \mathcal{M}}{\partial y}|_{y = 0} = \sum_{1\le i\le n}m_{i1}x^i$ be the generating functions of $M$ and its first column, respectively. It holds that

Proof. The Hankel condition enables us to group together terms along the same skew-diagonal. Noting that $x^iy+x^{i-1}y^2+\cdots+xy^i = xy(x^i-y^i)/(x-y)$ for each $1\le i\le n$, we have

as desired.

Recall the Narayana polynomial $N_n(t): = \sum_{\pi\in{\mathfrak{S}}_n(\tau)}t^{{\mathsf{des}}(\pi)}$ ($\tau = 312, 213, 132$ or $231$) and its generating function (see e.g. [26,Eq. 2.6])

Theorem 3.9. The generating function of the triple statistic $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$ over ${\mathfrak{S}}_n(312)$ is given by

Proof. Conditioning on $\pi(1)$, we claim that (abbreviating ${\mathfrak{S}}(312)^{{\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}}(t, r, p)$ to ${\mathfrak{S}}(t, r, p)$)

where

Indeed, the first summand $1$ in (14) corresponds to the empty permutation, and the second to those with $\pi(1) = 1$. As for the third summand, we consider permutations $\pi$ with $\pi(1)>1$. Now Eq. (10) and Theorem 3.6 tell us that for a given $1\not\in S\subseteq [n]$, the matrix $M_n^{{\mathrm{LMAX}} = S}(312): = (m_{ij})_{1\le i, j\le n}$ is Hankel. Note that ${\mathsf{iar}}(\pi) = n$ only for $\pi = {\mathrm{id}}_n$ but we require that $\pi(1)>1$, so using the fact that the matrix is Hankel, we see $m_{ij} = 0$ when $i+j\ge n+1$. Consequently, Lemma 3.8 is applicable. Lastly, as we have already noted in the proof of Corollary 3.7, each permutation $\sigma\in{\mathfrak{S}}_n(312)$ satisfies ${\mathrm{LMAX}}(\sigma)\cup{\mathrm{DESB}}(\sigma) = [n]$. This means in particular that the statistic ${\mathsf{des}}$ takes the same value for all permutations enumerated by $M_n^{{\mathrm{LMAX}} = S}(312)$, justifying the variable $t$ in (15).

Next, plugging (15) into (14) yields

Setting $p = 1$ in (16), solving for $\tilde{\mathfrak{S}}(t, r, 0)$ and then plugging back into (16) gives us

It remains to calculate $\tilde{\mathfrak{S}}(t, r, 1)$. Every nonempty $312$-avoiding permutation $\pi$ has the block decomposition $\pi = A\:1\:B$ such that $A$ and $B$ are both $312$-avoiding blocks with $A<B$. We consider the following two cases:

● $A = \emptyset$, i.e. $\pi(1) = 1$. This case contributes the generating function $rz{\mathfrak{S}}(t, r, 1)$.

● $A\neq\emptyset$. This case contributes the generating function $({\mathfrak{S}}(t, r, 1)-1)tz{\mathfrak{S}}(t, 1, 1).$

Summing up these two cases and noting that ${\mathfrak{S}}(t, 1, 1) = N$, we deduce that

Solving for $\tilde{\mathfrak{S}}(t, r, 1)$ we get

Plugging this back into (17), we establish (13) after simplification.

Recall that

which is the generating function of the descent polynomials on $321$-avoiding permutations, first derived by Barnabei, Bonetti and Silimbani [3].

Theorem 3.10. The generating function of the triple statistic $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$ over ${\mathfrak{S}}_n(321)$ is given by

Proof. Recently, Fu, Han and Lin [15,Lemma 4.5] generalized (18) to

For convenience, let $I(r): = I_{321}(t, r)$ be the generating function over $\mathcal{I}_n(321)$ with respect to $({\mathsf{des}}, {\mathsf{iar}})$. Since $321$ is indecomposable, ${\mathsf{des}}$ is totally $\oplus$-compatible and ${\mathsf{iar}}$ is partially $\oplus$-compatible, Eq. (4) gives

It follows that

Substituting these back to (20) yields (19).

Pattern $132$

Now we move onto the class of $132$-avoiding permutations, on which the joint distribution of $({\mathsf{iar}}, {\mathsf{comp}})$ is symmetric as well. We collect in the following proposition some nice features of $132$-avoiding permutations. All of the statements should be clear from the $132$-avoiding restriction, thus the proof is omitted.

Proposition 3.11. For any permutation $\pi\in{\mathfrak{S}}_n(132)$, we have

1. For $2\le i\le n$, $\pi(i)$ is a descent bottom of $\pi$ if and only if it is a left-to-right minimum of $\pi$, i.e., ${\mathrm{LMIN}}(\pi) = {\mathrm{DESB}}(\pi)\cup\{\pi(1)\}$.

2. When read from left to right, the values of the left-to-right maxima of $\pi$ form a sequence of consecutive integers $\pi(1), \pi(1)+1, \pi(1)+2, \ldots, n$.

3. The first $k = {\mathsf{iar}}(\pi)$ letters of $\pi$ equal $\pi(1), \pi(1)+1, \ldots, \pi(1)+k-1.$

4. Provided $k = {\mathsf{comp}}(\pi) \ge 2$, the last $k-1$ letters of $\pi$ equal $n-k+2, \ldots, n$.

The next theorem strengthens Theorem 1.1 (iii).

Theorem 3.12. For all positive integers $n$, given any two subsets $S, T\subseteq [n]$, the matrix $M_n^{{\mathrm{LMAX}} = S, {\mathrm{LMIN}} = T}(132)$ is Hankel. Consequently, the distribution of the quadruple $({\mathrm{LMAX}}, {\mathrm{LMIN}}, {\mathsf{iar}}, {\mathsf{comp}})$ is equal to that of $({\mathrm{LMAX}}, {\mathrm{LMIN}}, {\mathsf{comp}}, {\mathsf{iar}})$ over ${\mathfrak{S}}_n(132)$. In terms of generating function, we have

In particular, we have

Proof. We begin by noting that for each $\pi\in{\mathfrak{S}}_n(132)$, its initial ascending run consists of consecutive numbers, and, unless $\pi$ is indecomposable, we have $\pi(n) = n$. Now if ${\mathsf{iar}}(\pi) = {\mathsf{comp}}(\pi) = 1$, i.e., $\pi$ is an indecomposable $132$-avoiding permutation with $\pi(1)>\pi(2)$, then it is counted by the top-left entry of $M_n^{{\mathrm{LMAX}} = S, {\mathrm{LMIN}} = T}(132)$ for certain $S$ and $T$. Similarly, if ${\mathsf{iar}}(\pi) = {\mathsf{comp}}(\pi) = n$, then we must have $\pi = {\mathrm{id}}_n$ and it corresponds to the bottom-right entry $1$ of $M_n^{{\mathrm{LMAX}} = [n], {\mathrm{LMIN}} = \{1\}}(132)$. Otherwise, for the given subsets $S, T\subseteq [n]$, take any permutation $\pi\in{\mathfrak{S}}_n(132)$ such that ${\mathrm{LMAX}}(\pi) = S$, ${\mathrm{LMIN}}(\pi) = T$, $2\le {\mathsf{iar}}(\pi)\le n-1$, and $1\le {\mathsf{comp}}(\pi)\le n-2$. We are going to pair $\pi$ with a permutation $\sigma\in{\mathfrak{S}}_n(132)$ via a bijective map $\varphi$, such that

i. $\pi(i) = \sigma(i)$ for $1\le i\le {\mathsf{iar}}(\pi)-1$.

ii. ${\mathrm{LMAX}}(\sigma) = {\mathrm{LMAX}}(\pi) = S$, and ${\mathrm{LMIN}}(\sigma) = {\mathrm{LMIN}}(\pi) = T$.

iii. ${\mathsf{iar}}(\sigma) = {\mathsf{iar}}(\pi)-1$, and ${\mathsf{comp}}(\sigma) = {\mathsf{comp}}(\pi)+1$.

In terms of the two operations deletion and insertion that we introduce in Definition 2.1, we let

with

being the inverse map. We illustrate this definition by giving an example, where the letters affected by this map have been overlined.

Applying Proposition 3.11, it is rountine to verify i, ii, and iii, and we leave the details to the reader. Items ii and iii ensure that $M_n^{{\mathrm{LMAX}} = S, {\mathrm{LMIN}} = T}(132)$ is Hankel as claimed. Now for any permutation $\pi\in{\mathfrak{S}}_n(132)$ with ${\mathsf{iar}}(\pi) = j>{\mathsf{comp}}(\pi) = k$, we see $\tau: = \varphi^{j-k}(\pi)$ is a permutation in ${\mathfrak{S}}_n(132)$ with

Pairing permutations in this way leads to (21).

Finally, by Proposition 3.11 (1) we have ${\mathrm{LMIN}}(\pi)\setminus\{\pi(1)\} = {\mathrm{DESB}}(\pi)$. Furthermore, item i above implies in particular that $\pi(1) = \sigma(1)$, combining this with ${\mathrm{LMIN}}(\pi) = {\mathrm{LMIN}}(\sigma)$ we obtain (22).

Theorem 3.13. We have

Proof. The proof is analogous to that of Theorem 3.9. Noting that $M_n^{{\mathsf{des}} = k}(132)$ is Hankel for any fixed integer $0\le k\le n-1$ by Theorem 3.12, we begin by interpreting this in terms of generating function. Empty permutation and identity permutations of all lengths contribute $1/(1-rpz)$, while the remaining permutations are taken care of by Lemma 3.8, yielding

Converting to $\tilde{\mathfrak{S}}(t, r, p)$ we have

Plugging in $p = 1$ we have

Now solve for $\tilde{\mathfrak{S}}(t, r, 0)$ and substitute the result back in (24) we get

Next, we decompose each $132$-avoiding permutation $\pi$ as $\pi = A\:n\:B$, where $A$ and $B$ are blocks with $A>B$. In the same vein as with $312$-avoiding class, the discussion by two cases leads us to

We plug this back into (25) and simplify to arrive at (23).

3.2.   Asymmetric classes

We deal with the three remaining classes, namely, $213$-, $231$-, and $123$-avoiding permutations. The distributions of ${\mathsf{iar}}$ and ${\mathsf{comp}}$ on each of these classes are different. We are content with deriving their joint generating functions with ${\mathsf{des}}$, and addressing a conjugate relation between $M_n(213)$ and $M_n(231)$.

Patterns $213$ and $231$

Theorem 3.14. For every $n\ge 0$, there exists a bijection $\theta:{\mathfrak{S}}_n(213)\rightarrow{\mathfrak{S}}_n(231)$, such that for $\pi\in{\mathfrak{S}}_n(213)$ and $\sigma: = \theta(\pi)\in{\mathfrak{S}}_n(231)$, we have $\pi(1) = \sigma(1)$ and

In particular, the matrices $M_n(213)$ and $M_n(231)$ are conjugation of each other.

Proof. We define $\theta$ recursively. For $n = 0, 1, 2$, $\theta:{\mathfrak{S}}_n(213)\rightarrow{\mathfrak{S}}_n(231)$ is taken to be the identity map. Now suppose $\theta$ has been defined for all $k < n\; (n\ge 3)$, then take any $\pi\in{\mathfrak{S}}_n(213)$, we can uniquely decompose $\pi = \pi(1)\:A\:B$ with $A>\pi(1)>B$. Let $\mu = red(A)$ and $\nu = B$, then we see that ${\operatorname{del}}_{\pi(1)}(\pi) = \mu\ominus\nu$, where both $\mu$ and $\nu$ are $213$-avoiding, possibly empty permutations. Let

The following facts can be readily verified.

$1.$$\sigma\in{\mathfrak{S}}_n(231)$;

$2.$$\sigma(1) = \pi(1)$;

$3.$${\mathsf{des}}(\sigma) = \chi(\nu\neq\emptyset)+{\mathsf{des}}(\theta(\nu))+{\mathsf{des}}(\theta(\mu)) = {\mathsf{des}}(\pi)$;

$4.$${\mathsf{comp}}(\sigma) = 1+{\mathsf{comp}}(\theta(\mu)) = 1+{\mathsf{iar}}(\mu) = {\mathsf{iar}}(\pi)$;

$5.$${\mathsf{iar}}(\sigma) = 1+\chi(\nu = \emptyset)\cdot{\mathsf{iar}}(\theta(\mu)) = 1+\chi(\nu = \emptyset)\cdot{\mathsf{comp}}(\mu) = {\mathsf{comp}}(\pi)$.

So we see $\sigma$ is the desired image of $\pi$, and the proof is now completed by induction.

The equidistribution between $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$ over ${\mathfrak{S}}_n(213)$ and $({\mathsf{des}}, {\mathsf{comp}}, {\mathsf{iar}})$ over ${\mathfrak{S}}_n(231)$ could also be drawn from comparing the following generating functions.

Theorem 3.15. We have

Proof. We begin with the calculation of $\tilde{\mathfrak{S}}(213)^{{\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}}(t, r, p)$. Each $\pi\in{\mathfrak{S}}_n(213)$ can be decomposed as $\pi = \pi(1)\:A\:B$, where $A>\pi(1)>B$ are $213$-avoiding blocks, possibly empty. For $n\ge 2$, we consider the following three cases:

● $A = \emptyset$, $B\neq\emptyset$, contributing the generating function $trpz({\mathfrak{S}}(t, 1, 1)-1)$.

● $A\neq\emptyset$, $B = \emptyset$, contributing $rpz({\mathfrak{S}}(t, r, p)-1)$.

● $A\neq\emptyset$, $B\neq\emptyset$, contributing $trpz({\mathfrak{S}}(t, r, 1)-1)({\mathfrak{S}}(t, 1, 1)-1)$.

Summing up these three cases and noting that ${\mathfrak{S}}(t, 1, 1) = N$, we deduce that

Now we plug in $p = 1$ and solve for ${\mathfrak{S}}(t, r, 1)$, then plug it back to deduce (26) after simplification.

Decomposing each $\pi\in{\mathfrak{S}}_n(231)$ as $\pi = \pi(1)\:A\:B$ with $A<\pi(1)<B$, and calculating along the same line, we can establish (27) as well.

Pattern $123$

For $\pi\in{\mathfrak{S}}_n(123)$, clearly ${\mathsf{iar}}(\pi)\le 2$ and ${\mathsf{comp}}(\pi)\le 2$. We aim to calculate

where

By (18), the generating function for the descent polynomials on $123$-avoiding permutations is

Theorem 3.16. We have

Thus,

Proof. For $\pi\in{\mathfrak{S}}_n(123)$ with ${\mathsf{iar}}(\pi) = 1$ and ${\mathsf{comp}}(\pi) = 2$, we can decompose it as $\pi = A\: B$, where $A < B$ are both decreasing subsequences with $|A|\ge 2$ and $|B|\ge 1$. On the other hand, if $\pi\in{\mathfrak{S}}_n(123)$ and ${\mathsf{iar}}(\pi) = 2$, then we must have $\pi(2) = n$, and we calculate the two cases $\pi(1)>\pi(3)$ and $\pi(1)<\pi(3)$ separately. All these amount to give us the functional equations:

Solving this system of equations gives rise to (29) and (30).

The following corollary can be proved combinatorially from analyzing the designated $123$-avoiding permutations. But we prove it here algebraically relying on the generating function derived in Theorem 3.16.

Corollary 3.17. For $n\ge 2$, let ${\mathfrak{S}}_n^{*}(123): = \{\pi\in{\mathfrak{S}}_n(123):{\mathsf{des}}(\pi) = n-2\}$, then we have

In particular, the distribution of $({\mathsf{iar}}, {\mathsf{comp}})$ is symmetric over ${\mathfrak{S}}_n^*(123)$, and the number of permutations $\pi\in{\mathfrak{S}}_n^*(123)$ with ${\mathsf{iar}}(\pi) = {\mathsf{comp}}(\pi) = 1$ is the sequence A095264 in [25].

Proof. To calculate the generating function in (31), we need to extract the coefficients of $t^{n-2}z^n$ in ${\mathfrak{S}}(123)^{{\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}}(t, r, p)$ for each $n\ge 2$. For $rpzA(t, p)$, the term $\frac{(p-1)trpz^3}{(1-tz)^2}$ expands to terms all of the form $t^{n-2}z^n$, so we simply set $t = 1$ to get $\frac{(p-1)rpz^3}{(1-z)^2}$, while for the term $\frac{rp(1-tz)({\mathfrak{S}}(t, 1, 1)-1)}{1-tz+z}$, we substitute $tz$ for $z$, and $1/t$ for $t$ in

then take partial derivative $\partial/\partial t$ and let $t = 0$ to obtain $\frac{2rpz^3}{(1-z)^2(1-2z)}$. A similar approach yields the coefficients from $r^2pzB(t, p)$ and establishes (31). The claim about the symmetric distribution is evident from checking the variables $r$ and $p$ in (31).

4.   Two patterns of length 3

In this section, we let $P = (\tau_1, \tau_2)$ be a pair of patterns of length $3$, so there are $\binom{6}{2} = 15$ different pairs to consider. Once again, we accomplish two tasks as in Section 3 and assemble our results in Table 2.

The Wilf-classification of pairs of length $3$ patterns was done by Simion and Schmidt [28]. There are three Wilf-equivalent classes, which further split into eleven ${\mathsf{iar}}$-Wilf-equivalent subclasses: the class enumerated by $2^{n-1}$ splits into $6$ classes

the class enumerated by $1+\binom{n}{2}$ splits into $4$ classes

and the terminating (i.e., enumerated by $0$ when $n\ge 5$) class $\{(123, 321)\}$ stays as a single class. For ${\mathsf{comp}}$-Wilf-equivalences, the class enumerated by $2^{n-1}$ splits into $4$ classes

and the class enumerated by $1+\binom{n}{2}$ splits into $2$ classes

All the above refined Wilf-equivalences can be easily proven by setting $t = 1$, and $p = 1$ (or $r = 1$) in the generating functions listed in Table 2.

4.1.   Symmetric classes

For $P\in\{(132, 312), (132, 321), (213, 231), (123, 312)\}$, the joint distribution of $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$ is symmetric for ${\mathsf{iar}}$ and ${\mathsf{comp}}$ over ${\mathfrak{S}}_n(P)$. We consider these four classes in this subsection.

Pattern pairs $(132, 312)$ and $(132, 321)$

First note that if the pattern $312$ (resp. $321$) occurs in a permutation $\pi$, then we can always find an occurrence of $312$ (resp. $321$) in $\pi$ with the role of "$3$" played by a left-to-right maximum of $\pi$. Now recall the bijection $\varphi$ we construct in the proof of Theorem 3.12. For each $\pi\in{\mathfrak{S}}_n(132)$, observe that $\pi\in{\mathfrak{S}}_n(132, 312)$ (resp. $\pi\in{\mathfrak{S}}_n(132, 321)$) if and only if $\varphi(\pi)\in{\mathfrak{S}}_n(132, 312)$ (resp. $\varphi(\pi)\in{\mathfrak{S}}_n(132, 321)$). This fact, combined with Theorem 3.12, immediately yields the following theorem.

Theorem 4.1. For all positive integers $n$, given any two subsets $S, T\subseteq [n]$, the matrix $M_n^{{\mathrm{LMAX}} = S, {\mathrm{LMIN}} = T}(P)$ is Hankel, for $P\in\{(132, 312), (132, 321)\}$. Consequently, the distribution of the quadruple $({\mathrm{LMAX}}, {\mathrm{LMIN}}, {\mathsf{iar}}, {\mathsf{comp}})$ is equal to that of $({\mathrm{LMAX}}, {\mathrm{LMIN}}, {\mathsf{comp}}, {\mathsf{iar}})$ over ${\mathfrak{S}}_n(P)$. In terms of generating function, we have

In particular, we have

This symmetry can also be seen directly from the following generating functions.

Theorem 4.2. We have

Proof. The proof is quite analogous to that of Theorem 3.13. First for (32), Theorem 4.1 tells us that $M_n^{{\mathrm{LMAX}} = S, {\mathrm{LMIN}} = T}(132, 312)$ is Hankel. Relying on Lemma 3.8 again, we reinterpret this in terms of generating function (details left to the readers):

Next, note that all ${\mathrm{id}}_n: = 12\cdots n$ with $n\ge 0$ contribute collectively $1/(1-rpz)$ to ${\mathfrak{S}}(132, 312)^{{\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}}(t, r, p)$. On the other hand, every $\pi\in{\mathfrak{S}}_n(132, 312)$ with ${\mathsf{des}}(\pi)>0$ can be uniquely decomposed as $\pi = A\:n\:B$, where $A>B$ are two (possibly empty) blocks such that $B$ is decreasing and $A$ is $132$- and $312$-avoiding. We consider the following two cases.

● $B = \emptyset$. This case contributes the generating function $pz({\mathfrak{S}}(t, r, p)-\frac{1}{1-rpz})$.

● $B\neq\emptyset$. This case contributes $\frac{tz}{1-tz}\cdot\frac{rpz}{1-rz}+\frac{tpz^2}{1-tz}({\mathfrak{S}}(t, r, 1)-\frac{1}{1-rz})$.

Summing up all cases gives us

Set $p = 1$ and solve to get

then plug this back into (34) and simplify, we get (32). The proof of (33) is simpler noting that for $\pi\in{\mathfrak{S}}_n(132, 321)$ with the decomposition $\pi = A\:n\:B$, both $A$ and $B$ are increasing if $B\neq\emptyset$. The details are omitted.

Pattern pair $(213, 231)$

The first thing to notice is that for every $\pi\in{\mathfrak{S}}_n(213, 231)$, we must have $\pi(1) = 1$ or $n$, and ${\mathsf{iar}}(\pi) = {\mathsf{comp}}(\pi)$. The latter can be proved by induction relying on the former. In terms of generating function, this means

Solving these two functional equations gives us

Theorem 4.3.

Pattern pair $(123, 312)$

For every permutation $\pi\in{\mathfrak{S}}_n(123, 312)$, there are only five possible values for the triple $({\mathsf{des}}(\pi), {\mathsf{iar}}(\pi), {\mathsf{comp}}(\pi))$, since $123$-avoiding implies ${\mathsf{iar}}(\pi)\le 2$ and ${\mathsf{comp}}(\pi)\le 2$, while both $312$- and $123$-avoiding forces ${\mathsf{des}}(\pi)\ge n-2$. Now it suffices to enumerate each case separately.

● $({\mathsf{des}}(\pi), {\mathsf{iar}}(\pi), {\mathsf{comp}}(\pi)) = (n-1, 1, 1)$. There is a unique permutation ${\mathrm{id}}_n^{\mathrm{r}} = n\cdots 2 1$ for this case, which contributes $\frac{rpz}{1-tz}$ to the generating function.

● $({\mathsf{des}}(\pi), {\mathsf{iar}}(\pi), {\mathsf{comp}}(\pi)) = (n-2, 2, 2)$. There is a unique permutation $1\oplus{\mathrm{id}}_{n-1}^{\mathrm{r}}$ for this case, which contributes $\frac{r^2p^2z^2}{1-tz}$ to the generating function.

● $({\mathsf{des}}(\pi), {\mathsf{iar}}(\pi), {\mathsf{comp}}(\pi)) = (n-2, 1, 1)$. Permutations in this case are of the form $\pi = a\:a-1\cdots b\:n\cdots a+1\:b-1\cdots 1$, where $1<b<a<n$. Therefore this case contributes $\frac{t^2rpz^4}{(1-tz)^3}$ to the generating function.

● $({\mathsf{des}}(\pi), {\mathsf{iar}}(\pi), {\mathsf{comp}}(\pi)) = (n-2, 2, 1)$ or $(n-2, 1, 2)$. These two cases can be discussed similarly as the last case, and the contributions are $\frac{tr^2pz^3}{(1-tz)^2}$ and $\frac{trp^2z^3}{(1-tz)^2}$.

Summing up all cases above gives rise to

Theorem 4.4.

4.2.   Asymmetric classes

For the remaining choices of $P$, the distribution of $({\mathsf{iar}}, {\mathsf{comp}})$ over ${\mathfrak{S}}_n(P)$ is not symmetric. However, we still observe some conjugative pairs as in Section 3.

Pattern pairs $(213, 312)$, $(231, 312)$ and $(231, 321)$

Recall the two bijections, $\xi$ from Theorem 3.2, and $\theta$ from Theorem 3.14. Observe that

● $\pi\in{\mathfrak{S}}_n(231, 321)$ if and only if $\xi(\pi)\in{\mathfrak{S}}_n(231, 312)$.

● $\pi\in{\mathfrak{S}}_n(213, 312)$ if and only if $\theta(\pi)\in{\mathfrak{S}}_n(231, 312)$.

Then the following theorem is a quick corollary of Theorems 3.2 and 3.14.

Theorem 4.5. For each $n\ge 1$, the quadruple $({\mathrm{LMAX}}, {\mathrm{LMAXP}}, {\mathsf{iar}}, {\mathsf{comp}})$ has the same distribution over ${\mathfrak{S}}_n(231, 321)$ and ${\mathfrak{S}}_n(231, 312)$; the distribution of the triple $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$ over ${\mathfrak{S}}_n(213, 312)$ is equal to that of $({\mathsf{des}}, {\mathsf{comp}}, {\mathsf{iar}})$ over ${\mathfrak{S}}_n(231, 312)$.

Next, we compute the generating functions for these three pairs.

Theorem 4.6. We have

Proof. In view of Theorem 4.5, (35) follows from (36) by switching variables $r$ and $p$. To prove (36), note that both patterns $231$ and $312$ are indecomposable, thus we can apply Lemma 2.4 to reduce the calculation to that of the generating function of $({\mathsf{des}}, {\mathsf{iar}})$ over $\mathcal{I}_n(231, 312)$. But the indecomposable permutations in ${\mathfrak{S}}_n(231, 312)$ are precisely ${\mathrm{id}}_n^{\mathrm{r}} = n\:n-1\cdots 1$, thus $I_{231, 312}(t, r) = \frac{rz}{1-tz}$. Plugging this back into (4) gives us (36). Finally, every permutation in $\mathcal{I}_n(231, 321)$ must be of the form $1\ominus{\mathrm{id}}_{n-1} = n\:1\:2\cdots n-1$, yeilding the generating function $I_{231, 321}(r, t) = rz+\frac{trz^2}{1-z}$. Applying (4) from Lemma 2.4 again, we derive (37) and complete the proof.

Pattern pairs $(132, 213)$ and $(132, 231)$

For the same reason that the bijection $\theta$ from Theorem 3.14 preserves $132$-avoidance, we have the following conjugate relation.

Theorem 4.7. For each $n\ge 1$, the distribution of the triple $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$ over ${\mathfrak{S}}_n(132, 213)$ is equal to that of $({\mathsf{des}}, {\mathsf{comp}}, {\mathsf{iar}})$ over ${\mathfrak{S}}_n(132, 231)$.

Next, note that each permutation $\pi\in{\mathfrak{S}}_n(132, 231)$ either begins with $\pi(1) = n$, or ends with $\pi(n) = n$. Calculating these two cases separately we have

Solving this and applying Theorem 4.7, we can deduce the following theorem.

Theorem 4.8. We have

Pattern pair $(213, 321)$

Note that each permutation $\pi\in{\mathfrak{S}}_n(213, 321)$ can be decomposed as $\pi = A\:n\:B$, where $A$ and $B$ are both increasing blocks, and $B$ is consisted of consecutive integers. Calculating the two cases $1\in A$ and $1\in B$ separately, we obtain the following theorem.

Theorem 4.9. We have

Pattern pair $(312, 321)$

Noting that both $312$ and $321$ are indecomposable patterns, we apply (4)

from Lemma 2.4 (1) to reduce the calculation to

Now any indecomposable $\pi\in{\mathfrak{S}}_n(312, 321)$ must be of the form $\pi = 2\:3\cdots n\:1$. Hence

with which we can deduce

Theorem 4.10.

Pattern pairs $(123, 132)$, $(123, 213)$, $(123, 231)$ and $(123, 321)$

These four pattern sets all contain the pattern $123$, hence ${\mathsf{iar}}(\pi)\le 2$ and ${\mathsf{comp}}(\pi) \le 2$ for each permutation $\pi$ in ${\mathfrak{S}}_n(P)$. We take similar approach as Theorem 3.16, or analyze the position of $1$ or $n$ in $\pi$, to calculate their generating functions. We collect the results in the following theorem but omit the proof.

Theorem 4.11. We have

5.   Schröder classes: Two patterns of length 4

This section aims to characterize the pattern pair $P$ of length $4$ whose distribution matrix $M_n(P)$ equals $M_n(2413, 3142)$. The first few values of the symmetric matrices $M_n(2413, 3142)$ are:

The integer sequence formed by the entries in the upper-left corner of $M_n(2413, 3142)$ begins with

This sequence matches A010683 in the OEIS [25], a sequence that counts, among many combinatorial objects, dissections of a convex polygon with $n+3$ sides having a triangle over a fixed side (the base) of the polygon. This coincidence can be proved by comparing $\tilde {\mathfrak{S}}({\mathcal{S}})(1, 0, 0)$ from the expression (41) with the generating function supplied in the entry A010683.

The first result in this section is a consequence of Theorems 1.3 and 1.4.

Corollary 5.1. For $n\geq1$,

Consequently,

Proof. Since the patterns $2413, 4213$ and $3142$ are indecomposable, the equidistribution (38) is a consequence of Theorem 1.4 (with $x = 1$) and Lemma 2.4.

The identity (39) follows directly from (38) and Theorem 1.3.

Remark 3. In view of Corollary 5.1, one may wonder that if (2) can be further refined by ${\mathsf{comp}}$. This is not true and it turns out that even $({\mathsf{dd}}, {\mathsf{comp}})$ is not equidistributed over ${\mathfrak{S}}_5(2413, 3142)$ and ${\mathfrak{S}}_5(2413, 4213)$. Can Theorem 1.4 be further refined by other classical permutation statistics (cf. [20])?

Lin and Kim [24,Theorem 5.1] showed that, among all permutation classes avoiding two patterns of length 4, the three classes below are the only nontrivial classes which are ${\mathsf{des}}$-Wilf equivalent to the class of separable permutations.

Theorem 5.2 ([24]). We have the refined Wilf-equivalences:

It should be noted that ${\mathsf{iar}}$ is not a Comtet statistic over ${\mathfrak{S}}_n(2314, 3214)$. Computer program indicates that, among all permutation classes avoiding two patterns of length 4, the classes of $(2413, 4213)$ and $(3412, 4312)$ are the only two that are $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$-Wilf equivalent to the class of separable permutations.

Theorem 5.3. We have $(2413, 4213)\sim_{({\mathrm{DES}}, {\mathsf{comp}})}(3412, 4312)$. In particular,

Consequently,

In order to prove Theorem 5.3, we need a set-valued version of Lemma 2.4. For an integer $\ell$ and a set $S = \{s_1, s_2, \ldots\}$, let $\ell + S: = \{\ell+s_1, \ell+s_2, \ldots\}$. A set-valued statistic ${\mathrm{ST}}$ is called totally $\oplus$-compatible if for each $\pi = \tau_1\oplus\tau_2\oplus\cdots\oplus\tau_k$ with each $\tau_i$ an indecomposable permutation of length $\ell_i$,

where $c_i = \sum_{j = 1}^{i-1}\ell_j$. Note that the set-valued statistics ${\mathrm{DES}}$, ${\mathrm{DESB}}$, ${\mathrm{LMAX}}$ and ${\mathrm{LMAXP}}$ are all totally $\oplus$-compatible.

Lemma 5.4. Let $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ be a sequence of totally $\oplus$-compatible set-valued statistics. Let $P$ and $Q$ be two collections of indecomposable patterns. For $n\geq1$, if $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ has the same distribution over ${\mathfrak{S}}_n(P)$ and ${\mathfrak{S}}_n(Q)$, then so does $({\mathsf{comp}}, {\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$.

Proof. Since $P/Q$ (meaning $P$ or $Q$) is a collection of indecomposable patterns, each $P/Q$-avoiding permutation is a direct sum of some smaller $P/Q$-avoiding permutations. Thus, it is sufficient to show that if $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ is equidistributed over ${\mathfrak{S}}_n(P)$ and ${\mathfrak{S}}_n(Q)$ for $n\geq1$, then $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ is equidistributed over $\mathcal{I}_n(P)$ and $\mathcal{I}_n(Q)$. We aim to prove this by induction on $n$.

Obviously, the assertion is true for $n = 1$. Suppose that $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ is equidistributed over $\mathcal{I}_n(P)$ and $\mathcal{I}_n(Q)$ for $n\leq m$. It follows that $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ is equidistributed over ${\mathfrak{S}}_{m+1}(P)\setminus \mathcal{I}_{m+1}(P)$ and ${\mathfrak{S}}_{m+1}(Q)\setminus \mathcal{I}_{m+1}(Q)$, as $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ is a sequence of totally $\oplus$-compatible set-valued statistics. Now $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ is also equidistributed over ${\mathfrak{S}}_{m+1}(P)$ and ${\mathfrak{S}}_{m+1}(Q)$ and so $({\mathrm{ST}}_1, {\mathrm{ST}}_2, \ldots)$ is equidistributed over $\mathcal{I}_{m+1}(P)$ and $\mathcal{I}_{m+1}(Q)$. This completes the proof by induction.

Proof of Theorem 5.3. The refined Wilf-equivalence

is a direct consequence of Theorem 5.2 and Lemma 5.4, as the set-valued statistic ${\mathrm{DES}}$ is totally $\oplus$-compatible. The other two statements then follow immediately from Corollary 5.1.

Next we compute the generating function $\tilde{\mathfrak{S}}({\mathcal{S}})(t, r, p) = ({\mathfrak{S}}({\mathcal{S}})(t, r, p;z)-1)/rpz$ with respect to $({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}})$, where ${\mathcal{S}}$ is a pattern pair in

Theorem 5.5. Let $S(t): = {\mathfrak{S}}({\mathcal{S}})(t, 1, 1;z)-1$. Then,

where $S(t)$ satisfies the algebraic functional equation

Proof. The functional equation (42) for the generating function $S(t)$ of the descent polynomials over separable permutations was proved in [17]. Since the patterns $2413$ and $3142$ are indecomposable, ${\mathsf{des}}$ is totally $\oplus$-compatible and ${\mathsf{iar}}$ is partially $\oplus$-compatible, Eq. (6) gives

where $I_{{\mathcal{S}}}: = I_{{\mathcal{S}}}(t;z)$ is the generating function with respect to ${\mathsf{des}}$. Since $S(t) = \frac{I_{{\mathcal{S}}}}{1-I_{{\mathcal{S}}}}$, we have

Substitute this into (43) and simplify, we get (41).

Aided by the computer program, we make the following conjecture, whose validity will complete the characterization of pattern pairs of length $4$ that are ${\mathsf{iar}}$-Wilf equivalent to the class of separable permutations.

Conjecture 1. Let $P\notin\{(2413, 3142), (2413, 4213), (3412, 4312)\}$ be a pair of patterns of length $4$. Then, $P$ is ${\mathsf{iar}}$-Wilf equivalent to $(2413, 4213)$ if and only if $P$ is one of the following eleven pairs:

Moreover, if $P$ is one of the last five pairs (i.e., those in the second line above), then $P$ is $({\mathsf{iar}}, {\mathsf{comp}})$-Wilf equivalent to $(2413, 4213)$.

Remark 4. In view of Lemma 2.4, the second assertion for the $({\mathsf{iar}}, {\mathsf{comp}})$-Wilf equivalences in Conjecture 1 follows automatically from the first assertion, as all the patterns appear in the last five pairs are indecomposable.

In the rest of this section, we aim to confirm Conjecture 1 for the pattern pair $P = (2431, 4231)$ using the technique of generating trees, which was originally employed to study the Baxter permutations by Chung, Graham, Hoggatt and Kleiman [6], see also [28,31].

Theorem 5.6. We have the refined Wilf equivalence

In particular, $(2413, 4213)\sim_{({\mathsf{lmax}}, {\mathsf{iar}}, {\mathsf{comp}})}(2431, 4231)$ and Conjecture 1 is true for $P = (2431, 4231)$.

In view of Lemma 5.4, to prove Theorem 5.6, it is sufficient to prove the refined Wilf-equivalence $(2413, 4213)\sim_{{\mathrm{LMAXP}}}(2431, 4231)$. We will prove this by showing a growth rule for $(2431, 4231)$-avoiding permutations and then comparing it with that of $(2413, 4213)$-avoiding permutations.

For $\pi\in{\mathfrak{S}}_{n-1}$ and $i\in[n]$, let ${\operatorname{ins}}_i(\pi): = {\operatorname{ins}}_{i, n}(\pi)\in{\mathfrak{S}}_{n}$. Thus for example, ${\operatorname{ins}}_3(14532) = 156423$. If $\pi\in{\mathfrak{S}}_{n-1}(2431, 4231)$, then introduce the set of available inserting values of $\pi$ as

Clearly, if $i\in{\mathrm{AVA}}(\pi)$, then $k\in{\mathrm{AVA}}(\pi)$ for any $i\leq k\leq n$, since the newly inserted letter, which appears at the end, can only play the role of '1' in a pattern $2431$ or $4231$. Thus, ${\mathrm{AVA}}(\pi) = [m, n]: = \{m, m+1, \ldots, n\}$ for some $m<n$. We will call $m$ the critical value of $\pi$ in the sequel. For example, we have ${\mathrm{AVA}}(14523) = [3, 6]$.

We have the following growth rule for $(2431, 4231)$-avoiding permutations.

Lemma 5.7. Suppose $\pi\in{\mathfrak{S}}_{n-1}(2431, 4231)$ with ${\mathrm{AVA}}(\pi) = [m, n]$. Then,

Proof. For $m\leq j\leq n-1$, the letters $j-1$ (if $j\ge 2$) and $j+1$ appear before $j$ in ${\operatorname{ins}}_j(\pi)$ and these three letters form a pattern $132$ or $312$. Thus, $j-1\notin{\mathrm{AVA}}({\operatorname{ins}}_j(\pi))$. On the other hand, suppose $\hat\pi: = {\operatorname{ins}}_j({\operatorname{ins}}_j(\pi)) = \hat\pi(1)\cdots\hat\pi(n)\hat\pi(n+1)$, then we see $\hat\pi(a), \hat\pi(b), \hat\pi(c)$ and $\hat\pi(n) = j+1$ form a pattern $2431$ or $4231$, if and only if $\hat\pi(a), \hat\pi(b), \hat\pi(c)$ and $\hat\pi(n+1) = j$ do. This means we have $j\in{\mathrm{AVA}}({\operatorname{ins}}_j(\pi))$. Therefore $j$ is the critical value of ${\operatorname{ins}}_j(\pi)$ and ${\mathrm{AVA}}({\operatorname{ins}}_j(\pi)) = [j, n+1]$. Clearly, ${\mathrm{AVA}}({\operatorname{ins}}_n(\pi)) = [m, n+1]$. This completes the proof of the lemma.

The definition of ${\mathrm{AVA}}(\pi)$ for a $(2413, 4213)$-avoiding permutation $\pi$ was introduced similarly in [24], where they proved the following growth rule. Note that for any $\pi\in{\mathfrak{S}}_{n-1}(2413, 4213)$, ${\mathrm{AVA}}(\pi)$ always contains $1$ and $n$.

Lemma 5.8. (Lin and Kim [24,Lemma 5.3]). Suppose $\pi\in{\mathfrak{S}}_{n-1}(2413, 4213)$ with

Then, for $1\leq j\leq m$,

We are ready to prove Theorem 5.6 by constructing the generating trees for both classes.

Proof of Theorem 5.6. Label each $\pi\in{\mathfrak{S}}_n(2431, 4231)$ by $|{\mathrm{AVA}}(\pi)|$, Lemma 5.7 then produces the rewriting rule:

This means that the initial permutation ${\mathrm{id}}_1$ has label $(2)$ and all the $(2431, 4231)$-avoiding permutations derived from inserting a letter at the end of a $(2431, 4231)$-avoiding permutation labeled by $(k)$, are exactly those with labels $(k+1), (k+1), (k), (k-1), \ldots, (3)$.

We can construct a generating tree (an infinite rooted and labeled tree) for $(2431, 4231)$-avoiding permutations by representing each permutation as a node on the tree using its label. More precisely, the root is labeled $(2)$, and the children of a node labeled $(k)$ are those generated according to the rewriting rule $\Omega_{\mathrm{Sch}}$ in (44). In addition, the labels for those permutations ending with their greatest letter will have an extra '$*$', and we will call the corresponding nodes the star nodes. So in this generating tree, every node has precisely one child being a star node. See Fig. 1 for the first few levels of this generating tree. Note that the nodes at the $n$-th level of this tree are in one-to-one correspondence with elements of ${\mathfrak{S}}_n(2431, 4231)$. Moreover, if a permutation $\pi\in{\mathfrak{S}}_n(2431, 4231)$ is labeled by $\ell(\pi)$, and the unique path from the root $(2)^*$ to $\ell(\pi)$ goes through $p_1 = (2)^*, p_2, \ldots, p_n = \ell(\pi)$, then

For instance, the second $(4)^*$ appearing in level $3$ corresponds to $213$ and we have ${\mathrm{LMAXP}}(213) = \{1, 3\}$. In other words, the distribution of ${\mathrm{LMAXP}}$ over $(2431, 4231)$-avoiding permutations is completely determined by this generating tree.

It can be readily checked that Lemma 5.8 gives the same rewriting rule $\Omega_{\mathrm{Sch}}$ for $(2413, 4213)$-avoiding permutations, which in turn, produces for $(2413, 4213)$-avoiding permutations the identical generating tree as $(2431, 4231)$-avoiding permutations. This proves $(2413, 4213)\sim_{{\mathrm{LMAXP}}}(2431, 4231)$, as desired.

6.   Revisiting separable and (2413, 4213)-avoiding permutations

The main purpose of this section is to prove Theorem 1.4. We begin with the motivation that leads to the discovery of Theorem 1.4.

Recall that a sequence $e = (e_1, e_2, \ldots, e_n)\in \mathbb{N}^n$ is an inversion sequence of length $n$ if $e_i<i$ for each $i\in[n]$. An inversion sequence is {\em$021$-avoiding} if its positive entries are weakly increasing. Denote by $\mathfrak{I}_n(021)$ the set of $021$-avoiding inversion sequences of length $n$. Kim and Lin [24]

● constructed a bijection $\Psi: \mathfrak{I}_n(021)\rightarrow{\mathfrak{S}}_n(2413, 4213)$ which transforms the set-valued statistic ${\mathrm{ASC}}$ to ${\mathrm{DES}}$, where ${\mathrm{ASC}}(e): = \{i\in[n-1]: e_i<e_{i+1}\}$ is the set of ascents of $e$. In particular, together with the works in [10,17,23] we know

where ${\mathsf{asc}}(e): = |{\mathrm{ASC}}(e)|$;

● proved combinatorially via the so-called modified Foata–Strehl action that

Recall that $\Gamma_{n, k}(2413, 4213)$ is the set of permutations in ${\mathfrak{S}}_n(2413, 4213)$ with $k$ descents and without double descents. Combining (1), (45) and (46) yields

for all $0\leq k\leq n-1$. This identity was refined recently by Wang [30] as

where ${\mathsf{dd}}(\pi)$ denotes the number of double descents of $\pi$. Setting $x = 0$ in (48) we recover (47).

Theorem 1.4 is a refinement of Wang's equidistribution (48) by the Comtet statistic ${\mathsf{iar}}$. The three numerical statistics ${\mathsf{des}}$, ${\mathsf{dd}}$ and ${\mathsf{iar}}$ are all determined by the set-valued statistic ${\mathrm{DES}}$, but $(2413, 4213)$ is not ${\mathrm{DES}}$-Wilf equivalent to $(2413, 3142)$. In spite of that, we still have the refined Wilf-equivalence $(2413, 4213)\sim_{({\mathsf{des}}, {\mathsf{dd}}, {\mathsf{iar}})}(2413, 3142)$, to our surprise. Our proof of Theorem 1.4 is purely algebraic, basing on Kim–Lin's bijection $\Psi$, a decomposition of $021$-avoiding inversion sequences and Stankova's block decomposition of separable permutations [29]. It would be interesting to construct a bijective proof of this equidistribution.

As we will see, some easy combinatorial arguments on $021$-avoiding inversion sequences (see Theorem 6.1) together with Theorem 1.4 provide an alternative approach to a recent result of the first and third authors [18,Theorem 3.2].

6.1.   A recurrence for 021-avoiding inversion sequences

For each inversion sequence $e = (e_1, \ldots, e_n)$, let ${\mathsf{izero}}(e): = \min({\mathrm{ASC}}(e)\cup\{n\})$ be the number of initial zeros of $e$. It follows from the aforementioned bijection $\Psi$ that for $1\leq k\leq n$,

Thus,

by Theorem 1.4. We have the following recurrence relation for $I_{n, k}$.

Theorem 6.1. We have $I_{1, 1} = 1$ and

Proof. Let $\mathfrak{I}_{n, k}: = \{e\in \mathfrak{I}_n(021):{\mathsf{izero}}(e) = k\}$. For each inversion sequence $e\in \mathfrak{I}_n(021)$, let $\delta(e) = (\bar e_2, \bar e_3, \ldots, \bar e_n)\in \mathfrak{I}_{n-1}(021)$ with $\bar e_i = e_i-\chi(e_i>0)$ for $2\leq i\leq n$. The mapping $\delta: \mathfrak{I}_n(021)\rightarrow \mathfrak{I}_{n-1}(021)$ is surjective. To see (50), for any $e\in \mathfrak{I}_{n-1}(021)$ with ${\mathsf{izero}}(e) = k$, there are exactly $2^{k-1}$ preimages of $e$ in $\mathfrak{I}_{n, 1}$ under $\delta$, because

● each of the $k$ initial zeros of $e$, except for the first zero, can be either $0$ or $1$ in its preimages;

● but all zeros after the first positive entry of $e$, must remain zeros in its preimages, to guarantee that they are $021$-avoiding.

Recursion (51) follows from similar reasoning.

6.2.   Proof of Theorem 1.4

We will prove Theorem 1.4 by showing that the generating functions for both sides of (2) satisfy the same algebraic functional equation. We begin with the calculation of the generating function for the right-hand side of (2):

For any $e = (e_1, e_2, \ldots, e_n)\in \mathfrak{I}_n(021)$, we always attach $e_{n+1} = n$ to the end of $e$. Let ${\mathsf{da}}(e): = |\{1< i\leq n: e_{i-1}<e_i<e_{i+1}\}|$ be the number of double ascents of $e$. Since the bijection $\Psi: \mathfrak{I}_n(021)\rightarrow{\mathfrak{S}}_n(2413, 4213)$ transforms the set-valued statistics ${\mathrm{ASC}}$ to ${\mathrm{DES}}$, we have

Lemma 6.2. We have the algebraic functional equation for $G: = G(t, x, y;z)$:

where

Proof. Let ${\tilde {\mathfrak{I}}}_n(021)$ be the set of pairs ${\mathfrak{a}} = (e, \phi)$, where $e\in \mathfrak{I}_n(021)$ and $\phi$ is an arbitrary function from $[r]$ to $\{0, 1\}$ when ${\mathsf{izero}}(e) = r$. So ${\tilde {\mathfrak{I}}}_n(021)$ can be viewed as $021$-avoiding inversion sequences of length $n$ whose initial zeros are $2$-colored. Let

For each ${\mathfrak{a}} = (e, \phi)\in{\tilde {\mathfrak{I}}}_n(021)$ with ${\mathsf{izero}}(e) = r$, if ${\mathfrak{a}}\in{\tilde {\mathfrak{I}}}_n^{(0)}(021)$, then define

and

otherwise, ${\mathfrak{a}}\in{\tilde {\mathfrak{I}}}_n^{(1)}(021)$ and we define

and

The reason of defining these two statistics in this way will become transparent when we decompose $021$-avoiding inversion sequences. Let us introduce two generating functions

For convenience, we use the convention that ${\tilde {\mathfrak{I}}}_0^{(0)}(021)$, ${\tilde {\mathfrak{I}}}_0^{(1)}(021)$ and $\mathfrak{I}_0(021)$ contain only the empty inversion sequence.

Each $e = (e_1, \ldots, e_n)\in \mathfrak{I}_n(021)$ with $k = \min\{i\in[n]:e_{i+1} = i\}$ can be decomposed into a pair $(\hat e, {\mathfrak{a}})$, where $\hat e: = (e_2, e_3, \ldots, e_k)\in \mathfrak{I}_{k-1}(021)$ and ${\mathfrak{a}}: = (\tilde e, \phi)\in{\tilde {\mathfrak{I}}}_{n-k}^{(1)}(021)$ such that

● $\tilde e = (\tilde e_1, \tilde e_2, \ldots \tilde e_{n-k})$ with $\tilde e_{\ell} = e_{k+\ell}-k\cdot\chi(e_{k+\ell}>0)$ for $1\leq\ell\leq n-k$;

● and $\phi(i) = \chi(e_{k+i}>0)$ for $1\leq i\leq {\mathsf{izero}}(\tilde e)$.

This decomposition is reversible and satisfies

Turning the above decomposition into generating function yields

Similar decomposition as above for $2$-colored $021$-avoiding inversion sequences gives the system of functional equations

Eliminating $\tilde G_0$ gives the functional equation for $\bar G_1: = 1+\tilde G_1$:

On the other hand, solving (53) gives $\bar G_1 = \frac{G}{yz(1+G)}$. Substituting this expression into the above equation for $\bar G_1$ results in (52).

Next, we continue to compute the generating function for the left-hand side of (2):

This will be accomplished by applying Stankova's block decomposition [29] (see also [23]) of separable permutations that we now recall.

Lemma 6.3 (Stankova [29]). A permutation $\sigma\in{\mathfrak{S}}_n$ is a separable permutation (i.e. avoids $2413$ and $3142$) if and only if:

(i) $\sigma$ is of the form (positions of the blocks)

where $A_1<A_2<\cdots<A_k$ and $B_1>B_2>\cdots >B_l$ are blocks with respect to $n$.

(ii) The elements in any block form a permutation that avoids both $2413$ and $3142$.

See Fig. 2 for a transparent illustration of this lemma. Condition (ii) is clear, while condition (i) is equivalent to saying that $n$ is not an element of any subsequence of $\sigma$ that is order isomorphic to $2413$ or $3142$. Note that in the block decomposition, the minimal block can appear on either side of $n$. For example, compare the block decompositions of $259867431$ and $143867952$.

For convenience, we need to introduce two variants of the double descents. Let

where $\pi(0) = 0$ and $\pi(n+1) = +\infty$, and

where $\pi(0) = +\infty$ and $\pi(n+1) = 0$. Let us introduce

and

Set $B = B(y;z): = \frac{yz}{1-yz}$ and $\tilde L: = L-B$, where $B(y;z)$ enumerates identity permutations by length and ${\mathsf{iar}}$.

Lemma 6.4. Let $S_1 = S|_{y = 1}$ and $L_1 = L|_{y = 1}$. We have the system of functional equations

Proof. The first three equations of (54) were proved by Wang [30]. We begin with the proof of the fifth equation in (54) by writing $S$ as an expression in $L$ and $R$. By Lemma 6.3, every permutation $\pi\in{\mathfrak{S}}_n(2413, 3142)$ has block decomposition

where $A_1<A_2<\cdots<A_k$ and $B_1>B_2>\cdots >B_l$ are blocks with respect to $n$. We distinguish three cases according to the pair $(k, l)$:

$1)$ $(k, l) = (j, j)$ ($j\geq1$). Permutations in this case contribute to $S$ the generating function

$2)$ $(k, l) = (j+1, j)$ ($j\geq0$), and thus $1\in A_1$. Permutations in this case contribute to $S$ the generating function

$3)$ $(k, l) = (j, j+1)$ ($j\geq0$), and thus $1\in B_l$. Permutations in this case contribute to $S$ the generating function

Summing over all the above cases gives the fifth equation of (54). The fourth equation of (54) is obtained by writing $L$ as an expression of $L$, $R$ and $S_1$ via the same block decomposition, the details of which are omitted due to the similarity.

We are ready to verify Theorem 1.4.

Proof of Theorem 1.4. We aim to verify that $S$ satisfies the same functional equation as $G$ in (52). From the first two equations of (54) we see that $L_1$ and $R$ are rational fractions in $S_1$. Thus, in view of the fourth equation of (54), $\tilde L$ is also a rational fraction in $S_1$. Consequently, by the fifth equation of (54), $S$ is a rational fraction in $S_1$ as well. Plugging the expressions for $L_1$, $R$ and $\tilde L$ into the fifth equation of (54) for $S$ and factoring out (using Maple) the rational fraction

where $c_2$ and $c_3$ are defined in Lemma 6.2, we see the factor $tS_1^3+tzS_1^2+(z+txz-1)S_1+z$ appears in the denominator (the resulting rational fraction is too long to be included here). This factor is zero due to the third equation of (54), which proves that $S$ satisfies the same functional equation as $G$ in (52). This completes the proof of Theorem 1.4.

7.   Conclusion

In this paper, we launch a systematic study of the Wilf-equivalence refined by two permutation statistics, namely ${\mathsf{comp}}$, the number of components, and ${\mathsf{iar}}$, the length of the initial ascending run, for all patterns (resp. pairs of patterns) of length $3$. The results are summarized in Table 1 (resp. Table 2), where the trivariate generating functions ${\mathfrak{S}}(P)^{{\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}}(t, r, p;z)$ are supplied as well. In the cases where the pair $({\mathsf{iar}}, {\mathsf{comp}})$, together with other set-valued statistics, is symmetric over certain class of pattern-avoiding permutations, we construct various bijections to prove them (see e.g. Theorems 3.2, 3.12, 3.14, and 4.1). On the other hand, our proof of the result concerning separable permutations (see Theorem 1.4) is algebraic, and can hardly be called simple. Therefore, a direct bijection from ${\mathfrak{S}}_n(2413, 3142)$ to ${\mathfrak{S}}_n(2413, 4213)$ that preserves the statistics ${\mathsf{des}}$, ${\mathsf{dd}}$ and ${\mathsf{iar}}$ is much desired.

In view of Lemmas 2.5 and 5.4, we pose the following open problem about a set-valued extension of Lemma 2.5 for further investigation.

Problem. Let ${\mathrm{ST}}$ be a totally $\oplus$-compatible set-valued statistic. Let $P$ be a set of indecomposable patterns. Is it true that

In particular, we suspect that the equivalence above holds when ${\mathrm{ST}}$ is the statistic ${\mathrm{LMAX}}$.

Conjecture 2. Let $P$ be a set of indecomposable patterns. Then

It is our hope, that the results presented and conceived (see also Conjecture 1) here, would attract more people to work on Wilf-equivalences refined by Comtet statistics, or to unearth and study new Comtet statistics in general.

Acknowledgments

The authors thank the anonymous referees for their valuable comments and suggestions. Part of this work was initiated at the Research Center for Mathematics and Interdisciplinary Sciences at Shandong University. The authors would like to thank the center for the excellent working condition and the hospitality extended during their stay.