1.
Introduction
Let [n]:={1,2,…,n} be the set of the first n positive integers, and denote Sn the symmetric group consisting of all bijections from [n] to itself. A permutation π=π(1)⋯π(n)∈Sn is said to avoid the permutation (or pattern) σ=σ(1)⋯σ(k)∈Sk, k≤n, if and only if there is no subsequence π(j1)π(j2)⋯π(jk) with j1<j2<⋯<jk, such that π(ja)<π(jb) if and only if σ(a)<σ(b) for all 1≤a<b≤k. Otherwise, we say that the permutation π contains the pattern σ.
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 W a set of permutations, we write W(P) for the set of all permutations in 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∼Q, if |Sn(P)|=|Sn(Q)| for all positive integers n.
In this paper, we will restrict ourselves to the case where |P|=|Q|≤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 N:={0,1,2,…}. A set-valued statistic on S is a function from S to the set of finite subsets of N. Given a permutation π∈Sn, we mainly consider the set-valued statistic
called the descent set of π, and two statistics
called the descent number and the initial ascending run of π, respectively. Clearly, iar(π) can also be interpreted as the position of the leftmost descent of π, which indicates that iar is determined by DES. It should be noted that iar was also called lir, meaning "leftmost increasing run", in the literature (see e.g. [7]). The statistic des is known as an Eulerian statistic since its distribution over Sn is the n-th Eulerian polynomial
Another statistic highlighted in our study is comp(π), which can be introduced as
It is equal to the maximum number of components (see [1,7,8]) in an expression of π as a direct sum of permutations. For instance, comp(312465)=3, the three components being 312, 4, and 65 and 312465=312⊕1⊕21 (see Sect. 2.2 for the definition of direct sum ⊕). The statistic 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 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 iar and comp are not equidistributed over S4. Nonetheless, two of the authors [18] proved that 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 st on Sn, we say two sets of patterns P and Q are st-Wilf-equivalent, denoted as P∼stQ, if for all positive integers n, we have
meaning that for a fixed value of st, there are as many preimages in Sn(P) as those in Sn(Q). Note that by their definitions, P∼DESQ immediately implies P∼iarQ and P∼desQ, 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∼(DES,comp)Q and |Sn(P)DES,comp|=|Sn(Q)DES,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 π∈Sn, we introduce
the set of values and positions of the left-to-right maxima of π, respectively. The sets of values/positions of the left-to-right minima, the right-to-left maxima and the right-to-left minima of π can be defined and denoted similarly if needed. We use lowercase letters to denote the cardinality of these sets, so for example, LMIN(π) is the set of values of the left-to-right minima of π and lmin(π) is the corresponding numerical statistic. We will also consider the set of descent bottoms of π
which is another set-valued extension of des different from DES.
The first one of our main results concerns a single pattern of length 3.
Theorem 1.1. For every n≥1,
(i) the two triples (LMAX,iar,comp) and (LMAX,comp,iar) have the same distribution over Sn(321);
(ii) the two quadruples (LMAX,DESB,iar,comp) and (LMAX,DESB,comp,iar) have the same distribution over Sn(312);
(iii) the quadruples (LMAX,LMIN,iar,comp) and (LMAX,LMIN,comp,iar) have the same distribution over Sn(132).
The result on the symmetry of (comp,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 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 (comp,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 Sn(2413,3142) that preserves the pair of set-valued statistics (LMAX,DESB) but exchanges the pair (comp,iar). Consequently,
where xS:=∏i∈Sxi and yS:=∏i∈Syi for any subset S⊆[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 iar, combined with 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 γ-positivity interpretation for separable permutations [17,23] due to Zeng and the first two authors that we review below.
Recall that a polynomial in R[t] of degree n is said to be γ-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 γ-positive; see the comprehensive survey by Athanasiadis [2]. One typical example is the Eulerian polynomials
where Γn,k is the set of permutations in Sn with k descents and without double descents. Here an index i∈[n] is called a double descent of a permutation π∈Sn if π(i−1)>π(i)>π(i+1), where we use the convention π(0)=π(n+1)=0. The number of double descents of π will be denoted as dd(π). 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)∼des(2413,4213) (see [24,Thm. 5.1]), and that the γ-coefficient of the descent polynomial over (2413,4213)-avoiding permutations is similarly given by |Γ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≥1,
Theorem 1.4 refines Wang's equidistribution [30,Thm. 1.5] by the Comtet statistic 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 (des,iar,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 iar- or comp-Wilf equivalences for these patterns is given. Moreover, our attempt to characterize the pattern pairs of length 4 which are (iar,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 (iar,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 π∈Sn, there are three fundamental symmetry operations on π:
● its reversal πr∈Sn is given by πr(i)=π(n+1−i);
● its complement πc∈Sn is given by πc(i)=n+1−π(i);
● its inverse π−1∈Sn, is the usual group theoretic inverse permutation.
One thing we would like to point out, before we barge into classifying iar-Wilf-equivalences for various patterns, is that by taking 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 π, when n≥2. For the classical Wilf-equivalence, these symmetries reduce the number of possible equivalence classes considerably, since for example, π avoids 213 if and only if πr avoids 312. This fact about the statistic iar explains, at least partially, the following observations.
Observation 1. 1. The iar-Wilf-equivalence is less likely to be found than the Wilf-equivalence.
2. When 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 comp behaves better under these three elementary operations.
Observation 2. The two mappings π↦(πr)c and π↦π−1 both preserve the statistic 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 des,iar,comp, and variable z, and when the pattern set P is clear from the context, we also suppress P to write S(t,r,p). In most cases the variant ˜S(t,r,p):=(S(t,r,p)−1)/rpz of this generating function yields more compact expressions (see Tables 1 and 2). Let Mn(P):=Mn(P;iar,comp) be the n×n matrix, whose entry at the k-th row and the ℓ-th column is the number of permutations π in Sn(P) with iar(π)=k and comp(π)=ℓ. Let st be a permutation statistic, we can then refine Mn(P) as Mn(P)=∑iMst=in(P), so that the (k,ℓ)-entry of Mst=in(P) counts permutations π such that st(π)=i for a fixed integer i. This definition extends to set-valued statistics and multiple statistics in a natural way. So for instance, MLMAX=S,des=in(P) is the n×n matrix, whose (k,ℓ)-entry is the number of permutations π in Sn(P) with LMAX(π)=S, des(π)=i, iar(π)=k and comp(π)=ℓ.
We also need the following operations on permutations.
Definition 2.1. For a word w over 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 π∈Sn, the deletion of i, for each i∈[n], is the map that deletes i from π, and reduces the derived word to a permutation, denoted as deli(π)∈Sn−1. Similarly, the insertion of i at place k, for each i,k∈[n+1], is defined to be the map that increases all letters j≥i in π by 1, and inserts i between π(k−1) and π(k) to get a new permutation, denoted as insi,k(π)∈Sn+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 π⊕σ and the skew sum π⊖σ, of π∈Sk and σ∈Sl, are permutations in Sk+l defined respectively as
and
For instance, we have 123⊕21=12354 and 123⊖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 ⊕ and ⊖ repeatedly.
Definition 2.3. A nonempty permutation which is not the direct sum of two nonempty permutations is called indecomposable. Let In denote the set of all indecomposable permutations of length n. Any permutation π with comp(π)=k can be written uniquely as π=τ1⊕τ2⊕⋯⊕τk, where each τi is indecomposable. We call this decomposition the direct sum decomposition of π. Let idn denote the identity permutation of length n. A statistic st is called totally ⊕-compatible if st(π)=∑ki=1st(τi) and is called partially ⊕-compatible if st(π)=∑li=1st(τi), where l=min({i:τi≠id1}∪{k}).
For instance, des and comp are totally ⊕-compatible, while iar is partially ⊕-compatible. We emphasize here that total ⊕-compatibility does not imply partial ⊕-compatibility.
Let P be a collection of patterns and (st1,st2,…) be a sequence of permutation statistics. Let us introduce two generating functions with respect to (st1,st2,…) 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 comp.
Lemma 2.4. Let (st1,st2,…,st′1,st′2,…) be a sequence of statistics such that sti is totally ⊕-compatible and st′i is partially ⊕-compatible for each i. Let P and Q be two collections of indecomposable patterns.
1. We have the following functional equation:
where w=ztst1(id1)1tst2(id1)2⋯t′1st′1(id1)t′2st′2(id1)⋯ is the generating function for id1, and
are the generating functions with respect to (comp,st1,…,st′1,…) and (st1,…,st′1,…), respectively. In particular, IP(t,1):=IP(t1,…,1,…;z).
2. If P∼(st1,st2,…,st′1,st′2,…)Q, then P∼(comp,st1,st2,…,st′1,st′2,…)Q holds as well. In particular, if P∼Q, then P∼compQ.
Proof. Note that if σ is an indecomposable pattern and π=τ1⊕τ2⊕⋯⊕τk, then
Therefore, with respect to totally ⊕-compatible statistics t, the weight of π that contributes to the generating function FP(q) is the product of the weights of τ1,…,τk. But when partially ⊕-compatible statistics t′ are involved, further analysis is needed. Among these k indecomposable components, suppose the first i are trivial (i.e., id1) with weight w, the (i+1)-th component is nontrivial thus generated by IP(t,t′)−w, and the remaining k−i−1 components do not affect those partially ⊕-compatible statistics t′, thus each is generated by IP(t,1). The discussion above amounts to
which becomes 4 after simplification.
In view of 4, the following three statements are equivalent:
(i) FP(1)=FQ(1), namely P∼(st1,st2,…,st′1,st′2,…)Q.
(ii) IP(t,t′)=IQ(t,t′).
(iii) FP(q)=FQ(q).
For example, to see that (i) implies (ii), we first set t′i=1 for all i to obtain that FP(1)=FQ(1) implies IP(t,1)=IQ(t,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 st with comp over Sn(P), implies the seemingly stronger result that the joint distribution (st,comp) is symmetric over Sn(P). This result is somewhat surprising.
Lemma 2.5. Let P be a collection of indecomposable patterns. Let st′ be a partially ⊕-compatible statistic such that st′(id1)=1 and (st1,st2,…) be a sequence of totally ⊕-compatible statistics. If |Sn(P)st′,st1,st2,…|=|Sn(P)comp,st1,st2,…|, then
In particular, if st′ is a Comtet statistic over Sn(P), then (st′,comp) is a symmetric pair of Comtet statistics over Sn(P).
Proof. Let FP(r,s):=FP(r,s,t1,t2,…;z) and IP(s):=IP(s,t1,t2,…;z) be the generating functions with respect to (comp,st′,st1,st2,…) and (st′,st1,st2,…), respectively. By the relationship 4, we have
where w=ztst1(id1)1tst2(id1)2⋯. Since FP(1,s)=FP(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 τ of length 3 and complete two tasks:
1) Show the symmetry of the Comtet pair (iar,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: ξ (Theorem 3.2), α and β (Theorem 3.4), ψ (Theorem 3.6), φ (Theorem 3.12), and θ (Theorem 3.14).
2) Compute the trivariate generating function S(τ)des,iar,comp(t,r,p), which leads to the full iar- and comp-Wilf-equivalence classification. A snapshot of these results is presented in Table 1, where MT 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 iar-Wilf-equivalence classes:
While the comp-Wilf-equivalence classes are:
3.1. Symmetric classes
For the three patterns 312, 321 and 132, the distributions of iar and 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⊕21, we need to construct an involution φ on Sn(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 S3, 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 Sn(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 π∈Sn, let
be the position of the last descent of π. Recall the boldface notation xS defined in Theorem 1.3.
Theorem 3.1 (Rubey [27]). There exists an involution on Sn(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 π↦(π−1)rc. Notice that for each π∈Sn, we have the relationships
where ˉS:={n+1−i:i∈S} for any subset S⊆[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 ω, on Sn(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 π↦(π−1)rc, we obtain another bijection on Sn(321), say ˜ω, that yields Theorem 1.1 (i) as well. Interestingly, these two bijections ω and ˜ω turn out to be different from each other, although they do agree for permutations in Sn(321) when n≤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∼comp312 since 321∼312. We have the following refinement.
Theorem 3.2. For each n≥1, there exists a bijection ξ, mapping each π∈Sn(321) onto σ:=ξ(π)∈Sn(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 ⋄ that stands for an empty slot, which we introduce now.
Definition 3.3. Given a nonempty set S={s1,…,sk}⊆Z>0 with s1<⋯<sk, and a weak composition c=(c1,…,ck) of sk−k, we form the word
It is said to be an admissible word with respect to S and c, if for 1≤i≤k,
Let AWn denote the set of all admissible words of length n.
We also need to introduce the counterparts on AWn of the quadruple statistics in (8). For each w:=wS,c∈AWn, let ics(w) denote the number of initial consecutive letters from S in w, equ(w) denote the number of times the condition (*) is satisfied with an equal sign, and SP(w) denote the set of positions (in w) of letters from S. For example, if w=235⋄7⋄⋄1012⋄13⋄⋄ with S={2,3,5,7,10,12,13}, then ics(w)=3, equ(w)=2, SP(w)={1,2,3,5,8,9,11}.
Theorem 3.4. There exist two bijections α:Sn(321)→AWn and β:Sn(312)→AWn, such that for any π∈Sn(321) and σ∈Sn(312), we have
where wS,c=α(π) and wT,d=β(σ).
Proof. Since the constructions for the two bijections α and β are almost the same (the only difference lies in their inverses), we will give details mainly for α. For each π∈Sn(321), suppose
Let c=(c1,…,ck), with ch=ih+1−ih−1, for 1≤h≤k−1, ck=n−ik. 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 π. Now we define α(π):=wS,c. Note that π(i1),…,π(ik) are the left-to-right maxima of π, so we can verify the condition (*) holds for S and c, therefore α is a well-defined map from Sn(321) to AWn. The map β is defined analogously, only that now the preimage is a 312-avoiding, rather than 321-avoiding permutation. Now we show both α and β are bijections by constructing their inverses. Take a word wS,c∈AWn, we replace all the ⋄'s from left to right with the smallest unused letter in [n]∖S. This results in a 321-avoiding permutation, say ˆπ. On the other hand, if we replace all the ⋄'s from left to right with the largest unused letter in [n]∖S, keeping letters from S the left-to-right maxima, we will end up with a 312-avoiding permutation, say ˆσ.
It should be clear that
Now set α−1(wS,c)=ˆπ (resp. β−1(wS,c)=ˆσ). Evidently,
so α and β are indeed bijections that transform the quadruple statistics as shown in (9) and (10).
Proof of Theorem 3.2. Simply set ξ=β−1∘α, and (8) follows immediately from (9) and (10).
Remark 2. When composed with the complement map, our bijection ξ is equivalent to Simion and Schmidt's [28] bijection from Sn(123) to Sn(132). This bijection is also called the Knuth–Richards bijection by Claesson and Kitaev [7], see also [12].
In view of (9), the pair (ics,equ) on admissible words corresponds to the pair (iar,comp) on 321-avoiding permutations, so Rubey's Theorem 3.1 tells us that their distributions are jointly symmetric over AWn. Note that Rubey's proof was via an involution on Dyck paths. We are able to construct an invertible map ψ over the set of admissible words. To facilitate the description of ψ, we need the following definition.
Definition 3.5. Given an admissible word wS,c with S={s1,…,sk} and c=(c1,…,ck), the index i, 1≤i<k is said to be critical for w, if
For the previous example w=235⋄7⋄⋄1012⋄13⋄⋄, we see the indices 2,3 and 6 are critical for w. Let AWn,a,b denote the set of admissible words w:=wS,c∈AWn such that ics(w)=a, equ(w)=b and s1>1, where s1 is the smallest letter in S.
Theorem 3.6. For 1<a≤n and 1≤b<n, there exists a bijection ψ from AWn,a,b to AWn,a−1,b+1, such that for each wS,c∈AWn,a,b, if ψ(wS,c)=vT,d, then we have S=T.
Proof. Take any w:=wS,c∈AWn,a,b with S={s1,…,sk} and c=(c1,…,ck), we explain how to produce an admissible word v:=vS,d such that ics(v)=ics(w)−1 and equ(v)=equ(w)+1. Since ics(w)=a≥2, we see c1=c2=⋯=ca−1=0 and ca>0. Find the smallest ℓ≥a−1 such that the index ℓ is critical for w. Note that s1>1 guarantees the existence of such an ℓ. Let d=(d1,⋯,dk) be defined as
We denote v:=vS,d the admissible word with respect to S and d, and set ψ(w)=v. It can be checked that ∑ki=1ci=∑ki=1di=sk−k and ∑ℓi=1di=sℓ−ℓ, hence equ(v)=equ(w)+1 as desired. Also ics(v)=ics(w)−1=a−1 since now d1=⋯=da−2=0 and da−1=ca>0.
All it remains is to show that ψ is invertible. To this end, for each v:=vS,d∈AWn,a−1,b+1, find the smallest integer ℓ such that ∑ℓi=1di=sℓ−ℓ. Note that since equ(v)=b+1≥2, s1>1 and d1=⋯=da−2=0, we must have a−1≤ℓ<k, and ℓ being the smallest means dℓ>0. Now let c=(c1,…,ck) be defined as
It is routine to check that w:=wS,c is the desired preimage so that ψ(w)=v, ics(w)=ics(v)+1, and equ(w)=equ(v)−1.
The following result is the restatement of Theorem 1.1 (i) and (ii).
Corollary 3.7. For n≥1, the two triples (LMAX,iar,comp) and (LMAX,comp,iar) have the same distribution over Sn(321); while over Sn(312), the two quadruples (LMAX,DESB,iar,comp) and (LMAX,DESB,comp,iar) have the same distribution.
Proof. For each permutation π∈Sn(321) with π(1)>1, we find a unique permutation ρ∈Sn(321) such that
If iar(π)=comp(π), then simply take ρ=π. Otherwise we assume iar(π)=comp(π)+k for some k≠0, let
Combining Theorem 3.6 with (9), we verify that
as desired. Now both α and ψ are bijections, so π and ρ are in one-to-one correspondence. On the other hand, for each π∈Sn(321) with π(1)=1, we see ν:=del1(π)∈Sn−1(321) satisfies iar(ν)=iar(π)−1, comp(ν)=comp(π)−1, and LMAX(ν) is the set obtained from decreasing each number in LMAX(π)∖{1} by 1. This means we can use induction to finish the proof of the result for Sn(321).
Finally, applying the bijection β instead of α gives us the result for Sn(312). To see why we can include DESB to have a quadruple in this case, simply observe that for each permutation σ∈Sn(312), LMAX(σ)∪DESB(σ)=[n].
For most of our calculations of the generating function 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 σ∈Sn. A maximal consecutive subset of [n], all of whose elements appear on the same side of n (resp. 1) in σ, 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 χ(S)=1 if the statement S is true, and χ(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 Mn(P) or Mst=in(P) is a Hankel matrix. This not only implies that (iar,comp) is symmetric over Sn(P), but also facilitates our calculation of the generating function S(P)des,iar,comp(t,r,p;z). We elaborate on the latter point with the next lemma.
Lemma 3.8. Suppose M=(mij)1≤i,j≤n is a Hankel matrix such that mij=0 when i+j≥n+2. Let M(x,y):=∑1≤i,j≤nmijxiyj and N(x):=∂M∂y|y=0=∑1≤i≤nmi1xi 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 xiy+xi−1y2+⋯+xyi=xy(xi−yi)/(x−y) for each 1≤i≤n, we have
as desired.
Recall the Narayana polynomial Nn(t):=∑π∈Sn(τ)tdes(π) (τ=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 (des,iar,comp) over Sn(312) is given by
Proof. Conditioning on π(1), we claim that (abbreviating S(312)des,iar,comp(t,r,p) to S(t,r,p))
where
Indeed, the first summand 1 in (14) corresponds to the empty permutation, and the second to those with π(1)=1. As for the third summand, we consider permutations π with π(1)>1. Now Eq. (10) and Theorem 3.6 tell us that for a given 1∉S⊆[n], the matrix MLMAX=Sn(312):=(mij)1≤i,j≤n is Hankel. Note that iar(π)=n only for π=idn but we require that π(1)>1, so using the fact that the matrix is Hankel, we see mij=0 when i+j≥n+1. Consequently, Lemma 3.8 is applicable. Lastly, as we have already noted in the proof of Corollary 3.7, each permutation σ∈Sn(312) satisfies LMAX(σ)∪DESB(σ)=[n]. This means in particular that the statistic des takes the same value for all permutations enumerated by MLMAX=Sn(312), justifying the variable t in (15).
Next, plugging (15) into (14) yields
Setting p=1 in (16), solving for ˜S(t,r,0) and then plugging back into (16) gives us
It remains to calculate ˜S(t,r,1). Every nonempty 312-avoiding permutation π has the block decomposition π=A1B such that A and B are both 312-avoiding blocks with A<B. We consider the following two cases:
● A=∅, i.e. π(1)=1. This case contributes the generating function rzS(t,r,1).
● A≠∅. This case contributes the generating function (S(t,r,1)−1)tzS(t,1,1).
Summing up these two cases and noting that S(t,1,1)=N, we deduce that
Solving for ˜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 (des,iar,comp) over Sn(321) is given by
Proof. Recently, Fu, Han and Lin [15,Lemma 4.5] generalized (18) to
For convenience, let I(r):=I321(t,r) be the generating function over In(321) with respect to (des,iar). Since 321 is indecomposable, des is totally ⊕-compatible and iar is partially ⊕-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 (iar,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 π∈Sn(132), we have
1. For 2≤i≤n, π(i) is a descent bottom of π if and only if it is a left-to-right minimum of π, i.e., LMIN(π)=DESB(π)∪{π(1)}.
2. When read from left to right, the values of the left-to-right maxima of π form a sequence of consecutive integers π(1),π(1)+1,π(1)+2,…,n.
3. The first k=iar(π) letters of π equal π(1),π(1)+1,…,π(1)+k−1.
4. Provided k=comp(π)≥2, the last k−1 letters of π equal n−k+2,…,n.
The next theorem strengthens Theorem 1.1 (iii).
Theorem 3.12. For all positive integers n, given any two subsets S,T⊆[n], the matrix MLMAX=S,LMIN=Tn(132) is Hankel. Consequently, the distribution of the quadruple (LMAX,LMIN,iar,comp) is equal to that of (LMAX,LMIN,comp,iar) over Sn(132). In terms of generating function, we have
In particular, we have
Proof. We begin by noting that for each π∈Sn(132), its initial ascending run consists of consecutive numbers, and, unless π is indecomposable, we have π(n)=n. Now if iar(π)=comp(π)=1, i.e., π is an indecomposable 132-avoiding permutation with π(1)>π(2), then it is counted by the top-left entry of MLMAX=S,LMIN=Tn(132) for certain S and T. Similarly, if iar(π)=comp(π)=n, then we must have π=idn and it corresponds to the bottom-right entry 1 of MLMAX=[n],LMIN={1}n(132). Otherwise, for the given subsets S,T⊆[n], take any permutation π∈Sn(132) such that LMAX(π)=S, LMIN(π)=T, 2≤iar(π)≤n−1, and 1≤comp(π)≤n−2. We are going to pair π with a permutation σ∈Sn(132) via a bijective map φ, such that
i. π(i)=σ(i) for 1≤i≤iar(π)−1.
ii. LMAX(σ)=LMAX(π)=S, and LMIN(σ)=LMIN(π)=T.
iii. iar(σ)=iar(π)−1, and comp(σ)=comp(π)+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 MLMAX=S,LMIN=Tn(132) is Hankel as claimed. Now for any permutation π∈Sn(132) with iar(π)=j>comp(π)=k, we see τ:=φj−k(π) is a permutation in Sn(132) with
Pairing permutations in this way leads to (21).
Finally, by Proposition 3.11 (1) we have LMIN(π)∖{π(1)}=DESB(π). Furthermore, item i above implies in particular that π(1)=σ(1), combining this with LMIN(π)=LMIN(σ) we obtain (22).
Theorem 3.13. We have
Proof. The proof is analogous to that of Theorem 3.9. Noting that Mdes=kn(132) is Hankel for any fixed integer 0≤k≤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 ˜S(t,r,p) we have
Plugging in p=1 we have
Now solve for ˜S(t,r,0) and substitute the result back in (24) we get
Next, we decompose each 132-avoiding permutation π as π=AnB, 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 iar and comp on each of these classes are different. We are content with deriving their joint generating functions with des, and addressing a conjugate relation between Mn(213) and Mn(231).
Patterns 213 and 231
Theorem 3.14. For every n≥0, there exists a bijection θ:Sn(213)→Sn(231), such that for π∈Sn(213) and σ:=θ(π)∈Sn(231), we have π(1)=σ(1) and
In particular, the matrices Mn(213) and Mn(231) are conjugation of each other.
Proof. We define θ recursively. For n=0,1,2, θ:Sn(213)→Sn(231) is taken to be the identity map. Now suppose θ has been defined for all k<n(n≥3), then take any π∈Sn(213), we can uniquely decompose π=π(1)AB with A>π(1)>B. Let μ=red(A) and ν=B, then we see that delπ(1)(π)=μ⊖ν, where both μ and ν are 213-avoiding, possibly empty permutations. Let
The following facts can be readily verified.
1.σ∈Sn(231);
2.σ(1)=π(1);
3.des(σ)=χ(ν≠∅)+des(θ(ν))+des(θ(μ))=des(π);
4.comp(σ)=1+comp(θ(μ))=1+iar(μ)=iar(π);
5.iar(σ)=1+χ(ν=∅)⋅iar(θ(μ))=1+χ(ν=∅)⋅comp(μ)=comp(π).
So we see σ is the desired image of π, and the proof is now completed by induction.
The equidistribution between (des,iar,comp) over Sn(213) and (des,comp,iar) over Sn(231) could also be drawn from comparing the following generating functions.
Theorem 3.15. We have
Proof. We begin with the calculation of ˜S(213)des,iar,comp(t,r,p). Each π∈Sn(213) can be decomposed as π=π(1)AB, where A>π(1)>B are 213-avoiding blocks, possibly empty. For n≥2, we consider the following three cases:
● A=∅, B≠∅, contributing the generating function trpz(S(t,1,1)−1).
● A≠∅, B=∅, contributing rpz(S(t,r,p)−1).
● A≠∅, B≠∅, contributing trpz(S(t,r,1)−1)(S(t,1,1)−1).
Summing up these three cases and noting that S(t,1,1)=N, we deduce that
Now we plug in p=1 and solve for S(t,r,1), then plug it back to deduce (26) after simplification.
Decomposing each π∈Sn(231) as π=π(1)AB with A<π(1)<B, and calculating along the same line, we can establish (27) as well.
Pattern 123
For π∈Sn(123), clearly iar(π)≤2 and comp(π)≤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 π∈Sn(123) with iar(π)=1 and comp(π)=2, we can decompose it as π=AB, where A<B are both decreasing subsequences with |A|≥2 and |B|≥1. On the other hand, if π∈Sn(123) and iar(π)=2, then we must have π(2)=n, and we calculate the two cases π(1)>π(3) and π(1)<π(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≥2, let S∗n(123):={π∈Sn(123):des(π)=n−2}, then we have
In particular, the distribution of (iar,comp) is symmetric over S∗n(123), and the number of permutations π∈S∗n(123) with iar(π)=comp(π)=1 is the sequence A095264 in [25].
Proof. To calculate the generating function in (31), we need to extract the coefficients of tn−2zn in S(123)des,iar,comp(t,r,p) for each n≥2. For rpzA(t,p), the term (p−1)trpz3(1−tz)2 expands to terms all of the form tn−2zn, so we simply set t=1 to get (p−1)rpz3(1−z)2, while for the term rp(1−tz)(S(t,1,1)−1)1−tz+z, we substitute tz for z, and 1/t for t in
then take partial derivative ∂/∂t and let t=0 to obtain 2rpz3(1−z)2(1−2z). A similar approach yields the coefficients from r2pzB(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=(τ1,τ2) be a pair of patterns of length 3, so there are 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 patterns was done by Simion and Schmidt [28]. There are three Wilf-equivalent classes, which further split into eleven -Wilf-equivalent subclasses: the class enumerated by splits into classes
the class enumerated by splits into classes
and the terminating (i.e., enumerated by when ) class stays as a single class. For -Wilf-equivalences, the class enumerated by splits into classes
and the class enumerated by splits into classes
All the above refined Wilf-equivalences can be easily proven by setting , and (or ) in the generating functions listed in Table 2.
4.1. Symmetric classes
For , the joint distribution of is symmetric for and over . We consider these four classes in this subsection.
Pattern pairs and
First note that if the pattern (resp. ) occurs in a permutation , then we can always find an occurrence of (resp. ) in with the role of "" played by a left-to-right maximum of . Now recall the bijection we construct in the proof of Theorem 3.12. For each , observe that (resp. ) if and only if (resp. ). This fact, combined with Theorem 3.12, immediately yields the following theorem.
Theorem 4.1. For all positive integers , given any two subsets , the matrix is Hankel, for . Consequently, the distribution of the quadruple is equal to that of over . 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 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 with contribute collectively to . On the other hand, every with can be uniquely decomposed as , where are two (possibly empty) blocks such that is decreasing and is - and -avoiding. We consider the following two cases.
● . This case contributes the generating function .
● . This case contributes .
Summing up all cases gives us
Set and solve to get
then plug this back into (34) and simplify, we get (32). The proof of (33) is simpler noting that for with the decomposition , both and are increasing if . The details are omitted.
Pattern pair
The first thing to notice is that for every , we must have or , and . 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
For every permutation , there are only five possible values for the triple , since -avoiding implies and , while both - and -avoiding forces . Now it suffices to enumerate each case separately.
● . There is a unique permutation for this case, which contributes to the generating function.
● . There is a unique permutation for this case, which contributes to the generating function.
● . Permutations in this case are of the form , where . Therefore this case contributes to the generating function.
● or . These two cases can be discussed similarly as the last case, and the contributions are and .
Summing up all cases above gives rise to
Theorem 4.4.
4.2. Asymmetric classes
For the remaining choices of , the distribution of over is not symmetric. However, we still observe some conjugative pairs as in Section 3.
Pattern pairs , and
Recall the two bijections, from Theorem 3.2, and from Theorem 3.14. Observe that
● if and only if .
● if and only if .
Then the following theorem is a quick corollary of Theorems 3.2 and 3.14.
Theorem 4.5. For each , the quadruple has the same distribution over and ; the distribution of the triple over is equal to that of over .
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 and . To prove (36), note that both patterns and are indecomposable, thus we can apply Lemma 2.4 to reduce the calculation to that of the generating function of over . But the indecomposable permutations in are precisely , thus . Plugging this back into (4) gives us (36). Finally, every permutation in must be of the form , yeilding the generating function . Applying (4) from Lemma 2.4 again, we derive (37) and complete the proof.
Pattern pairs and
For the same reason that the bijection from Theorem 3.14 preserves -avoidance, we have the following conjugate relation.
Theorem 4.7. For each , the distribution of the triple over is equal to that of over .
Next, note that each permutation either begins with , or ends with . 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
Note that each permutation can be decomposed as , where and are both increasing blocks, and is consisted of consecutive integers. Calculating the two cases and separately, we obtain the following theorem.
Theorem 4.9. We have
Pattern pair
Noting that both and are indecomposable patterns, we apply (4)
from Lemma 2.4 (1) to reduce the calculation to
Now any indecomposable must be of the form . Hence
with which we can deduce
Theorem 4.10.
Pattern pairs , , and
These four pattern sets all contain the pattern , hence and for each permutation in . We take similar approach as Theorem 3.16, or analyze the position of or in , 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 of length whose distribution matrix equals . The first few values of the symmetric matrices are:
The integer sequence formed by the entries in the upper-left corner of begins with
This sequence matches A010683 in the OEIS [25], a sequence that counts, among many combinatorial objects, dissections of a convex polygon with sides having a triangle over a fixed side (the base) of the polygon. This coincidence can be proved by comparing 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 ,
Consequently,
Proof. Since the patterns and are indecomposable, the equidistribution (38) is a consequence of Theorem 1.4 (with ) 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 . This is not true and it turns out that even is not equidistributed over and . 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 -Wilf equivalent to the class of separable permutations.
Theorem 5.2 ([24]). We have the refined Wilf-equivalences:
It should be noted that is not a Comtet statistic over . Computer program indicates that, among all permutation classes avoiding two patterns of length 4, the classes of and are the only two that are -Wilf equivalent to the class of separable permutations.
Theorem 5.3. We have . In particular,
Consequently,
In order to prove Theorem 5.3, we need a set-valued version of Lemma 2.4. For an integer and a set , let . A set-valued statistic is called totally -compatible if for each with each an indecomposable permutation of length ,
where . Note that the set-valued statistics , , and are all totally -compatible.
Lemma 5.4. Let be a sequence of totally -compatible set-valued statistics. Let and be two collections of indecomposable patterns. For , if has the same distribution over and , then so does .
Proof. Since (meaning or ) is a collection of indecomposable patterns, each -avoiding permutation is a direct sum of some smaller -avoiding permutations. Thus, it is sufficient to show that if is equidistributed over and for , then is equidistributed over and . We aim to prove this by induction on .
Obviously, the assertion is true for . Suppose that is equidistributed over and for . It follows that is equidistributed over and , as is a sequence of totally -compatible set-valued statistics. Now is also equidistributed over and and so is equidistributed over and . 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 is totally -compatible. The other two statements then follow immediately from Corollary 5.1.
Next we compute the generating function with respect to , where is a pattern pair in
Theorem 5.5. Let . Then,
where satisfies the algebraic functional equation
Proof. The functional equation (42) for the generating function of the descent polynomials over separable permutations was proved in [17]. Since the patterns and are indecomposable, is totally -compatible and is partially -compatible, Eq. (6) gives
where is the generating function with respect to . Since , 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 that are -Wilf equivalent to the class of separable permutations.
Conjecture 1. Let be a pair of patterns of length . Then, is -Wilf equivalent to if and only if is one of the following eleven pairs:
Moreover, if is one of the last five pairs (i.e., those in the second line above), then is -Wilf equivalent to .
Remark 4. In view of Lemma 2.4, the second assertion for the -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 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, and Conjecture 1 is true for .
In view of Lemma 5.4, to prove Theorem 5.6, it is sufficient to prove the refined Wilf-equivalence . We will prove this by showing a growth rule for -avoiding permutations and then comparing it with that of -avoiding permutations.
For and , let . Thus for example, . If , then introduce the set of available inserting values of as
Clearly, if , then for any , since the newly inserted letter, which appears at the end, can only play the role of '1' in a pattern or . Thus, for some . We will call the critical value of in the sequel. For example, we have .
We have the following growth rule for -avoiding permutations.
Lemma 5.7. Suppose with . Then,
Proof. For , the letters (if ) and appear before in and these three letters form a pattern or . Thus, . On the other hand, suppose , then we see and form a pattern or , if and only if and do. This means we have . Therefore is the critical value of and . Clearly, . This completes the proof of the lemma.
The definition of for a -avoiding permutation was introduced similarly in [24], where they proved the following growth rule. Note that for any , always contains and .
Lemma 5.8. (Lin and Kim [24,Lemma 5.3]). Suppose with
Then, for ,
We are ready to prove Theorem 5.6 by constructing the generating trees for both classes.
Proof of Theorem 5.6. Label each by , Lemma 5.7 then produces the rewriting rule:
This means that the initial permutation has label and all the -avoiding permutations derived from inserting a letter at the end of a -avoiding permutation labeled by , are exactly those with labels .
We can construct a generating tree (an infinite rooted and labeled tree) for -avoiding permutations by representing each permutation as a node on the tree using its label. More precisely, the root is labeled , and the children of a node labeled are those generated according to the rewriting rule 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 -th level of this tree are in one-to-one correspondence with elements of . Moreover, if a permutation is labeled by , and the unique path from the root to goes through , then
For instance, the second appearing in level corresponds to and we have . In other words, the distribution of over -avoiding permutations is completely determined by this generating tree.
It can be readily checked that Lemma 5.8 gives the same rewriting rule for -avoiding permutations, which in turn, produces for -avoiding permutations the identical generating tree as -avoiding permutations. This proves , 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 is an inversion sequence of length if for each . An inversion sequence is {\em-avoiding} if its positive entries are weakly increasing. Denote by the set of -avoiding inversion sequences of length . Kim and Lin [24]
● constructed a bijection which transforms the set-valued statistic to , where is the set of ascents of . In particular, together with the works in [10,17,23] we know
where ;
● proved combinatorially via the so-called modified Foata–Strehl action that
Recall that is the set of permutations in with descents and without double descents. Combining (1), (45) and (46) yields
for all . This identity was refined recently by Wang [30] as
where denotes the number of double descents of . Setting in (48) we recover (47).
Theorem 1.4 is a refinement of Wang's equidistribution (48) by the Comtet statistic . The three numerical statistics , and are all determined by the set-valued statistic , but is not -Wilf equivalent to . In spite of that, we still have the refined Wilf-equivalence , to our surprise. Our proof of Theorem 1.4 is purely algebraic, basing on Kim–Lin's bijection , a decomposition of -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 -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 , let be the number of initial zeros of . It follows from the aforementioned bijection that for ,
Thus,
by Theorem 1.4. We have the following recurrence relation for .
Theorem 6.1. We have and
Proof. Let . For each inversion sequence , let with for . The mapping is surjective. To see (50), for any with , there are exactly preimages of in under , because
● each of the initial zeros of , except for the first zero, can be either or in its preimages;
● but all zeros after the first positive entry of , must remain zeros in its preimages, to guarantee that they are -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 , we always attach to the end of . Let be the number of double ascents of . Since the bijection transforms the set-valued statistics to , we have
Lemma 6.2. We have the algebraic functional equation for :
where
Proof. Let be the set of pairs , where and is an arbitrary function from to when . So can be viewed as -avoiding inversion sequences of length whose initial zeros are -colored. Let
For each with , if , then define
and
otherwise, and we define
and
The reason of defining these two statistics in this way will become transparent when we decompose -avoiding inversion sequences. Let us introduce two generating functions
For convenience, we use the convention that , and contain only the empty inversion sequence.
Each with can be decomposed into a pair , where and such that
● with for ;
● and for .
This decomposition is reversible and satisfies
Turning the above decomposition into generating function yields
Similar decomposition as above for -colored -avoiding inversion sequences gives the system of functional equations
Eliminating gives the functional equation for :
On the other hand, solving (53) gives . Substituting this expression into the above equation for 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 is a separable permutation (i.e. avoids and ) if and only if:
(i) is of the form (positions of the blocks)
where and are blocks with respect to .
(ii) The elements in any block form a permutation that avoids both and .
See Fig. 2 for a transparent illustration of this lemma. Condition (ii) is clear, while condition (i) is equivalent to saying that is not an element of any subsequence of that is order isomorphic to or . Note that in the block decomposition, the minimal block can appear on either side of . For example, compare the block decompositions of and .
For convenience, we need to introduce two variants of the double descents. Let
where and , and
where and . Let us introduce
and
Set and , where enumerates identity permutations by length and .
Lemma 6.4. Let and . 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 as an expression in and . By Lemma 6.3, every permutation has block decomposition
where and are blocks with respect to . We distinguish three cases according to the pair :
(). Permutations in this case contribute to the generating function
(), and thus . Permutations in this case contribute to the generating function
(), and thus . Permutations in this case contribute to the generating function
Summing over all the above cases gives the fifth equation of (54). The fourth equation of (54) is obtained by writing as an expression of , and 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 satisfies the same functional equation as in (52). From the first two equations of (54) we see that and are rational fractions in . Thus, in view of the fourth equation of (54), is also a rational fraction in . Consequently, by the fifth equation of (54), is a rational fraction in as well. Plugging the expressions for , and into the fifth equation of (54) for and factoring out (using Maple) the rational fraction
where and are defined in Lemma 6.2, we see the factor 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 satisfies the same functional equation as 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 , the number of components, and , the length of the initial ascending run, for all patterns (resp. pairs of patterns) of length . The results are summarized in Table 1 (resp. Table 2), where the trivariate generating functions are supplied as well. In the cases where the pair , 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 to that preserves the statistics , and 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 be a totally -compatible set-valued statistic. Let be a set of indecomposable patterns. Is it true that
In particular, we suspect that the equivalence above holds when is the statistic .
Conjecture 2. Let 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.