Consecutive Patterns in Inversion Sequences II: Avoiding Patterns of Relations

Juan S. Auli and Sergi Elizalde Department of Mathematics Dartmouth College Hanover, NH 03755 USA

         juan.s.auli.gr@dartmouth.edu
         sergi.elizalde@dartmouth.edu

Abstract

Inversion sequences are integer sequences e = e_{1}e_{2} ⋯ e_{n} such that 0 ≤ e_{i} < i for each i. The study of patterns in inversion sequences was initiated by Corteel-Martinez-Savage-Weselcouch and Mansour-Shattuck in the classical (non-consecutive) case, and later by Auli-Elizalde in the consecutive case, where the entries of a pattern are required to occur in adjacent positions. In this paper we continue this investigation by considering consecutive patterns of relations, in analogy to the work of Martinez-Savage in the classical case. Specifically, given two binary relations R_{1}, R_{2} ∈ {≤, ≥, <, >, =, ≠}, we study inversion sequences e with no subindex i such that e_{i}R_{1}e_{i+1}R_{2}e_{i+2}. By enumerating such inversion sequences according to their length, we obtain well-known quantities such as Catalan numbers, Fibonacci numbers and central polynomial numbers, relating inversion sequences to other combinatorial structures. We also classify consecutive patterns of relations into Wilf equivalence classes, according to the number of inversion sequences avoiding them, and into more restrictive classes that consider the positions of the occurrences of the patterns.

As a byproduct of our techniques, we obtain a simple bijective proof of a result of Baxter-Shattuck and Kasraoui about Wilf-equivalence of vincular patterns, and we prove a conjecture of Martinez and Savage, as well as related enumeration formulas for inversion sequences satisfying certain unimodality conditions.

1 Introduction

A common encoding of permutations is by their inversion sequences. Specifically, denoting by S_{n} the set of permutations of [n] = {1, 2, …, n}, and by I_{n} the set of inversion sequences of length n—that is, integer sequences e = e_{1}e_{2} ⋯ e_{n} with 0 ≤ e_{i} < i for each i—one can define a bijection Θ : S_{n} → I_{n} that assigns to each π ∈ S_{n} its inversion sequence

Θ(π) = e = e_{1}e_{2} ⋯ e_{n}, where e_{i} = |{j : j < i and π_{j} > π_{i}}| .  (1)

Clearly, e_{1} + ⋯ + e_{n} is the number of inversions of π, namely, pairs (i, j) with i < j and π_{i} > π_{j}.

In analogy to patterns in permutations, a research area that has received a lot of attention in the last few decades, one can study patterns in inversion sequences. In this context, a pattern is a sequence p = p_{1}p_{2} ⋯ p_{r} with p_{i} ∈ {0, 1, …, r − 1} for each i, where any value j > 0 can appear in p only if j − 1 appears as well. Given a word w = w_{1}w_{2} ⋯ w_{k} over the integers, define its reduction to be the word obtained by replacing all the occurrences of the ith smallest entry of w with i−1 for all i. Then, an inversion sequence e contains the classical pattern p = p_{1}p_{2} ⋯ p_{r} if there exists a subsequence e_{i_{1}}e_{i_{2}} ⋯ e_{i_{r}} of e (where i_{1} < ⋯ < i_{r}) with reduction p. Otherwise, we say that e avoids p. For instance, the inversion sequence e = 00014224 avoids the pattern 210, but it contains the pattern 101 because e_{5}e_{6}e_{8} = 424 has reduction 101.

The study of classical patterns in inversion sequences was started by Corteel, Martinez, Savage, and Weselcouch [10], and Mansour and Shattuck [19]. Their work connected classical patterns in inversion sequences to other combinatorial structures, which inspired a growing body of research on classical patterns in inversion sequences [5, 7, 17, 16, 18, 20, 25].

Motivated by the work of Corteel et al. [10], and Mansour and Shattuck [19], and by the growing interest in consecutive patterns in permutations [13, 12], we introduced consecutive patterns in inversion sequences and initiated an analogous study [1]. In the definition below, the entries of a consecutive pattern are underlined to distinguish it from a classical pattern.

Definition 1. An inversion sequence e contains the consecutive pattern p = \underline{p_{1}p_{2} ⋯ p_{r}} if there is a consecutive subsequence e_{i}e_{i+1} ⋯ e_{i+r−1} of e whose reduction is p. In this case, we call e_{i}e_{i+1} ⋯ e_{i+r−1} an occurrence of p in position i. If e does not contain p, then we say that e avoids p. Denote by I_{n}(p) the set of inversion sequences of length n that avoid p.

Example 2. The inversion sequence e = 002241250 ∈ I_{9} avoids the consecutive pattern \underline{210}, even though it contains the classical pattern 210. On the other hand, e contains \underline{201} because e_{5}e_{6}e_{7} is an occurrence of \underline{201} in position 5.

It is often useful to represent an inversion sequence e as an underdiagonal lattice path from the origin to the line x = n, consisting of unit horizontal steps E = (1, 0) and unit vertical steps N = (0, 1) and S = (0, −1). Each entry e_{i} of e is represented by a horizontal step: a segment between the points (i − 1, e_{i}) and (i, e_{i}). Any necessary vertical steps are then inserted to make the path connected (see Figure 1).

Figure 1: Representation of e = 002241250 ∈ I_{9} as a lattice path.

Extending the systematic study of Corteel et al. [10] for classical patterns in inversion sequences, Martinez and Savage [20] reframe the notion of a pattern of length 3 to instead consider a triple of binary relations between the entries of the occurrence. Given a fixed triple of binary relations (R_{1}, R_{2}, R_{3}), where R_{i} ∈ {≤, ≥, <, >, =, ≠, −} for all i, they study the set I_{n} (R_{1}, R_{2}, R_{3}) consisting of those e ∈ I_{n} with no subindices i < j < k such that e_{i}R_{1}e_{j}, e_{j}R_{2}e_{k} and e_{i}R_{3}e_{k}. The symbol − denotes the trivial relation where all elements are related, that is, x − y for all x, y.

Example 3. I_{n} (≥, ≤, ≤) is the set of inversion sequences e ∈ I_{n} with no i < j < k such that e_{i} ≥ e_{j}, e_{j} ≤ e_{k} and e_{i} ≤ e_{k}; equivalently, the set of inversion sequences in I_{n} avoiding all the patterns in the set {000, 001, 101, 102}. On the other hand, I_{n} (≥, ≤, −) denotes the set of inversion sequences avoiding all the patterns in the set {000, 001, 100, 101, 102, 201}.

In this paper, we continue the work we initiated on consecutive patterns in inversion sequences [1], by considering consecutive analogues of the notions introduced by Martinez and Savage [20]. Specifically, we focus on the consecutive analogues of the sets I_{n} (R_{1}, R_{2}, −). These are the most natural ones to study, since the general case would impose a restrictive relation R_{3} between non-consecutive entries.

Definition 4. Let R_{1}, R_{2} ∈ {≤, ≥, <, >, =, ≠}. An inversion sequence e contains the consecutive pattern of relations (\underline{R_{1}, R_{2}}) if there is an i such that e_{i}R_{1}e_{i+1} and e_{i+1}R_{2}e_{i+2}. In this case, we call e_{i}e_{i+1}e_{i+2} an occurrence of (\underline{R_{1}, R_{2}}) in position i. If e does not contain (\underline{R_{1}, R_{2}}), then we say that e avoids (\underline{R_{1}, R_{2}}). Denote by I_{n} (\underline{R_{1}, R_{2}}) the set of inversion sequences of length n that avoid (\underline{R_{1}, R_{2}}).

Example 5. The inversion sequence e = 002241250 contains (\underline{>, <}) because e_{5}e_{6}e_{7} = 412 is an occurrence of this pattern. However, e avoids (\underline{=, >}), and so e ∈ I_{9} (\underline{=, >}).

Note that an occurrence of a consecutive pattern (\underline{R_{1}, R_{2}}) in an inversion sequence is also an occurrence of some consecutive pattern of length 3. Thus, every set I_{n} (\underline{R_{1}, R_{2}}) can be expressed as an intersection ⋂_{p} I_{n}(p) where p ranges over the consecutive patterns p = \underline{p_{1}p_{2}p_{3}} satisfying p_{1}R_{1}p_{2} and p_{2}R_{2}p_{3}. For instance, since occurrences of (\underline{≥, =}) are occurrences of either \underline{100} or \underline{000}, we can write I_{n} (\underline{≥, =}) = I_{n} (\underline{000}) ∩ I_{n} (\underline{100}).

This paper focuses on the enumeration of the sets I_{n} (\underline{R_{1}, R_{2}}). These sets often exhibit more structure than the sets I_{n}(p) avoiding a single consecutive pattern of length 3. Consequently, the sequences |I_{n} (\underline{R_{1}, R_{2}})| are often simpler than the sequences |I_{n}(p)|, which we studied before [1], and they provide more connections to other combinatorial objects and well-known integer sequences.

In addition to providing enumeration formulas, we also introduce several notions of equivalence between consecutive patterns of relations. These definitions are analogous to those for consecutive patterns in inversion sequences [1], which in turn are based on standard notions of equivalence between consecutive patterns in permutations [11, 12].

Definition 6. Let (\underline{R_{1}, R_{2}}) and (\underline{R′_{1}, R′_{2}}) be consecutive patterns of relations in inversion

sequences. We say that (\underline{R_{1}, R_{2}}) and (\underline{R′_{1}, R′_{2}}) are

• Wilf equivalent, denoted by (\underline{R_{1}, R_{2}}) ∼ (\underline{R′_{1}, R′_{2}}), if |I_{n} (\underline{R_{1}, R_{2}})| = |I_{n} (\underline{R′_{1}, R′_{2}})| for all n;

• strongly Wilf equivalent, denoted by (\underline{R_{1}, R_{2}}) ∼^{s} (\underline{R′_{1}, R′_{2}}), if for each n and m, the

number of inversion sequences in I_{n} containing m occurrences of (\underline{R_{1}, R_{2}}) is the same

as for (\underline{R′_{1}, R′_{2}});

• super-strongly Wilf equivalent, denoted by (\underline{R_{1}, R_{2}}) ∼^{ss} (\underline{R′_{1}, R′_{2}}), if the above condition holds for any set of prescribed positions for the m occurrences.

We use the term generalized Wilf equivalence to refer to an equivalence of any one of the these three types.

2 Summary of results

We will show that the 36 consecutive patterns of relations of the form (\underline{R_{1}, R_{2}}), with R_{1}, R_{2} ∈ {≤, ≥, <, >, =, ≠} fall into 30 Wilf equivalence classes, and into 31 strong Wilf equivalence classes, which are also super-strong equivalence classes. The next result provides this classification. Patterns are listed from least avoided to most avoided in inversion sequences of length 10.

Theorem 7. A complete list of the generalized Wilf equivalences between consecutive patterns of relations (\underline{R_{1}, R_{2}}) in inversion sequences is as follows:

(i) (\underline{≥, <}) ∼^{ss} (\underline{<, ≥}) ∼ (\underline{≠, ≥}) . ; (ii) (\underline{≥, ≥}) ∼^{ss} (\underline{<, <}). ; (iii) (\underline{≥, =}) ∼^{ss} (\underline{=, ≥}).  {(iv) (\underline{≥, >}) ∼^{ss} (\underline{>, ≥}). \atop (v) (\underline{>, =}) ∼^{ss} (\underline{=, >}).}

It is worth pointing out that the patterns (\underline{≥, <}) and (\underline{≠, ≥}) (similarly, (\underline{<, ≥}) and (\underline{≠, ≥})) are Wilf equivalent but not strongly Wilf equivalent.

Corollary 8. Wilf equivalence and strong Wilf equivalence classes of consecutive patterns of relations in inversion sequences do not coincide in general.

This result is interesting for two reasons. On the one hand, Wilf equivalence and strong Wilf equivalence classes of single consecutive patterns are conjectured to coincide, both in the setting of permutations, see Nakamura’s conjecture [21, Conj. 5.6], and in the setting of inversion sequences [1, Conj. 2.3]. Corollary 8 shows that, perhaps surprisingly, the analogous statement for consecutive patterns of relations does not hold. On the other hand, when considering consecutive patterns of relations in the setting of permutations, by defining π_{i}π_{i+1}π_{i+2} to be an occurrence of (\underline{R_{1}, R_{2}}) in π ∈ S_{n} if π_{i}R_{1}π_{i+1} and π_{i+1}R_{2}π_{i+2}, Wilf equivalence and strong Wilf equivalence classes of patterns of the form (\underline{R_{1}, R_{2}}) in permutations coincide. In fact, all such equivalences are obtained from trivial symmetries, unlike in the case of consecutive patterns of relations in inversion sequences.

As a consequence of Theorem 7(iv), we will deduce the following result about permutation patterns, originally conjectured by Baxter and Pudwell [3, Conj. 17], and later proved by Baxter and Shattuck [4, Cor. 11] and by Kasraoui [15, Cor. 1.9(a)]. Here we present a direct bijective proof based on consecutive patterns of relations in inversion sequences, which is simpler than the previously known proofs. We write \underline{124}3 and \underline{421}3 to denote vincular (also called generalized) permutation patterns, where entries in underlined positions are required to be adjacent in an occurrence [2]. We use S_{n}(σ) to denote the set of permutations in S_{n} that avoid a pattern σ, and we say that two permutation patterns σ and τ are Wilf equivalent if |S_{n}(σ)| = |S_{n}(τ)| for all n.

Corollary 9. The vincular permutation patterns \underline{124}3 and \underline{421}3 are Wilf equivalent.

Aside from the classification provided in Theorem 7, the other central result in this paper is the enumeration of inversion sequences avoiding consecutive patterns of relations. We will show that, for many patterns (\underline{R_{1}, R_{2}}), the sequence |I_{n} (\underline{R_{1}, R_{2}})| matches an existing sequence in the On-line Encyclopedia of Integer Sequences (OEIS) [22] enumerating other combinatorial objects. In most cases, we will prove this bijectively. These results are summarized in Table 1. For other patterns of relations, even though we have no closed-form formulas for |I_{n} (\underline{R_{1}, R_{2}})|, we can obtain recurrences to compute these numbers.

As a byproduct of our enumeration, we will prove the following result involving nonconsecutive triples of relations, which was conjectured by Martinez and Savage [20, Sec. 2.19]. After presenting our solution at the conference Permutation Patterns 2018, we learned

Pattern (\underline{R_{1}, R_{2}})  OEIS [22] Description  Initial terms |I_{n} (\underline{R_{1}, R_{2}})| for 1 ≤ n ≤ 9
(\underline{≤, ≠})  \underline{A040000} 2 (for n > 1)  1, 2, 2, 2, 2, 2, 2, 2, 2
(\underline{≤, ≥})  \underline{A000027} n  1, 2, 3, 4, 5, 6, 7, 8, 9
(\underline{≥, ≠})  \underline{A000124} \binom{n}{2} + 1  1, 2, 4, 7, 11, 16, 22, 29, 37
(\underline{≥, ≤})  \underline{A000045} F_{n+1}  1, 2, 3, 5, 8, 13, 21, 34, 55
(\underline{≠, ≤})  \underline{A000071} F_{n+2} − 1  1, 2, 4, 7, 12, 20, 33, 54, 88
(\underline{≥, <}) ∼^{ss} (\underline{<, ≥}) ∼ (\underline{≠, ≥}) \underline{A000079} 2^{n−1}  1, 2, 4, 8, 16, 32, 64, 128, 256
(\underline{≠, ≠})

\underline{A000085}

Number of involutions of [n]

1, 2, 4, 10, 26, 76, 232, 764, 2620

(\underline{≤, >})  \underline{A000108} C_{n} (Catalan)  1, 2, 5, 14, 42, 132, 429, 1430, 4862
(\underline{>, ≤})

\underline{A071356}

Underdiagonal paths of from the origin to x = n with steps (0, 1), (1, 0), (1, 2)

1, 2, 6, 20, 72, 272, 1064, 4272, 17504

(\underline{=, ≠})  \underline{A003422} 0!+1!+2!+⋯+(n−1)! 1, 2, 4, 10, 34, 154, 874, 5914, 46234
(\underline{≥, ≥}) ∼^{ss} (\underline{<, <})  \underline{A049774} |S_{n} (\underline{321})|  1, 2, 5, 17, 70, 349, 2017, 13358, 99377
(\underline{≠, =})  \underline{A000522} ∑_{i=0}^{n−1}(n − 1)!/i!  1, 2, 5, 16, 65, 326, 1957, 13700, 109601
(\underline{≥, >}) ∼^{ss} (\underline{>, ≥})  \underline{A200403} |S_{n} (\underline{124}3)|  1, 2, 6, 23, 107, 584, 3660, 25910, 204564
(\underline{=, =})  \underline{A052169} \frac{(n+1)!−d_{n+1}}{n}  1, 2, 5, 19, 91, 531, 3641, 28673, 254871

Table 1: Consecutive patterns of relations (\underline{R_{1}, R_{2}}) for which |I_{n} (\underline{R_{1}, R_{2}})| appears in the OEIS [22] and has an existing alternative combinatorial interpretation. Here F_{n} denotes the nth Fibonacci number, and d_{n} is the number of derrangements of [n]. The patterns are listed from least avoided to most avoided in inversion sequences of length 10.

that it has also been proved independently using different methods by Cao, Jin, and Lin [9, Thm. 5.1] and by Hossain [14].

Theorem 10. The sequence |I_{n} (>, ≤, −)| has ordinary generating function (OGF)

∑_{n≥0} |I_{n} (>, ≤, −)| z^{n} = \frac{1 + 2z − \sqrt{1 − 4z − 4z^{2}}}{4z} .

The paper is organized as follows. Section 3 is devoted to the classification of consecutive patterns of relations into generalized Wilf equivalence classes, as given in Definition 6, proving Theorem 7. We also provide a bijective proof of Corollary 9. In Section 4, we prove the enumerative results summarized in Table 1, as well as Theorem 10. Finally, in Section 5 we generalize the method used in the proof of Theorem 10 and apply it to enumerate different types of unimodal inversion sequences.

3 Generalized Wilf equivalences

3.1 Proof of Theorem 7

In this section we will find all the generalized Wilf equivalences between consecutive patterns of relations. We start proving part (v) of Theorem 7. Occurrences of (\underline{>, =}) and (\underline{=, >}) are simply occurrences of \underline{100} and \underline{110}, respectively. Hence, the equivalence (\underline{>, =}) ∼^{ss} (\underline{=, >}) is a restatement of the equivalence \underline{100} ∼^{ss} \underline{110} (defined to mean that the number of inversion sequences of any given length with occurrences in any prescribed positions is the same for both patterns), which is already known [1, Prop. 3.12]. We repeat the proof here because the same method will be useful in proving several equivalences between consecutive patterns of relations.

First, we introduce some notation. Given R_{1}, R_{2} ∈ {≤, ≥, <, >, =, ≠} and e ∈ I_{n}, define

Em ((\underline{R_{1}, R_{2}}) , e) = \{i : e_{i}e_{i+1}e_{i+2} is an occurrence of (\underline{R_{1}, R_{2}})\} .

Note that, by definition, (\underline{R_{1}, R_{2}}) ∼^{ss} (\underline{R′_{1}, R′_{2}}) if and only if

|\{e ∈ I_{n} : Em ((\underline{R_{1}, R_{2}}) , e) = S\}| = |\{e ∈ I_{n} : Em ((\underline{R′_{1}, R′_{2}}) , e) = S\}|

for all n and all S ⊆ [n]. The next lemma, which is analogous to [1, Lem. 3.11], has a straightforward proof using the principle of inclusion-exclusion.

Lemma 11. Let (\underline{R_{1}, R_{2}}) and (\underline{R′_{1}, R′_{2}}) be two consecutive patterns of relations such that

|\{e ∈ I_{n} : Em ((\underline{R_{1}, R_{2}}) , e) ⊇ S\}| = |\{e ∈ I_{n} : Em ((\underline{R′_{1}, R′_{2}}) , e) ⊇ S\}|

for all positive integers n and all S ⊆ [n]. Then (\underline{R_{1}, R_{2}}) ∼^{ss} (\underline{R′_{1}, R′_{2}}).

Now we are ready to prove Theorem 7(v).

Proposition 12. The patterns (\underline{>, =}) and (\underline{=, >}) are super-strongly Wilf equivalent.

Proof. By Lemma 11, it suffices to show that, for all positive integers n and all S ⊆ [n],

|\{e ∈ I_{n} : Em ((\underline{=, >}) , e) ⊇ S\}| = |\{e ∈ I_{n} : Em ((\underline{>, =}) , e) ⊇ S\}| .

To show this, we construct a bijection

Φ_{S} : \{e′ ∈ I_{n} : Em ((\underline{=, >}) , e′) ⊇ S\} → \{e ∈ I_{n} : Em ((\underline{>, =}) , e) ⊇ S\}

that replaces the occurrences of (\underline{=, >}) (equivalently, of \underline{110}) in e in positions S with occurrences of (\underline{>, =}) (equivalently, of \underline{100}). For e ∈ I_{n} with Em ((\underline{=, >}) , e′) ⊇ S, define Φ_{S}(e) = e′ by setting

e′_{j} = \begin{cases}e_{j+1}, & if j − 1 ∈ S; \\ e_{j}, & otherwise; \end{cases}

for 1 ≤ j ≤ n. The sequence e′ is an inversion sequence because if j − 1 ∈ S, then e′_{j} = e_{j+1} < e_{j} < j.

To see that Φ_{S} is a bijection, we describe its inverse Ψ_{S}. For e′ ∈ I_{n} with Em ((\underline{>, =}) , e) ⊇ S, define Ψ_{S}(e′) = e by

e_{j} = \begin{cases}e′_{j−1}, & if j − 1 ∈ S; \\ e′_{j}, & otherwise; \end{cases}

for 1 ≤ j ≤ n. Note that e ∈ I_{n} because if j − 1 ∈ S, then e_{j} = e′_{j−1} < j − 1 < j. Since no two occurrences of (\underline{=, >}) (respectively, (\underline{>, =})) can overlap in more than one entry, the maps Φ_{S} and Ψ_{S} are inverses of each other.

The next result proves Theorem 7(iii). It again relies on Lemma 11.

Proposition 13. The patterns (\underline{≥, =}) and (\underline{=, ≥}) are super-strongly Wilf equivalent.

Proof. Let n be a positive integer and S ⊆ [n]. By Lemma 11, it suffices to construct a bijection

Φ_{S} : \{e ∈ I_{n} : Em ((\underline{=, ≥}) , e) ⊇ S\} → \{e′ ∈ I_{n} : Em ((\underline{≥, =}) , e′) ⊇ S\} .

We can write S uniquely as a disjoint union of blocks, which we define as maximal subsets whose entries are consecutive. Explicitly, write

S = ⨆_{j=1}^{m} B_{j},

where B_{j} = {i_{j}, i_{j} + 1, …, i_{j} + l_{j}}, with l_{j} ≥ 0 and i_{j} + l_{j} + 1 < i_{j+1} for all j.

Let e ∈ I_{n} be such that Em ((\underline{=, ≥}) , e) ⊇ S. Then, for each 1 ≤ j ≤ m, we have

e_{i_{j}} = e_{i_{j}+1} = ⋯ = e_{i_{j}+l_{j}+1} ≥ e_{i_{j}+l_{j}+2}.

Define Φ_{S}(e) = e′ by setting

e′_{i} = \begin{cases}e_{i_{j}+l_{j}+2}, & if i − 1 ∈ B_{j} for some j and e_{i_{j}+l_{j}+1} > e_{i_{j}+l_{j}+2}; \\ e_{i}, & otherwise; \end{cases}

for 1 ≤ i ≤ n, as described schematically in Figure 2. In other words, we have

e_{i_{j}} = e′_{i_{j}} ≥ e′_{i_{j}+1} = ⋯ = e′_{i_{j}+l_{j}+1} = e′_{i_{j}+l_{j}+2} = e_{i_{j}+l_{j}+2}

Figure 2: Schematic diagram of the behavior of Φ_{S} and Ψ_{S} from Proposition 13.

for each j, and so Em ((\underline{≥, =}) , e′) ⊇ S. Additionally, if i is such that e′_{i} ≠ e_{i}, then e′_{i} = e_{i_{j}+l_{j}+2} ≤ e_{i} < i. Hence e′ ∈ I_{n}.

To see that Φ_{S} is a bijection, we describe its inverse map Ψ_{S} as follows. Given e′ ∈ I_{n} such that Em ((\underline{≥, =}) , e′) ⊇ S, let Ψ_{S} (e′) = e, where

e_{i} = \begin{cases}e′_{i_{j}}, & if i − 1 ∈ B_{j} for some j and e′_{i_{j}} > e′_{i_{j}+1}; \\ e′_{i}, & otherwise; \end{cases}

for 1 ≤ i ≤ n. If i is such that e_{i} ≠ e′_{i}, then e_{i} = e′_{i_{j}} < i_{j} < i, and so e ∈ I_{n}. Additionally, Em ((\underline{=, ≥}) , e) ⊇ S. By construction, the maps Φ_{S} and Ψ_{S} are inverses of each other.

Next we prove Theorem 7(iv), using a similar argument.

Proposition 14. The patterns (\underline{≥, >}) and (\underline{>, ≥}) are super-strongly Wilf equivalent.

Proof. Let n be a positive integer and S ⊆ [n]. By Lemma 11, it is enough to describe a bijection

Φ_{S} : \{e ∈ I_{n} : Em ((\underline{≥, >}) , e) ⊇ S\} → \{e′ ∈ I_{n} : Em ((\underline{>, ≥}) , e′) ⊇ S\} .

Again, we write S as a disjoint union of blocks, S = ⨆_{j=1}^{m} B_{j}, where B_{j} = {i_{j}, i_{j} + 1, …, i_{j} + l_{j}}, with l_{j} ≥ 0 and i_{j} + l_{j} + 1 < i_{j+1} for all j.

Given e ∈ I_{n} such that Em ((\underline{≥, >}) , e) ⊇ S, we have

e_{i_{j}} ≥ e_{i_{j}+1} > ⋯ > e_{i_{j}+l_{j}+1} > e_{i_{j}+l_{j}+2}

for each j. Define Φ_{S}(e) = e′ by setting

e′_{i} = \begin{cases}e_{i+1}, & if i − 1 ∈ B_{j} for some j and e_{i_{j}} = e_{i_{j}+1}; \\ e_{i}, & otherwise; \end{cases}

for 1 ≤ i ≤ n, as shown in Figure 3. Then

e′_{i_{j}} > e′_{i_{j}+1} > ⋯ > e′_{i_{j}+l_{j}+1} ≥ e′_{i_{j}+l_{j}+2}

Figure 3: Schematic diagram of the behavior of Φ_{S} and Ψ_{S} from Proposition 14.

for each j, and so Em ((\underline{>, ≥}) , e′) ⊇ S. Additionally, since e′_{i} = e_{i+1} < e_{i} < i whenever e′_{i} ≠ e_{i}, we have that e′ ∈ I_{n}.

To see that Φ_{S} is a bijection, note that its inverse Ψ_{S} can be described as follows. Given e′ ∈ I_{n} such that Em ((\underline{>, ≥}) , e′) ⊇ S, let Ψ_{S} (e′) = e, where

e_{i} = \begin{cases}e′_{i−1}, & if i − 1 ∈ B_{j} for some j and e′_{i_{j}+l_{j}+1} = e′_{i_{j}+l_{j}+2}; \\ e′_{i}, & otherwise. \end{cases}

Given e = e_{1}e_{2} ⋯ e_{n} ∈ I_{n}, we define its complement to be the inversion sequence e^{C} = e_{1}^{C}e_{2}^{C} ⋯ e_{n}^{C}, where e_{i}^{C} = i − 1 − e_{i} for 1 ≤ i ≤ n. This notion is useful in proving Theorem 7(i)(ii), which we do next.

Proposition 15. The following equivalences hold.

(i_{1}) (\underline{≥, <}) ∼^{ss} (\underline{<, ≥}).  (ii) (\underline{≥, ≥}) ∼^{ss} (\underline{<, <}).

Proof. To prove part (i_{1}), note that e_{i} ≥ e_{i+1} if and only if e_{i}^{C} < e_{i+1}^{C}. Indeed, the first equality is equivalent to i − 1 − e_{i}^{C} ≥ i − e_{i+1}^{C}, which is in turn equivalent to the second. We deduce that

e_{i} ≥ e_{i+1} < e_{i+2} if and only if e_{i}^{C} < e_{i+1}^{C} ≥ e_{i+2}^{C}.

It follows that the involution e → e^{C} replaces occurrences of (\underline{≥, <}) by occurrences of (\underline{<, ≥}), and vice versa. We conclude that (\underline{≥, <}) and (\underline{<, ≥}) are super-strongly Wilf equivalent.

A very similar argument proves part (ii).

The next proposition proves the other equivalence in Theorem 7(i). Corollary 8 is an immediate consequence.

Proposition 16. The patterns (\underline{<, ≥}) and (\underline{≠, ≥}) are Wilf equivalent, but not strongly Wilf equivalent.

Proof. To prove that (\underline{<, ≥}) ∼ (\underline{≠, ≥}), we will show that, in fact, I_{n} (\underline{<, ≥}) = I_{n} (\underline{≠, ≥}). Occurrences of (\underline{<, ≥}) are occurrences of one of the following consecutive patterns: \underline{010}, \underline{011}, \underline{021}, \underline{120}. Similarly, occurrences of (\underline{≠, ≥}) are occurrences of one of the same four patterns, together with \underline{100} or \underline{210}. We deduce that I_{n} (\underline{≠, ≥}) ⊆ I_{n} (\underline{<, ≥}).

Suppose that e ∈ I_{n} (\underline{<, ≥}) has an occurrence e_{i}e_{i+1}e_{i+2} of (≠, ≥). Then it must be an occurrence of \underline{100} or \underline{210}, so e_{i} > e_{i+1} ≥ 0. Let j be the largest index such that 1 ≤ j < i and e_{j} < e_{j+1}. Such a j must exist because e_{1} = 0 and e_{i} > 0. But then e_{j} < e_{j+1} ≥ e_{j+2}, that is, e_{j}e_{j+1}e_{j+2} is an occurrence of (\underline{<, ≥}), which is a contradiction. We conclude that I_{n} (\underline{<, ≥}) = I_{n} (\underline{≠, ≥}).

To show that (\underline{<, ≥}) and (\underline{≠, ≥}) are not strongly Wilf equivalent, it is enough to look at the number of occurrences of these patterns in inversion sequences of length 4. There is an inversion sequence in I_{4} with two occurrences of (\underline{≠, ≥}), namely 0100, but none with two occurrences of (\underline{<, ≥}).

Proof of Theorem 7. Propositions 12, 13, 14, 15 and 16 prove all the equivalences listed. A brute force computation of the first 10 terms of the sequences |I_{n} (\underline{R_{1}, R_{2}})| for R_{1}, R_{2} ∈ \{≤ , ≥, <, >, =, ≠} confirms that there are no other Wilf equivalences between such consecutive patterns of relations, showing that the list is complete.

3.2 An application to permutation patterns

Inversion sequences avoiding the patterns (\underline{≥, >}) and (\underline{>, ≥}) are closely related to permutations avoiding vincular patterns. We will exploit this connection to deduce Corollary 9 from Theorem 7(iv), using the following lemma.

Lemma 17. Let π ∈ S_{n} and e = Θ(π). Then:

(a) e_{i} ≥ e_{i+1} if and only if π_{i} < π_{i+1};
(b) e_{i} > e_{i+1} if and only if there exists j < i such that π_{i} < π_{j} < π_{i+1}.

Proof. Let E_{i} = {j ∈ [n] : j < i and π_{j} > π_{i}}, so that the entries of e satisfy e_{i} = |E_{i}|.

To prove (a), first suppose that π_{i} < π_{i+1}. Then every j < i + 1 such that π_{j} > π_{i+1} satisfies j < i and π_{j} > π_{i}. It follows that E_{i+1} ⊆ E_{i}, and so e_{i} ≥ e_{i+1}. Conversely, suppose that π_{i} > π_{i+1}. Then every j < i such that π_{j} > π_{i} satisfies π_{j} > π_{i+1}, so E_{i} ⊆ E_{i+1}. Furthermore, i ∈ E_{i+1}\E_{i}, so this inclusion is strict and, consequently, e_{i} < e_{i+1}.

To prove (b), suppose that e_{i} > e_{i+1}. Then π_{i} < π_{i+1} by part (a), and so E_{i+1} ⊆ E_{i}. If for every j < i we had either π_{j} < π_{i} or π_{i+1} < π_{j}, then E_{i} ⊆ E_{i+1}, from where E_{i} = E_{i+1} and e_{i} = e_{i+1}, which is a contradiction. Hence, there exists j < i such that π_{i} < π_{j} < π_{i+1}.

Conversely, if j < i is such that π_{i} < π_{j} < π_{i+1}, then E_{i+1} ⊆ E_{i} and j ∈ E_{i}\E_{i+1}, so this inclusion is strict. Thus, e_{i} > e_{i+1}.

The following result connects the vincular permutation patterns \underline{124}3 and \underline{421}3 to the consecutive patterns of relations (\underline{>, ≥}) and (\underline{≥, >}), respectively. In the proof we will use the next two definitions. For a permutation π ∈ S_{n}, define its reverse π^{R} to be the permutation with entries π_{i}^{R} = π_{n+1−i}, and its reverse-complement π^{RC} to be the permutation such that π_{i}^{RC} = n + 1 − π_{i}^{R} for all i.

Proposition 18. Let π ∈ S_{n} and e = Θ(π). Then:

(a) π avoids the vincular pattern 2\underline{134} if and only if e avoids the consecutive pattern of relations (\underline{>, ≥}). Consequently, |S_{n} (\underline{124}3)| = |S_{n} (2\underline{134})| = |I_{n} (\underline{>, ≥})|.

(b) π avoids the vincular pattern 3\underline{124} if and only if e avoids the consecutive pattern of relations (\underline{≥, >}). Consequently, |S_{n} (\underline{421}3)| = |S_{n} (3\underline{124})| = |I_{n} (\underline{≥, >})|.

Proof. The permutation π contains the vincular pattern 2\underline{134} if and only if there exist indices j < i such that π_{i} < π_{j} < π_{i+1} < π_{i+2}. By Lemma 17, these inequalities are equivalent to e_{i} > e_{i+1} ≥ e_{i+2}, namely, to e having an occurrence of (\underline{>, ≥}) in position i. It follows that π avoids 2\underline{134} if and only if e avoids (\underline{>, ≥}). Since the map π → π^{RC} induces a bijection between S_{n} (\underline{124}3) and S_{n} (2\underline{134}), this proves part (a).

Similarly, π contains the vincular pattern 3\underline{124} if and only if there exist indices j < i such that π_{i} < π_{i+1} < π_{j} < π_{i+2}. By Lemma 17, this is equivalent e having an occurrence of (\underline{≥, >}) in position i. Thus, π avoids 3\underline{124} if and only if e avoids (\underline{≥, >}). Since the map π → π^{R} induces a bijection between S_{n} (\underline{421}3) and S_{n} (3\underline{124}), part (b) follows.

Theorem 7(iv) and Proposition 18 imply that |S_{n} (\underline{124}3)| = |S_{n} (\underline{421}3)|, which proves Corollary 9. This result was originally conjectured by Baxter and Pudwell [3, Conj. 17], and later proved by Baxter and Shattuck [4, Cor. 11] and by Kasraoui [15, Cor. 1.9(a)], who showed that the vincular permutation patterns \underline{124}3 and \underline{421}3 are, in fact, strongly Wilf equivalent.

However, none of these proofs provides a simple bijection between S_{n} (\underline{124}3) and S_{n} (\underline{421}3). Next we present such a bijection. Its easiest description is at the level of inversion sequences. Note that, even though we proved in Proposition 14 that (\underline{≥, >}) and (\underline{>, ≥}) are super-strongly Wilf equivalent, our proof did not give a bijection between the corresponding pattern-avoiding sets.

Proposition 19. For n ≥ 1, there is an explicit bijection Φ : I_{n} (\underline{≥, >}) → I_{n} (\underline{>, ≥}) with the property that if e′ = Φ(e), then e′_{n} = e_{n}.

Proof. Given e ∈ I_{n} (\underline{≥, >}), define Φ(e) = e′ to be the inversion sequence obtained by replacing each maximal occurrence of a consecutive pattern \underline{10^{r}} (for r ≥ 2) in e with an occurrence of \underline{1^{r}0}. In other words, each maximal subsequence of the form e_{j} > e_{j+1} = e_{j+2} = ⋯ = e_{j+r} (with r ≥ 2) becomes a subsequence e′_{j} = e′_{j+1} = ⋯ = e′_{j+r−1} > e′_{j+r}, where e′_{j} = e_{j} and e′_{j+r} = e_{j+r}. Note that Φ acts on these subsequences in analogy to how the map Ψ_{S}, described in the schematic diagram in Figure 2, acted on blocks.

We now show that e′ ∈ I_{n} (\underline{>, ≥}). Since e ∈ I_{n} (\underline{≥, >}), it avoids (\underline{>, >}) as well. Given that Φ removes all occurrences of (\underline{>, =}) in e, it suffices to prove that Φ introduces no new occurrences of (\underline{>, ≥}) at the edges of the changed subsequences; that is, that e′_{j−1}e′_{j}e′_{j+1} and e′_{j+r−1}e′_{j+r}e′_{j+r+1} are not occurrences of (\underline{>, ≥}) for j and r as above.

We argue by contradiction. Suppose that e′_{j−1} > e′_{j} ≥ e′_{j+1}. Then either e_{j−1} = e′_{j−1} or e_{j−1} = e′_{j}. Thus, e_{j−1} ≥ e′_{j} = e_{j} > e_{j+1}, so e_{j−1}e_{j}e_{j+1} would have been an occurrence of (\underline{≥, >}).

Now, suppose that e′_{j+r−1} > e′_{j+r} ≥ e′_{j+r+1}. Then e_{j+r−1} = e_{j+r} = e′_{j+r} ≥ e′_{j+r+1} ≥ e_{j+r+1}. However, at least one of these two inequalities must be strict because e_{j+r} = e_{j+r+1} would contradict the maximality of r. But then e_{j+r−1}e_{j+r}e_{j+r+1} would have been an occurrence of (\underline{≥, >}).

It is clear that Φ is a bijection, since the inverse map can be obtained by replacing each maximal occurrence of a consecutive pattern \underline{1^{r}0} (for r ≥ 2) with an occurrence of \underline{10^{r}}. Also, by construction, Φ preserves the last entry of e.

Combining Propositions 18 and 19, we see that the map π ↦ Θ^{−1} (Φ(Θ(π^{RC})))^{R} is a bijection between S_{n} (\underline{124}3) and S_{n} (\underline{421}3).

4 Enumerative results

In this section, we show that for consecutive patterns of relations (\underline{R_{1}, R_{2}}) in 14 of the 30 Wilf equivalence classes, the sequence |I_{n} (\underline{R_{1}, R_{2}})| matches a sequence in the OEIS [22] that is known to enumerates another combinatorial object. These results are summarized in Table 1.

This leaves 16 Wilf equivalence classes for which the first few terms of the sequence |I_{n} (\underline{R_{1}, R_{2}})| do not match any previously existing sequence in the OEIS [22], see Table 2. For 4 of these 16 classes, avoidance of a pattern of relations equates to avoidance of a single consecutive pattern. Specifically, the patterns of relations (\underline{<, =}), (\underline{=, <}), (\underline{>, =}) ∼^{ss} (\underline{=, >}) and (\underline{>, >}) correspond to the consecutive patterns \underline{011}, \underline{001}, \underline{100} ∼^{ss} \underline{110} and \underline{210}, respectively. Recurrences for these 4 classes are known, as they were treated in our systematic study of consecutive patterns in inversion sequences [1]. The remaining 12 Wilf equivalence classes of consecutive patterns of relations, listed from least avoided to most avoided in inversion sequences of length 10, are (\underline{≤, ≤}), (\underline{<, ≠}), (\underline{≠, <}), (\underline{≤, <}), (\underline{≠, >}), (\underline{<, >}), (\underline{<, ≤}), (\underline{>, ≠}),

(\underline{>, <}), (\underline{=, ≤}), (\underline{≤, =}), and (\underline{≥, =}) ∼^{ss} (\underline{=, ≥}).

For each pattern (\underline{R_{1}, R_{2}}) above, even though we do not have closed-form formulas for |I_{n} (\underline{R_{1}, R_{2}})|, we can obtain recurrences to compute these quantities. The recurrences are similar to the one in Proposition 47, and can be proved using analogous arguments.

Pattern (\underline{R_{1}, R_{2}}) New OEIS [22] entry Initial terms |I_{n} (\underline{R_{1}, R_{2}})| for 1 ≤ n ≤ 10
(\underline{≤, ≤})  \underline{A328357}  1, 2, 1, 4, 6, 36, 117, 804, 4266, 33768
(\underline{<, ≠})  \underline{A328358}  1, 2, 4, 10, 30, 100, 376, 1566, 7094, 34751
(\underline{≠, <})  \underline{A328429}  1, 2, 5, 14, 46, 170, 691, 3073, 14809, 76666
(\underline{≤, <})  \underline{A328430}  1, 2, 3, 7, 18, 70, 317, 1825, 11805, 88212
(\underline{≠, >})  \underline{A328431}  1, 2, 5, 15, 53, 214, 960, 4701, 24873, 141147
(\underline{<, >})  \underline{A328432}  1, 2, 5, 15, 53, 216, 994, 5076, 28403, 172538
(\underline{<, ≤})  \underline{A328433}  1, 2, 4, 11, 37, 157, 791, 4676, 31490, 238814
(\underline{>, ≠})  \underline{A328434}  1, 2, 6, 21, 81, 346, 1630, 8350, 45958, 269815
(\underline{>, <})  \underline{A328435}  1, 2, 6, 21, 83, 368, 1814, 9837, 58095, 370499
(\underline{=, ≤})  \underline{A328436}  1, 2, 3, 9, 37, 190, 1181, 8564, 70914, 659810
(\underline{=, <})  \underline{A328437}  1, 2, 4, 11, 42, 210, 1292, 9352, 77505, 722294
(\underline{≤, =})  \underline{A328438}  1, 2, 4, 13, 57, 304, 1937, 14315, 120264, 1131896
(\underline{<, =})  \underline{A328439}  1, 2, 5, 17, 75, 407, 2621, 19524, 165090, 1561900
(\underline{≥, =}) ∼^{ss} (\underline{=, ≥})  \underline{A328440}  1, 2, 5, 18, 81, 448, 2920, 21955, 186981, 1779170
(\underline{>, =}) ∼^{ss} (\underline{=, >})  \underline{A328441}  1, 2, 6, 23, 109, 618, 4098, 31173, 267809, 2565520
(\underline{>, >})  \underline{A328442}  1, 2, 6, 24, 118, 684, 4554, 34192, 285558, 2624496

Table 2: Consecutive patterns of relations (\underline{R_{1}, R_{2}}) for which |I_{n} (\underline{R_{1}, R_{2}})| did not previously appear in the OEIS [22]. The patterns are listed from least avoided to most avoided in inversion sequences of length 10.

4.1 The pattern (\underline{≤, ≠})

The following lemma gives a very simple description of the set I_{n} (\underline{≤, ≠}). The notation a^{s} indicates repetition s times of the entry a.

Lemma 20. For n ≥ 2,

I_{n} (\underline{≤, ≠}) = \{0^{n}, 01^{n−1}\} .

Proof. We proceed by induction on n. The statement is trivially true for the base case n = 2. Now let n ≥ 3, suppose the statement holds for n − 1, and let e ∈ I_{n} (\underline{≤, ≠}). Then e_{1}e_{2} ⋯ e_{n−1} ∈ I_{n−1} (\underline{≤, ≠}), so either e = 0^{n−1} or e = 01^{n−2}. In any case, e_{n−2} ≤ e_{n−1}, so it must be that e_{n−1} = e_{n}. Hence, either e = 0^{n} or e = 01^{n−1}. Since both of these inversion sequences avoid (\underline{≤, ≠}), we deduce that I_{n} (\underline{≤, ≠}) = \{0^{n}, 01^{n−1}\}.

It follows from Lemma 20 that |I_{1} (\underline{≤, ≠})| = 1 and |I_{n} (\underline{≤, ≠})| = 2 for n ≥ 2.

4.2 The pattern (\underline{≤, ≥})

The next lemma provides a characterization of the set I_{n} (\underline{≤, ≥}) in terms of a monotonicity condition. This will be a recurrent idea in this paper, as it is often convenient to describe the inversion sequences in I_{n} (\underline{R_{1}, R_{2}}) in terms of a monotonicity or unimodal condition, in order to enumerate them.

Lemma 21. For n ≥ 1,

I_{n} (\underline{≤, ≥}) = \{e ∈ I_{n} : e_{2} < e_{3} < ⋯ < e_{n}\}.

Proof. The inclusion to the left is immediate. To prove the inclusion to the right, let e ∈ I_{n} (\underline{≤, ≥}). We will show that e_{j} < e_{j+1} for 2 ≤ j < n by induction on j. For the base case j = 2, note that e_{1} = 0 ≤ e_{2} implies e_{2} < e_{3}, otherwise e_{1}e_{2}e_{3} would be an occurrence of (\underline{≤, ≥}). Now suppose that e_{j} < e_{j+1} for some 2 ≤ j < n − 1. Then e_{j+1} < e_{j+2}, because otherwise e_{j}e_{j+1}e_{j+2} would be an occurrence of (\underline{≤, ≥}).

Proposition 22. For n ≥ 1, |I_{n} (\underline{≤, ≥})| = n.

Proof. It follows from Lemma 21 and the definition of inversion sequence that I_{n} (\underline{≤, ≥}) is the set of sequences e_{1} … e_{n} with 0 = e_{1} ≤ e_{2} < e_{3} < ⋯ < e_{n} ≤ n − 1. Disregarding the forced entry e_{1} = 0, this condition in equivalent to

0 ≤ e_{2} ≤ e_{3} − 1 ≤ e_{4} − 2 ≤ ⋯ ≤ e_{n} − (n − 2) ≤ 1,  (2)

and so these entries are determined by the choice of which one of the n inequalities in (2) is strict. In other words, these entries are given by

e_{i} = \begin{cases}i − 2, & if 2 ≤ i ≤ j; \\ i − 1, & if j < i ≤ n; \end{cases}

for some fixed 1 ≤ j ≤ n. Thus, there are n such sequences.

4.3 The pattern (\underline{≥, ≠})

The next lemma characterizes inversion sequences avoiding this pattern.

Lemma 23. For n ≥ 1,

I_{n} (\underline{≥, ≠}) = \{e ∈ I_{n} : e_{1} < e_{2} < ⋯ < e_{j} ≥ e_{j+1} = e_{j+2} = ⋯ = e_{n} for some 1 ≤ j ≤ n\}.

Proof. The inclusion to the left is straightforward. For the inclusion to the right, let e ∈ I_{n} (\underline{≥, ≠}), and let j be the largest integer such that e_{1} < e_{2} < ⋯ < e_{j}. If j < n, then e_{j} ≥ e_{j+1} by construction, and since e avoids (\underline{≥, ≠}), it must be that e_{j+1} = e_{j+2} (if these entries are defined). Repeating the same argument, we have e_{j+1} = e_{j+2} = ⋯ = e_{n}.

Next we obtain a formula for the number of inversion sequences that avoid (\underline{≥, ≠}). This sequence appears as \underline{A000124} in the OEIS [22]; it is sometimes referred to as central polygonal numbers or as the lazy caterer’s sequence.

Proposition 24. For n ≥ 1, |I_{n} (\underline{≥, ≠})| = \binom{n}{2} + 1.

Proof. Let A_{n} be the collection of subsets of {0, 1, …, n − 2} with at most two elements. Clearly, |A_{n}| = \binom{n−1}{2} + (n − 1) + 1 = \binom{n}{2} + 1. We define a bijection Γ : I_{n} (\underline{≥, ≠}) → A_{n} by letting, for each e ∈ I_{n} (\underline{≥, ≠}),

Γ(e) = \begin{cases}\{max_{i}\{e_{i}\}, e_{n}\}, & if e_{n} ≠ n − 1; \\ ∅, & otherwise; \end{cases}

where {a, a} is simply the set {a}. If j is the index such that e_{1} < e_{2} < ⋯ < e_{j} ≥ e_{j+1} = e_{j+2} = ⋯ = e_{n}, which exists by Lemma 23 and is unique by definition, then e_{i} = i − 1 for 1 ≤ i ≤ j, so the above definition can be restated as Γ(e) = {e_{j}, e_{n}} if j < n and Γ(e) = ∅ otherwise.

To see that Γ is a bijection, we describe its inverse. Given any A ∈ A_{n}, we have

Γ^{−1}(A) = \begin{cases}012 ⋯ abb ⋯ b, & if A = \{a, b\} with a > b; \\ 012 ⋯ aa ⋯ a, & if A = \{a\}; \\ 012 ⋯ (n − 1), & if A = ∅. \end{cases}

Example 25. Applying the map Γ from the proof of Proposition 24 to e = 012322 ∈ I_{6} (\underline{≥, ≠}), we get Γ(e) = \{3, 2\}. Similarly, if e = 012344 ∈ I_{6} (\underline{≥, ≠}), then Γ(e) = \{4\}.

One can also obtain the formula in Proposition 24 as follows. Martinez and Savage [20, Observation 11] note that the set I_{n} (≥, ≠, −) is characterized by the same inequalities from Lemma 23, so we deduce that I_{n} (\underline{≥, ≠}) = I_{n} (≥, ≠, −). Moreover, they show that I_{n} (≥, ≠, −) = Θ (S_{n}(213, 321)), where Θ is given by (1) and S_{n}(213, 321) denotes the set of permutations in S_{n} avoiding both of the (classical) permutation patterns 213 and 321 [20, Thm. 9]. It was shown by Simion and Schmidt [23, Prop. 11] that |S_{n}(213, 321)| = \binom{n}{2} + 1. We conclude that

|I_{n} (\underline{≥, ≠})| = |I_{n} (≥, ≠, −)| = |S_{n}(213, 321)| = \binom{n}{2} + 1.

4.4 The pattern (\underline{≥, ≤})

The next lemma characterizes the set I_{n} (\underline{≥, ≤}) as strictly unimodal inversion sequences.

Lemma 26. For n ≥ 1,

I_{n} (\underline{≥, ≤}) = \{e ∈ I_{n} : e_{1} < e_{2} < ⋯ < e_{j} ≥ e_{j+1} > e_{j+2} > ⋯ > e_{n} for some 1 ≤ j ≤ n\}.

Figure 4: Two inversion sequences e ∈ I_{6} (\underline{≥, ≤}): e = 012210 (left) and e = 012310 (right).

Proof. The inclusion to the left is immediate, so let us prove the inclusion to the right. Suppose that e ∈ I_{n} (\underline{≥, ≤}), and let j be the smallest integer such that e_{j} ≥ e_{j+1}, or j = n if no such integer exists. Since e avoids (\underline{≥, ≤}), it must be that e_{j+1} > e_{j+2} (if these entries are defined). Repeating the same argument, we see that e_{j+1} > e_{j+2} > ⋯ > e_{n}. On the other hand, e_{j−1} < e_{j} (if j ≥ 2) by definition of j. Since e avoids (\underline{≥, ≤}), we must then have e_{1} < e_{2} < ⋯ < e_{j}. We conclude that e satisfies the stated unimodality condition.

Let C_{n} be the set of compositions of n with parts 1 and 2, that is, sequences (a_{1}, a_{2}, …, a_{j}) such that a_{1}+⋯+a_{j} = n and a_{i} ∈ {1, 2} for 1 ≤ i ≤ j. It is well-known that |C_{n}| = F_{n+1}, the (n + 1)th Fibonacci number, defined by the recurrence F_{0} = 0, F_{1} = 1 and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2. The integer sequence sequence F_{n} is listed as \underline{A000045} in the OEIS [22].

Proposition 27. There is a bijective correspondence between I_{n} (\underline{≥, ≤}) and C_{n}. In particular, |I_{n} (\underline{≥, ≤})| = F_{n+1}.

Proof. Given e ∈ I_{n} (\underline{≥, ≤}), we know by Lemma 26 that

e_{1} < e_{2} < ⋯ < e_{j} ≥ e_{j+1} > e_{j+2} > ⋯ > e_{n}

for some j. Since e is an inversion sequence, it follows that e_{i} = i − 1 for 1 ≤ i ≤ j.

Define f(e) = (a_{1}, a_{2}, …, a_{j}), where a_{i} is the number of entries in e that are equal to i − 1, for 1 ≤ i ≤ j. Note that f(e) ∈ C_{n} because, for each 1 ≤ i ≤ j, the sequence e has one or two entries equal to i − 1, and it has no entries larger than j − 1.

Let us show that f is a bijection by describing its inverse. Given (a_{1}, a_{2}, …, a_{j}) ∈ C_{n}, we recover the unique e ∈ I_{n} (\underline{≥, ≤}) such that f(e) = (a_{1}, a_{2}, …, a_{j}) as follows. First, set e_{i} = i − 1 for 1 ≤ i ≤ j. To define the remaining entries, let i range from 1 to j, and whenever a_{i} = 2, set the rightmost entry of e that has not been defined equal to e_{i}.

Example 28. Applying the bijection f from the above proof to the inversion sequences in Figure 4, we get f(012210) = (2, 2, 2) and f(012310) = (2, 2, 1, 1).

4.5 The pattern (\underline{≠, ≤})

As in previous subsections, we start by characterizing the inversion sequences avoiding this pattern.

Lemma 29. For n ≥ 1,

I_{n} (\underline{≠, ≤}) = \{e ∈ I_{n} : e_{1} = e_{2} = ⋯ = e_{j−1} < e_{j} > e_{j+1} > ⋯ > e_{n} for some 2 ≤ j ≤ n + 1\}.

Proof. The inclusion to the left is straightforward. For the inclusion to the right, take e ∈ I_{n} (\underline{≠, ≤}) and let 2 ≤ j ≤ n+1 be the largest integer such that 0 = e_{1} = e_{2} = ⋯ = e_{j−1}. If j ≤ n, then e_{j−1} < e_{j}. Furthermore, if j ≤ n − 1, then e_{j} > e_{j+1} because e avoids the pattern (\underline{≠, ≤}). The same argument shows that e_{j} > e_{j+1} > ⋯ > e_{n}.

Martinez and Savage [20, Thm. 12] proved that the inversion sequences in I_{n} (≠, ≤, −) are characterized by the same inequalities from Lemma 29, so we deduce that I_{n} (\underline{≠, ≤}) = I_{n} (≠, ≤, −). They also show that |I_{n} (≠, ≤, −)| = F_{n+2} −1 for n ≥ 1. This sequence is listed as \underline{A000071} in the OEIS [22]. The next corollary follows.

Corollary 30. For n ≥ 1, |I_{n} (\underline{≠, ≤})| = |I_{n} (≠, ≤, −)| = F_{n+2} − 1.

4.6 The patterns (\underline{≥, <}) ∼^{ss} (\underline{<, ≥}) ∼ (\underline{≠, ≥})

We have the following characterizations of inversion sequences avoiding these three patterns.

Lemma 31. For n ≥ 1,

I_{n} (\underline{<, ≥}) = I_{n} (\underline{≠, ≥}) = \{e ∈ I_{n} : e_{1} = e_{2} = ⋯ = e_{j} < e_{j+1} < ⋯ < e_{n} for some 1 ≤ j ≤ n\},

I_{n} (\underline{≥, <}) = \{e ∈ I_{n} : e_{1} < e_{2} < ⋯ < e_{j} ≥ e_{j+1} ≥ ⋯ ≥ e_{n} for some 1 ≤ j ≤ n\}.

Proof. We showed in the proof of Proposition 16 that I_{n} (\underline{<, ≥}) = I_{n} (\underline{≠, ≥}). Given e ∈ I_{n} (\underline{<, ≥}), let 1 ≤ j ≤ n be the largest integer such that 0 = e_{1} = e_{2} = ⋯ = e_{j}. If j < n, then e_{j} < e_{j+1}, and if j < n − 1, then e_{j+1} < e_{j+2} because e avoids the pattern (\underline{<, ≥}). An inductive argument shows that e_{j} < e_{j+1} < ⋯ < e_{n}.

The characterization of e ∈ I_{n} (\underline{≥, <}) can be obtained similarly by letting j be the largest integer such that e_{1} < e_{2} < ⋯ < e_{j}. Alternatively, it follows from the fact, shown in the proof of Proposition 15(i_{1}), that the map e → e^{C} sending each inversion sequence to its complement induces a bijection between I_{n} (\underline{≥, <}) and I_{n} (\underline{<, ≥}).

Martinez and Savage [20, Thm. 15] showed that the set I_{n} (≠, ≤, −) is also characterized by the same condition as in the first part of Lemma 31, and so I_{n} (\underline{<, ≥}) = I_{n} (\underline{≠, ≥}) = I_{n} (≠, ≤, −). In addition, there is a bijection between this set and the set of all subsets of [n − 1], obtained by mapping an inversion sequence to the set of its nonzero values. The next result now follows using Theorem 7(i).

Corollary 32. For n ≥ 1, |I_{n} (\underline{≥, <})| = |I_{n} (\underline{<, ≥})| = |I_{n} (\underline{≠, ≥})| = 2^{n−1}.

4.7 The pattern (\underline{≠, ≠})

Let I_{n} denote the set of involutions of [n], that is, permutations π ∈ S_{n} such that π^{−1} = π. We will show that there is a bijection between I_{n} (\underline{≠, ≠}) and I_{n}.

Proposition 33. There is a bijection Υ : I_{n} (\underline{≠, ≠}) → I_{n}. In particular, the number of inversion sequences avoiding (\underline{≠, ≠}) satisfies the recurrence

|I_{n} (\underline{≠, ≠})| = |I_{n−1} (\underline{≠, ≠})| + (n − 1) |I_{n−2} (\underline{≠, ≠})|  (3)

for n ≥ 2, with initial conditions |I_{0} (\underline{≠, ≠})| = |I_{1} (\underline{≠, ≠})| = 1, and its exponential generating function is

∑_{n≥0} |I_{n} (\underline{≠, ≠})| \frac{z}{n!} = exp (z + \frac{z^{2}}{2} ) .

Proof. We start by proving the recurrence (3), which will also inform the construction of the bijection Υ. The initial conditions are trivially satisfied. Let n ≥ 2, and let e ∈ I_{n} (\underline{≠, ≠}). If e_{n−1} = e_{n}, then e is obtained from an arbitrary inversion sequence in I_{n−1} (\underline{≠, ≠}) by repeating the last entry, so there are |I_{n−1} (\underline{≠, ≠})| inversion sequences with e_{n−1} = e_{n}. If e_{n−1} ≠ e_{n}, then we must have e_{n−2} = e_{n−1} (unless n = 2, in which case e = 01), since e avoids (\underline{≠, ≠}). In this case, e is obtained from an arbitrary inversion sequence in I_{n−2} (\underline{≠, ≠}) by repeating the last entry, and then appending any element from {0, 1, …, n − 1} \ {e_{n−2}}, for which there are n − 1 choices. Thus, there are (n − 1) |I_{n−2} (\underline{≠, ≠})| inversion sequences with e_{n−1} ≠ e_{n}. The recurrence is now proved.

It is well known that the number of involutions |I_{n}| satisfies the same recurrence. It follows that |I_{n} (\underline{≠, ≠})| = |I_{n}|, and that their exponential generating function is exp (z + \frac{z^{2}}{2} ).

To construct an explicit bijection Υ, let e ∈ I_{n} (\underline{≠, ≠}), and define Υ(e) ∈ S_{n} recursively as follows. For n = 0, define the image of the empty inversion sequence to be the empty permutation; for n = 1, define Υ(0) = 1. For n ≥ 2, let i ∈ [n] be such that e_{n} − e_{n−1} ≡ i (mod n).

• If i = n, let σ = Υ (e_{1}e_{2} ⋯ e_{n−1}), and define Υ(e) = σ_{1}σ_{2} ⋯ σ_{n−1} n.

• If i ≠ n, let σ be the permutation of [n − 1]\ {i} with reduction Υ (e_{1}e_{2} ⋯ e_{n−2}), and define Υ(e) = σ_{1}σ_{2} ⋯ σ_{i−1} n σ_{i}σ_{i+1} ⋯ σ_{n−2} i.

The inverse map Υ^{−1} is defined recursively as follows. Given σ ∈ I_{n} with n ≥ 2 (the cases n = 0 and n = 1 are trivial), let i = σ_{n}.

• If i = n, let e_{1}e_{2} ⋯ e_{n−1} = Υ^{−1} (σ_{1}σ_{2} ⋯ σ_{n−1}), and define Υ^{−1}(σ) = e_{1}e_{2} ⋯ e_{n−1}e_{n−1}.

• If i ≠ n, let σ′ be the reduction of σ_{1}σ_{2} ⋯ σ_{i−1}σ_{i+1}σ_{i+2} ⋯ σ_{n−1}, and let e_{1}e_{2} ⋯ e_{n−2} = Υ^{−1}(σ′). Define Υ^{−1}(σ) = e_{1}e_{2} ⋯ e_{n−2}e_{n−2}k, where 0 ≤ k < n is the unique integer satisfying k ≡ e_{n−2} + i (mod n).

Example 34. Consider e = 00114. Computing Υ (e_{1}e_{2} ⋯ e_{i}) recursively yields: Υ(0) = 1, Υ(00) = 12, Υ(001) = 321, Υ(0011) = 3214, and Υ(e) = 42513.

Both maps Υ^{−1} (from the proof of Proposition 33) and Θ (from Equation (1)) give encodings of involutions as inversion sequences, but they do not coincide in general. For instance, if π = 42513, then Υ^{−1}(π) = 00114 ≠ 01032 = Θ(π).

4.8 The pattern (\underline{≤, >})

We show that inversion sequences avoiding this pattern are those that are weakly increasing, and that they are in bijection with Dyck paths.

Lemma 35. For n ≥ 1,

I_{n} (\underline{≤, >}) = \{e ∈ I_{n} : e_{1} ≤ e_{2} ≤ ⋯ ≤ e_{n}\}.

Proof. If e ∈ I_{n} (\underline{≤, >}), the fact that 0 = e_{1} ≤ e_{2} implies that e_{2} ≤ e_{3}, assuming these entries are defined. The remaining inequalities follow by iterating the same argument.

A Dyck path of semilength n is a lattice path in ℤ^{2} from (0, 0) to (n, n) consisting of vertical steps N = (0, 1) and horizontal steps E = (1, 0), which never goes above the line y = x. Denoting by D_{n} the set of such paths, it is well-known that |D_{n}| = C_{n} = \frac{1}{n+1} \binom{2n}{n}, the n-th Catalan number, and that

C(z) := ∑_{n≥0} C_{n}z^{n} = \frac{1 − \sqrt{1 − 4z}}{2z} .  (4)

The sequence C_{n} is one of the most ubiquitous sequences in enumerative combinatorics [24], and it is listed as \underline{A000108} in the OEIS [22].

Proposition 36. Let n ≥ 1 and 0 ≤ k < n. Then

|I_{n} (\underline{≤, >})| = C_{n} = \frac{1}{n + 1}\binom{2n}{n}.

Proof. Using Lemma 35, we obtain a straightforward bijection between I_{n} (\underline{≤, >}) and D_{n} by appending n − e_{n} steps N to our usual representation of an inversion sequence e ∈ I_{n} (\underline{≤, >}) as an underdiagonal lattice path, see Figure 5.

Figure 5: Representation of e = 001123 ∈ I_{6} (\underline{≤, >}) as an underdiagonal lattice path. Adding the last vertical step we obtain the Dyck path EENNEENNENEN.

4.9 The pattern (\underline{>, ≤})

We characterize inversion sequences avoiding this pattern in terms of an asymmetric unimodality condition.

Lemma 37. For n ≥ 1,

I_{n} (\underline{>, ≤}) = \{e ∈ I_{n} : e_{1} ≤ e_{2} ≤ ⋯ ≤ e_{j} > e_{j+1} > ⋯ > e_{n} for some 1 ≤ j ≤ n\}.

Proof. Given e ∈ I_{n} (\underline{>, ≤}), let 1 ≤ j ≤ n be the smallest index such that e_{j} > e_{j+1}, or let j = n if there is no such index. Since e avoids (\underline{>, ≤}), we must have e_{j} > e_{j+1} > ⋯ > e_{n}. The characterization follows.

Martinez and Savage [20, Sec. 2.19] showed that inversion sequences in I_{n} (>, ≤, −) are those satisfying the same inequalities from Lemma 37, and so

I_{n} (\underline{>, ≤}) = I_{n} (>, ≤, −) .  (5)

They also conjecture that |I_{n} (>, ≤, −)| is given by sequence \underline{A071356} in the OEIS [22]; equivalently, that Theorem 10 holds. To prove their conjecture, we introduce certain lattice paths.

Definition 38. A marked Dyck path P is an underdiagonal lattice path from (0, 0) to some point in the diagonal, with horizontal steps E = (1, 0) and two possible kinds of vertical steps (0, 1), denoted by N and N^{∗} (the latter are called marked steps). Denoting by E(P), N(P) and N^{∗}(P), the number of E, N and N^{∗} steps in P, respectively, the size of P is defined as N^{∗}(P) + E(P) = N(P) + 2N^{∗}(P). Let P_{n} denote the set of marked Dyck paths of size n.

If a marked Dyck path P has at least one N^{∗} step in the last run of vertical steps, then we say that P has a marked tail. Otherwise, we say that P has an unmarked tail. We denote by R_{n} the set of paths in P_{n} with an unmarked tail.

Example 39. The marked Dyck path P_{1} = ENEN^{∗} has size 3 and a marked tail, so P_{1} ∈ P_{3} \R_{3}. On the other hand, P = ENEN^{∗}EEN^{∗}EENNN has size 8 and an unmarked tail, so P ∈ R_{8}. These paths are drawn in Figure 6, with a ∗ indicating which vertical steps are N^{∗} steps.

Figure 6: The marked Dyck path R = ENEN^{∗}EEN^{∗}EENNN ∈ R_{8} may be decomposed as R = P_{1}EP_{2}N, with P_{1} = ENEN^{∗} ∈ P_{3} and P_{2} = EN^{∗}EENN ∈ R_{4}.

Next we prove Theorem 10, which gives a generating function for the sequence |I_{n} (\underline{>, ≤})| = |I_{n} (>, ≤, −)|.

Proof of Theorem 10. First, we describe a bijection φ between I_{n} (\underline{>, ≤}) (which, by Equation (5), equals I_{n} (>, ≤, −)) and R_{n}. Let e ∈ I_{n} (\underline{>, ≤}). By Lemma 37, there exists 1 ≤ j ≤ n such that e_{1} ≤ e_{2} ≤ ⋯ ≤ e_{j} > e_{j+1} > ⋯ > e_{n}. Let P be the corresponding underdiagonal lattice path from (0, 0) to the line x = n, using steps N = (0, 1), S = (0, −1) and E = (1, 0), having n steps E at heights given by e_{1}, …, e_{n}. We construct φ(e) ∈ R_{n} as follows; see Figure 7(a)(b) for an example.

1) For every E step in the descending portion of P (that is, to the right of the line x = j), which corresponds to an entry e_{i} with i > j, mark the N step in the ascending portion of P going from height e_{i} to height e_{i} + 1, turning it into an N^{∗} step.

2) Erase the descending portion of P, and instead append j − e_{j} N steps. Let φ(e) ∈ R_{n} be the resulting path from the origin to (j, j).

It is clear that φ : I_{n} (\underline{>, ≤}) → R_{n} is a bijection, so it suffices to enumerate R_{n}.

For n ≥ 1, every R ∈ R_{n} can be decomposed uniquely as R = P_{1}EP_{2}N, where P_{1} ∈ P_{j} and P_{2} ∈ R_{n−j−1} for some 0 ≤ j ≤ n − 1 (see Figure 6 for an example). It follows that if we define P (z) = ∑_{n≥0} |P_{n}| z^{n} and R(z) = ∑_{n≥0} |R_{n}| z^{n}, these generating functions are related by R(z) = 1 + z P (z)R(z), and so

R(z) = \frac{1}{1 − z P (z)}.

(a)  (b)  (c)

Figure 7: (a) The inversion sequence e = 011344421 ∈ I_{9} (\underline{>, ≤}) represented as the underdiagonal lattice path P = ENEENNENEEESSESE. (b) Its corresponding marked Dyck path φ(e) = ENEEN^{∗}N^{∗}ENEEENNN ∈ R_{9}. (c) The path R′ = ENEEDDENEEE ∈ R′_{8} corresponding to e under the bijection φ′.

To find P (z), think of marked Dyck paths as Dyck paths with two kinds of vertical steps: N (contributing 1 to the size) and N^{∗} (contributing 2 to the size), whereas E steps do not contribute to the size. If follows that P (z) = C(z + z^{2}), with C(z) given by Equation (4). Indeed, the monomials z and z^{2} account for the choice of N and N^{∗} steps, respectively. We deduce that

R(z) = \frac{1}{1 − z C(z + z^{2})} = \frac{2 + 2z}{1 + 2z + \sqrt{1 − 4z − 4z^{2}}} = \frac{1 + 2z − \sqrt{1 − 4z − 4z^{2}}}{4z} .

Martinez and Savage’s original conjecture [20, Sec. 2.19] stated that |I_{n} (>, ≤, −)| coincides with sequence \underline{A071356} in the OEIS [22], which enumerates the sets R′_{n} consisting of underdiagonal paths from (0, 0) to the line x = n with steps N, E and D = (1, 2). Even though Theorem 10 already proves their conjecture, we can also give a direct bijective proof, by exhibiting a bijection between I_{n} (>, ≤, −) and R′_{n−1}. Indeed, given e ∈ I_{n} (>, ≤, −), we can construct its corresponding marked Dyck path with an unmarked tail, R = φ(e) ∈ R_{n}. Replacing each marked step N^{∗} in R by a D step and deleting the last run of N steps as well as the E step immediately preceding it, we obtain a path R′ ∈ R′_{n−1} (see Figure 7(c) for an example). Defining φ′(e) = R′, it is straightforward to verify that φ′ is a bijection between I_{n} (>, ≤, −) and R′_{n−1}.

For e ∈ I_{n}, define the statistic dist(e) = |{e_{1}, e_{2}, …, e_{n}}|, that is, the number of distinct entries of e. Using numerical evidence, Martinez and Savage [20, Sec. 2.19] also conjecture that the distribution of this statistic is symmetric on I_{n} (>, ≤, −). Next we prove this conjecture by interpreting the statistic dist in terms of marked Dyck paths, and finding the corresponding bivariate generating function refining Theorem 10.

Theorem 40.

∑_{n≥0} ∑_{e∈I_{n}(\underline{>,≤})} z^{n}t^{dist(e)} = \frac{1 + z(3 − t) − \sqrt{1 − z (2 + 2t − z + 6zt − zt^{2})}}{4z}.

Proof. Let e ∈ I_{n} (\underline{>, ≤}), and let R = φ(e), where φ is the bijection in the proof of Theorem 10. Define an elbow of a path in P_{n} to be an occurrence of a horizontal step E immediately followed by a vertical step N or N^{∗}. Then dist(e) becomes the following statistic on R, which we also denote by dist with some abuse of notation:

dist(R) = # {elbows in R} + # {N^{∗} steps in R that are not part of an elbow} .

For instance, the marked Dyck path R = ENEEN^{∗}N^{∗}ENEEENNN in Figure 7(b) has 4 elbows and 1 marked step that is not part of an elbow, so dist(R) = 5. Define the bivariate generating functions

R(z, t) = ∑_{n≥0} ∑_{R∈R_{n}} z^{n}t^{dist(R)} = ∑_{n≥0} ∑_{e∈I_{n}(\underline{>,≤})} z^{n}t^{dist(e)} and P (z, t) = ∑_{n≥0} ∑_{P ∈P_{n}} z^{n}t^{dist(P)}.

Decomposing R ∈ R_{n} for n ≥ 1 as R = P_{1}EP_{2}N, where P_{1} ∈ P_{j} and P_{2} ∈ R_{n−j−1} for some 0 ≤ j ≤ n−1, and noting that the last two steps of R form an elbow when P_{2} is empty, we get the equation

R(z, t) = 1 + zt P (z, t) + z P (z, t) (R(z, t) − 1) ,

and so

R(z, t) = \frac{1 − z(1 − t)P (z, t)}{1 − z P (z, t)}.  (6)

To find P (z, t), note that if a marked Dyck path P is irreducible (i.e., it is nonempty and it returns to the diagonal only at the end), then P = EP′N or P = EP′N^{∗}, where P′ is a marked Dyck path. When P′ is empty, such paths P contribute zt + z^{2}t to the generating function, since they consist of an elbow; when P′ is nonempty, they contribute (z + z^{2}t) (P (z, t) − 1). Since every path in P_{n} can be decomposed uniquely as a sequence of irreducible paths, we deduce that

P (z, t) = \frac{1}{1 − [zt + z^{2}t + (z + z^{2}t) (P (z, t) − 1)]}.

Solving for P (z, t) and taking the solution without negative powers in its series expansion, we find that

P (z, t) = \frac{1 + z(1 − t) − \sqrt{(1 + z(1 − t))^{2} − 4 (z + z^{2}t)}}{2 (z + z^{2}t)}.

It then follows from Equation (6) that

R(z, t) = \frac{1 + z(3 − t) − \sqrt{1 − z (2 + 2t − z + 6zt − zt^{2})}}{4z}.

In Section 5 we will show how the argument in the proof of Theorem 40 can be generalized to find bivariate generating functions for the number of inversion sequences e satisfying certain unimodality conditions, with respect to the length of e and dist(e).

Now we can finally show that the statistic dist has a symmetric distribution on I_{n} (>, ≤, −) = I_{n} (\underline{>, ≤}), proving Martinez and Savage’s conjecture.

Corollary 41. For all n ≥ d ≥ 1,

|\{e ∈ I_{n} (\underline{>, ≤}) : dist(e) = d\}| = |\{e ∈ I_{n} (\underline{>, ≤}) : dist(e) = n + 1 − d\}|.

Proof. Write R(z, t) = ∑_{n≥0} U_{n}(t)z^{n}, where U_{n}(t) = ∑_{e∈I_{n}(\underline{>,≤})} t^{dist(e)} = ∑_{i=1}^{n} u_{i,n}t^{i}. Then

t R (zt, \frac{1}{t}) = t + t ∑_{n≥1} (u_{1,n} \frac{1}{t} + u_{2,n} \frac{1}{t^{2}} + ⋯ + u_{n,n} \frac{1}{t^{n}} ) (zt)^{n}

= t + ∑_{n≥1} (u_{1,n}t^{n} + u_{2,n}t^{n−1} + ⋯ + u_{n,n}t) z^{n}.

Thus, in order to prove that u_{d,n} = u_{n+1−d,n} for n ≥ d ≥ 1, it is enough to show that R(z, t) − 1 = t R (zt, \frac{1}{t}) − t. This is now immediate from Theorem 40, since

t R (zt, \frac{1}{t}) − t = \frac{1 − z(1 + t) − \sqrt{1 − z (2 + 2t − z + 6zt − zt^{2})}}{4z} = R(z, t) − 1.

A different proof of this corollary, showing γ-positivity of U_{n}(t), has recently been given by Cao, Jin, and Lin [9, Them. 5.1].

4.10 The pattern (\underline{=, ≠})

The characterization of inversion sequences avoiding this pattern is relatively simple.

Lemma 42. For n ≥ 1,

I_{n} (\underline{=, ≠}) = \{e ∈ I_{n} : e_{1} ≠ e_{2} ≠ ⋯ ≠ e_{j} = e_{j+1} = ⋯ = e_{n} for some 1 ≤ j ≤ n\}.

Proof. Given e ∈ I_{n} (\underline{=, ≠}), let 1 ≤ j ≤ n−1 be the smallest index such that e_{j} = e_{j+1}, or let j = n if there is not such index. Since e avoids (\underline{=, ≠}), we must have e_{j} = e_{j+1} = ⋯ = e_{n}.

Next we use this characterization to find a formula for |I_{n} (\underline{=, ≠})|. The corresponding sequence, which is listed as \underline{A003422} in the OEIS [22], is sometimes referred to as the left factorial of n.

Proposition 43. For n ≥ 1, |I_{n} (\underline{=, ≠})| = 0! + 1! + 2! + ⋯ + (n − 1)!.

Proof. By Lemma 42, we can express I_{n} (\underline{=, ≠}) as a disjoint union ⨆_{j=1}^{n} A_{n,j}, where A_{n,j} = {e ∈ I_{n} : e_{1} ≠ e_{2} ≠ ⋯ ≠ e_{j} = e_{j+1} = ⋯ = e_{n}}.

To specify an element e ∈ A_{n,j}, after setting e_{1} = 0, we have i − 1 choices for e_{i} for each 2 ≤ i ≤ j, because e_{i} ∈ {0, 1, …, i − 1} \ {e_{i−1}}. Once e_{j} is chosen, the entries e_{j+1}, e_{j+2}, …, e_{n} are forced. It follows that |A_{n,j}| = (j − 1)!, and consequently,

|I_{n} (\underline{=, ≠})| = ∑_{j=1}^{n} |A_{n,j}| = 0! + 1! + 2! + ⋯ + (n − 1)!.

4.11 The patterns (\underline{≥, ≥}) ∼^{ss} (\underline{<, <})

An occurrence of (\underline{<, <}) in an inversion sequence is precisely an occurrence of the consecutive pattern \underline{012}, so I_{n} (\underline{<, <}) = I_{n} (\underline{012}). It is known that if Θ : S_{n} → I_{n} is the map defined by (1) and π ∈ S_{n}, then π avoids the consecutive permutation pattern \underline{321} if and only Θ(π) avoids \underline{012} [1, Prop. 3.19]. Using Theorem 7(ii) and [13, Thm. 4.1], the next corollary follows.

Corollary 44 ([1, 13]). Let π ∈ S_{n}, and let e = Θ(π) be its corresponding inversion sequence. Then π avoids \underline{321} if and only e avoids (\underline{<, <}). In particular, |I_{n} (\underline{≥, ≥})| = |I_{n} (\underline{<, <})| = |I_{n} (\underline{012})| = |S_{n} (\underline{321})| for all n, and the corresponding exponential generating function is

∑_{n≥0} |I_{n} (\underline{<, <})| \frac{z^{n}}{n!} = \frac{\sqrt{3}}{2} \begin{matrix}exp & (z/2) \\ cos & (π/6 + \sqrt{3}z/2) \end{matrix}.

4.12 The pattern (\underline{≠, =})

The techniques in this section are similar to those in Section 4.10.

Lemma 45. For n ≥ 1,

I_{n} (\underline{≠, =}) = \{e ∈ I_{n} : e_{1} = e_{2} = ⋯ = e_{j} ≠ e_{j+1} ≠ ⋯ ≠ e_{n} for some 1 ≤ j ≤ n\}.

Proof. Given e ∈ I_{n} (\underline{≠, =}), let 1 ≤ j ≤ n − 1 be the smallest index such that e_{j} ≠ e_{j+1}, or let j = n if there is no such index. Since e avoids (\underline{≠, =}), we have e_{j} ≠ e_{j+1} ≠ ⋯ ≠ e_{n}.

We can use the description of inversion sequences avoiding the pattern (\underline{≠, =}) given by Lemma 45 to enumerate them. The corresponding sequence is listed as \underline{A000522} in the OEIS [22].

Proposition 46. For n ≥ 1, |I_{n} (\underline{≠, =})| = ∑_{i=0}^{n−1}(n − 1)!/i!.

Proof. By Lemma 45, we can express I_{n} (\underline{≠, =}) as a disjoint union ⨆_{j=1}^{n} A_{n,j}, where A_{n,j} = {e ∈ I_{n} : e_{1} = e_{2} = ⋯ = e_{j} ≠ e_{j+1} ≠ ⋯ ≠ e_{n}}.

To specify an element e ∈ A_{n,j}, after setting e_{1} = ⋯ = e_{j} = 0, we have i − 1 choices for e_{i} for each j + 1 ≤ i ≤ n, because e_{i} ∈ {0, 1, …, i − 1} \ {e_{i−1}}. Thus, |A_{n,j}| = j(j + 1) ⋯ (n − 1) = (n − 1)!/(j − 1)!, and

|I_{n} (\underline{≠, =})| = ∑_{j=1}^{n} |A_{n,j}| = ∑_{i=0}^{n−1} \frac{(n − 1)!}{i!}.

4.13 The patterns (\underline{≥, >}) ∼^{ss} (\underline{>, ≥})

We showed in Proposition 18 that |I_{n} (\underline{>, ≥})| = |I_{n} (\underline{≥, >})| = |S_{n} (\underline{124}3)|. This sequence appears as \underline{A200403} in the OEIS [22], but no closed-form formula for it is known.

We can obtain a recurrence to compute |I_{n} (\underline{>, ≥})| by introducing some refinements. Let I_{n,k} = \{e ∈ I_{n} : e_{n} = k\}, and define I_{n,k} (\underline{R_{1}, R_{2}}) = I_{n,k} ∩ I_{n} (\underline{R_{1}, R_{2}}) for any consecutive pattern of relations (\underline{R_{1}, R_{2}}). Note that I_{n} (\underline{R_{1}, R_{2}}) = ⨆_{k=0}^{n−1} I_{n,k} (\underline{R_{1}, R_{2}}), and that I_{n,k} (\underline{R_{1}, R_{2}}) = ∅ unless 0 ≤ k < n.

Proposition 19 shows that |I_{n,k} (\underline{>, ≥})| = |I_{n,k} (\underline{≥, >})|. To compute these numbers, we define

I_{n,k}^{>} (\underline{>, ≥}) = \{e ∈ I_{n,k} (\underline{>, ≥}) : e_{n−1} > e_{n}\} .

Proposition 47. For n ≥ 2, the sequences |I_{n,k} (\underline{>, ≥})| and |I_{n,k}^{>} (\underline{>, ≥})| satisfy the recurrences

|I_{n,k} (\underline{>, ≥})| = \begin{cases}|I_{n−1} (\underline{>, ≥})| , & if k = n − 1; \\ |I_{n,k+1} (\underline{>, ≥})| − |I_{n−1,k}^{>} (\underline{>, ≥})| , & if 0 ≤ k ≤ n − 2; \\ 0, & otherwise; \end{cases}  (7)

|I_{n,k}^{>} (\underline{>, ≥})| = \begin{cases}|I_{n,k+1}^{>} (\underline{>, ≥})| − |I_{n−1,k+1}^{>} (\underline{>, ≥})| + |I_{n−1,k+1} (\underline{>, ≥})| , & if 0 ≤ k ≤ n − 2; \\ 0, & otherwise; \end{cases}

(8)

with initial conditions |I_{1} (\underline{>, ≥})| = |I_{1,0} (\underline{>, ≥})| = 1, |I_{1,k} (\underline{>, ≥})| = 0 for k > 0, and |I_{1,k}^{>} (\underline{>, ≥})| = 0 for all k.

Equations (7) and (8) allow us to compute the values |I_{n,k} (\underline{>, ≥})| and |I_{n,k}^{>} (\underline{>, ≥})| recursively, since an entry indexed by (n, k) depends only on entries indexed by (n, j) where k < j < n, or by (n − 1, j) for some j.

Proof. Note that e ∈ I_{n,k} (\underline{>, ≥}) if and only if e_{n} = k and

e_{1}e_{2} … e_{n−1} ∈ I_{n−1} (\underline{>, ≥}) \ ⨆_{j=k}^{n−2} I_{n−1,j}^{>} (\underline{>, ≥}) ,

where the subtracted term guarantees that e_{n−2}e_{n−1}e_{n} is not an occurrence of (\underline{>, ≥}). Thus,

|I_{n,k} (\underline{>, ≥})| = |I_{n−1} (\underline{>, ≥})| − ∑_{j=k}^{n−2} |I_{n−1,j}^{>} (\underline{>, ≥})| .  (9)

In particular, this implies that |I_{n,n−1} (\underline{>, ≥})| = |I_{n−1} (\underline{>, ≥})|. If 0 ≤ k ≤ n − 2, then subtracting Equation (9) from the same equation with k + 1 substituted for k, we may write

|I_{n,k+1} (\underline{>, ≥})| − |I_{n,k} (\underline{>, ≥})| = |I_{n−1,k}^{>} (\underline{>, ≥})| .

This proves the recurrence (7).

Now, e ∈ I_{n,k}^{>} (\underline{>, ≥}) if and only if e_{n} = k and e_{1}e_{2} ⋯ e_{n−1} ∈ ⨆_{j=k+1}^{n−2} I_{n−1,j} (\underline{>, ≥}) \I_{n−1,j}^{>} (\underline{>, ≥}). Hence,

|I_{n,k}^{>} (\underline{>, ≥})| = ∑_{j=k+1}^{n−2} (|I_{n−1,j} (\underline{>, ≥})| − |I_{n−1,j}^{>} (\underline{>, ≥})|) .  (10)

In particular, |I_{n,n−1}^{>} (\underline{>, ≥})| = 0. If 0 ≤ k ≤ n − 2, then subtracting Equation (10) from the same equation with k + 1 substituted for k, we may write

|I_{n,k+1}^{>} (\underline{>, ≥})| − |I_{n,k}^{>} (\underline{>, ≥})| = − |I_{n−1,k+1} (\underline{>, ≥})| + |I_{n−1,k+1}^{>} (\underline{>, ≥})| .

This proves Equation (8).

More generally, for any R_{1}, R_{2} ∈ {≤, ≥, <, >, =, ≠}, we define the refinement

I_{n,k}^{R_{1}} (\underline{R_{1}, R_{2}}) = \{e ∈ I_{n,k} (\underline{R_{1}, R_{2}}) : e_{n−1}R_{1}e_{n}\} .  (11)

Then, arguing as in the proof of Proposition 47, we can write

|I_{n,k} (\underline{R_{1}, R_{2}})| = |I_{n−1} (\underline{R_{1}, R_{2}})| − ∑_{\begin{matrix}j=0 \\ jR_{2}k \end{matrix}}^{n−2} I_{n−1,j}^{R_{1}} (\underline{R_{1}, R_{2}})

and

|I_{n,k}^{R_{1}} (\underline{R_{1}, R_{2}})| = ∑_{\begin{matrix}j=0 \\ jR_{1}k \end{matrix}}^{n−2} |I_{n−1,j} (\underline{R_{1}, R_{2}})| − ∑_{\begin{matrix}j=0 \\ jR_{1}k, jR_{2}k \end{matrix}}^{n−2} I_{n−1,j}^{R_{1}} (\underline{R_{1}, R_{2}}) .

These two equations can be simplified, depending on R_{1} and R_{2}, to obtain recurrences analogous to Equations (7) and (8), which allow us to compute the values |I_{n,k} (\underline{R_{1}, R_{2}})| and |I_{n,k}^{R_{1}} (\underline{R_{1}, R_{2}})| recursively. In particular, we can obtain such recurrences for each of the 12 Wilf equivalence classes of consecutive patterns of relations mentioned in the beginning of Section 4, for which |I_{n} (\underline{R_{1}, R_{2}})| does not match any sequence in the OEIS [22].

We remark that, even though |I_{n,k} (\underline{>, ≥})| = |I_{n,k} (\underline{≥, >})| by Proposition 19, the resulting recurrences involving the refinements in (11) are different. In particular, while the quantities |I_{n,k}^{>} (\underline{>, ≥})| and |I_{n,k}^{≥} (\underline{≥, >})| are not equal in general, one can show that |I_{n,k}^{>} (\underline{>, ≥})| = |I_{n,k+1}^{≥} (\underline{≥, >})| for all n and k.

4.14 The pattern (\underline{=, =})

An occurrence of (\underline{=, =}) in an inversion sequence is precisely an occurrence of the consecutive pattern \underline{000}, so I_{n} (\underline{=, =}) = I_{n} (\underline{000}). The next proposition rephrases a known result about inversion sequences that avoid \underline{000}, see [1, Prop. 3.1 and Cor. 3.3]. We use d_{n} to denote the number of derangements of length n, i.e., the number of permutations in S_{n} with no fixed points.

Proposition 48 ([1]). The sequence |I_{n} (\underline{=, =})| satisfies the recurrence

|I_{n} (\underline{=, =})| = (n − 1) |I_{n−1} (\underline{=, =})| + (n − 2) |I_{n−2} (\underline{=, =})|

for n ≥ 3, with initial terms |I_{1} (\underline{=, =})| = 1 and |I_{2} (\underline{=, =})| = 2. It follows that

|I_{n} (\underline{=, =})| = \frac{(n + 1)! − d_{n+1}}{n} .

5 Inversion sequences satisfying unimodality conditions

In Lemma 37 we enumerated inversion sequences satisfying a unimodality condition, which, as observed by Martinez and Savage [20, Sec. 2.19], are precisely those inversion sequences avoiding the pattern (>, ≤, −). This is one of 10 triples of binary relations of the form (R_{1}, R_{2}, R_{3}) such that I_{n} (R_{1}, R_{2}, R_{3}) is characterized by some type of unimodality condition. Martinez and Savage [20] carried out the enumeration of the inversion sequences in each case, with the results summarized in Table 3.

Martinez and Savage [20] obtain these via ad hoc methods. In this section, we provide a unified approach, generalizing the method that we used in Section 4.9 to prove Theorem 10, in order to recover their results. Furthermore, we find bivariate generating functions keeping track of the statistic dist (recording the number of distinct entries), in analogy to Theorem 40, for each of the patterns in Table 3. For a triple of relations (R_{1}, R_{2}, R_{3}), define

I_{(R_{1},R_{2},R_{3})}(z, t) = ∑_{n≥0} ∑_{e∈I_{n}(R_{1},R_{2},R_{3})} z^{n}t^{dist(e)}.

We begin by considering the pattern (>, <, −), and noting that I_{n} (>, ≤, −) ⊆ I_{n} (>, <, −). We generalize Definition 38 by allowing different kinds of marked steps in a Dyck path.

Definition 49. A multi-marked Dyck path P is an underdiagonal path from (0, 0) to some point in the diagonal, with horizontal steps E = (1, 0) and infinitely many possible kinds of vertical steps (0, 1), denoted by N and N_{t}^{∗} for t ≥ 2 (the latter are called marked steps). Denoting by E(P), N(P) and N_{t}^{∗}(P) the number of E, N and N_{t}^{∗} steps in P, respectively, the size of P is defined as

E(P) + ∑_{t≥2}(t − 1)N_{t}^{∗}(P) = N(P) + ∑_{t≥2} t N_{t}^{∗}(P).

Pattern (R_{1}, R_{2}, R_{3}) OEIS[22] Unimodality condition for e ∈ I_{n} (R_{1}, R_{2}, R_{3}) |I_{n} (R_{1}, R_{2}, R_{3})| counted

by

(<, −, <)  \underline{A000124} ∃j : e_{1} = ⋯ = e_{j} ≤ e_{j+1} ≥ 0 = ⋯ = 0  1 + \binom{n}{2}
(≠, <, −)  \underline{A000325} ∃j : e_{1} = ⋯ = e_{j} ≤ e_{j+1} ≥ e_{j+2} ≥ ⋯ ≥ e_{n}  2^{n} − n
(≠, ≤, −)  \underline{A000071} ∃j : e_{1} = ⋯ = e_{j} < e_{j+1} > e_{j+2} > ⋯ > e_{n}  F_{n+2} − 1
(>, <, −)  \underline{A033321} ∃j : e_{1} ≤ ⋯ ≤ e_{j} > e_{j+1} ≥ e_{j+2} ≥ ⋯ ≥ e_{n}  OGF is \frac{1+z−\sqrt{1−6z+5z^{2}}}{2z(2−z)}
(>, ≤, −)  \underline{A071356} ∃j : e_{1} ≤ ⋯ ≤ e_{j} > e_{j+1} > e_{j+2} > ⋯ > e_{n}  OGF is \frac{1+2z−\sqrt{1−4z−4z^{2}}}{4z}
(>, ≠, −)  \underline{A279561} ∃j : e_{1} ≤ ⋯ ≤ e_{j} ≥ e_{j+1} = e_{j+2} = ⋯ = e_{n}  1 + ∑_{i=1}^{n−1} \binom{2i}{i−1}
(≥, ≠, −)  \underline{A000124} ∃j : e_{1} < ⋯ < e_{j} ≥ e_{j+1} = e_{j+2} = ⋯ = e_{n}  1 + \binom{n}{2}
(=, <, −)  \underline{A000079} ∃j : e_{1} < ⋯ < e_{j} ≥ e_{j+1} ≥ e_{j+2} ≥ ⋯ ≥ e_{n}  2^{n−1}
(=, ≤, −)  \underline{A000045} ∃j : e_{1} < ⋯ < e_{j} ≥ e_{j+1} > e_{j+2} > ⋯ > e_{n}  F_{n+1}
(≥, ≤, ≠)  \underline{A000071} ∃(j ≤ i) : e_{1} < ⋯ < e_{j} = ⋯ = e_{i} > ⋯ > e_{n} F_{n+2} − 1

Table 3: Patterns (R_{1}, R_{2}, R_{3}) for which I_{n} (R_{1}, R_{2}, R_{3}) is characterized by a unimodality condition. These enumerative results are due to Martinez and Savage [20]. Patterns are listed in the same order they use, rather than in our usual order (least avoided to most avoided).

We denote by P̃_{n} the set of multi-marked Dyck paths of size n.

If P ∈ P̃_{n} has at least one N_{t}^{∗} step in the last run of vertical steps, then we say that P has a marked tail. Otherwise, we say that P has an unmarked tail. We denote by R̃_{n} the set of paths in P̃_{n} with an unmarked tail.

Multi-marked Dyck paths generalize marked Dyck paths from Definition 38, in the sense that any marked Dyck path in P_{n}, after replacing N^{∗} steps with N_{2}^{∗} steps, can be seen as a multi-marked Dyck path in P̃_{n} containing no steps N_{t}^{∗} with t ≥ 3. Hence, P_{n} ⊆ P̃_{n} and R_{n} ⊆ R̃_{n}.

Example 50. The multi-marked Dyck path R = ENEEN_{4}^{∗}N_{2}^{∗}ENEN_{3}^{∗}EN has size 12, so R ∈ P̃_{12}. In fact, R has an unmarked tail, so R ∈ R̃_{12}. This path is drawn on the right of Figure 8(b).

Theorem 51.

I_{(>,<,−)}(z, t) = \frac{1 + z(2 − t) − z^{2}(1 − t) − (1 − z)\sqrt{(1 + z − zt)^{2} − \frac{4z(1−z+zt)}{1−z}}}{2z(2 − z)} .

Proof. We begin by describing a bijection φ : I_{n} (>, <, −) → R̃_{n}, generalizing the bijection in the proof of Theorem 10, which was between I_{n} (>, ≤, −) and R_{n}.

Let e ∈ I_{n} (>, <, −), and let j be such that e_{1} ≤ e_{2} ≤ ⋯ ≤ e_{j} > e_{j+1} ≥ e_{j+2} ≥ ⋯ ≥ e_{n}. Let P be the corresponding underdiagonal lattice path from (0, 0) to the line x = n, with

(a)  (b)

Figure 8: (a) The inversion sequence e = 011345442111 ∈ I_{12} (>, <, −) represented as the underdiagonal lattice path P = ENEENNENENESEESSESEEE. (b) Its corresponding multi-marked Dyck path R = ENEEN_{4}^{∗}N_{2}^{∗}ENEN_{3}^{∗}EN ∈ R̃_{12}.

E steps at heights e_{1}, …, e_{n}, and the necessary N and S steps in between. We construct φ(e) ∈ R̃_{n} as follows; see Figure 8 for an example.

1) For every maximal run of consecutive E steps in the descending portion of P (to the right of x = j), which corresponds to entries e_{i} = e_{i+1} = ⋯ = e_{i+t−2} with i > j and t ≥ 2, turn the N step in the ascending portion of P going from height e_{i} to height e_{i} + 1 into an N_{t}^{∗} step.

2) Erase the descending portion of P, and instead append j − e_{j} N steps . Let φ(e) ∈ R̃_{n} be the resulting path from the origin to (j, j).

It is clear that φ is a bijection, so |I_{n} (>, <, −) | = |R̃_{n}|. In the rest of the proof we count multi-marked Dyck paths with an unmarked tail, mimicking the proof of Theorem 40.

Define an elbow of a path in P̃_{n} to be a consecutive occurrence of EN or EN_{t}^{∗} for some t ≥ 2. If e ∈ I_{n} (>, <, −) and R = φ(e), then dist(e) equals the following statistic on R, which we also denote by dist:

dist(R) = # {elbows in R} + ∑_{t≥2} # {N_{t}^{∗} steps in R that are not part of an elbow} .

Now we find expressions for the generating functions

R̃(z, t) = ∑_{n≥0} ∑_{R∈R̃_{n}} z^{n}t^{dist(R)} = I_{(>,<,−)}(z, t) and P̃(z, t) = ∑_{n≥0} ∑_{P ∈P̃_{n}} z^{n}t^{dist(P)}.

An identical argument to the one we used to deduce Equation (6) yields

R̃(z, t) = \frac{1 − z(1 − t)P̃(z, t)}{1 − zP̃(z, t)},  (12)

so it is enough to compute P̃(z, t).

If P is an irreducible multi-marked Dyck path, then there is a unique multi-marked Dyck path P′ such that either P = EP′N or P = EP′N_{t}^{∗} for some t ≥ 2. Paths P for which P′ is empty contribute zt + \frac{z^{2}t}{1−z} to the generating function P̃(z, t), because in this case P is an elbow. On the other hand, paths P for which P′ is nonempty contribute (z + \frac{z^{2}t}{1−z}) (P̃(z, t) − 1) to P̃(z, t). Given that every path in P̃_{n} has a unique decomposition as a sequence of irreducible multi-marked Dyck paths, it follows that

P̃(z, t) = \frac{1}{1 − [z(t − 1) + (z + \frac{z^{2}t}{1−z}) P̃(z, t)]}.

Solving for P̃(z, t) yields

P̃(z, t) = \frac{(1 − z) (1 + z − zt − \sqrt{(1 + z − zt)^{2} − 4 (z \frac{z^{2}t}{1−z})})}{2z(1 − z + zt)}.

Hence, Equation (12) implies that

R̃(z, t) = \frac{1 + z(2 − t) − z^{2}(1 − t) + (z − 1)\sqrt{(1 + z − zt)^{2} + \frac{4z(1−z+zt)}{z−1}}}{2z(2 − z)} .

By setting t = 1 in Theorem 51, we find that

∑_{n≥0} |I_{n} (>, <, −)| z^{n} = \frac{1 + z − \sqrt{1 − 6z + 5z^{2}}}{2z(2 − z)} ,  (13)

which appears as \underline{A033321} in the OEIS [22]. This is also the generating function for |S_{n} (2143, 3142, 4132)|, that is, permutations simultaneously avoiding the classical patterns 2143, 3142 and 4132 [6, Lem. 3.2]. Burstein and Stromquist [8] point out that π → Θ (π^{RC}) is a bijection between S_{n} (2143, 3142, 4132) and I_{n} (>, <, −).

In Section 4.9 we provided a bijection between I_{n} (>, ≤, −) and R′_{n−1}. To extend this construction to inversion sequences avoiding (>, <, −), let R̃′_{n} be the set of underdiagonal paths from (0, 0) to the line x = n with steps N, E and D_{t} = (t − 1, t) for t ≥ 2, and note that R′_{n} ⊆ R̃′_{n}. We construct a bijection between I_{n} (>, <, −) and R̃′_{n−1} as follows. Given e ∈ I_{n} (>, <, −), first let R ∈ R̃_{n} be its corresponding multi-marked Dyck path with an unmarked tail. Then replace each marked step N_{t}^{∗} in R by a step D_{t}, and delete the last run of N steps as well as the E step immediately preceding it, to obtain a path R′ ∈ R̃′_{n−1} (see Figure 9 for an example). It follows from this bijection and Equation (13) that

∑_{n≥0} |R̃′_{n}| z^{n} = \frac{1 − 3z + 2z^{2} − \sqrt{1 − 6z + 5z^{2}}}{2z^{2}(2 − z)} .

Figure 9: The path R′ = ENEED_{4}D_{2}ENED_{3} ∈ R̃′_{11} corresponding to e = 011345442111 (from Figure 8) under the bijection I_{12}(>, <, −) → R̃′_{11}.

Let (R_{1}, R_{2}, R_{3}) be one of the patterns listed in Table 3. Then I_{n} (R_{1}, R_{2}, R_{3}) ⊆ I_{n} (>, <, −). Indeed, Table 3 shows that the unimodality condition characterizing I_{n} (R_{1}, R_{2}, R_{3}) is weaker than that characterizing I_{n} (>, <, −). Hence, an inversion sequence e ∈ I_{n} (R_{1}, R_{2}, R_{3}) can still be represented as a multi-marked Dyck path φ(e) with an unmarked tail, where φ is the bijection in the proof of Theorem 51. For each pattern in Table 3, φ induces a bijection between I_{n} (R_{1}, R_{2}, R_{3}) and a subset of R̃_{n}, which can be characterized as shown in Table 4. These descriptions allow us to find the following expressions for I_{(R_{1},R_{2},R_{3})}(z, t) using the symbolic method.

Theorem 52. For patterns (R_{1}, R_{2}, R_{3}) such that I_{n} (R_{1}, R_{2}, R_{3}) is characterized by unimodality conditions, the generating functions I_{(R_{1},R_{2},R_{3})}(z, t) are as follows:

I_{(<,−,<)}(z, t) = \frac{1 − 3z + zt + 3z^{2} − 2z^{2}t + z^{2}t^{2} − z^{3} + z^{3}t}{(1 − z)^{3}},  (14)

I_{(≠,<,−)}(z, t) = \frac{1 − 4z + zt + 6z^{2} − 4z^{2}t + z^{2}t^{2} − 4z^{3} + 5z^{3}t − z^{3}t^{2} + z^{4} − 2z^{4}t + z^{4}t^{2}}{(1 − z)^{2}(1 − 2z + z^{2} − z^{2}t)} ,

I_{(≠,≤,−)}(z, t) = \frac{1 − 2z + zt + z^{2} − 2z^{2}t + z^{2}t^{2} + z^{3}t}{(1 − z)(1 − z − z^{2}t)},

I_{(>,<,−)}(z, t) = \frac{1 + z(2 − t) − z^{2}(1 − t) − (1 − z)\sqrt{(1 + z − zt)^{2} − \frac{4z(1−z+zt)}{1−z}}}{2z(2 − z)} ,  (15)

I_{(>,≤,−)}(z, t) = \frac{1 + z(3 − t) − \sqrt{1 − z (2 + 2t − z + 6zt − zt^{2})}}{4z},  (16)

I_{(>,≠,−)}(z, t) = \frac{1 − 2z + z^{2}(1 − t)^{2} + (1 − z + zt)\sqrt{(1 + z − zt)^{2} − 4z}}{2(1 − z)\sqrt{(1 + z − zt)^{2} − 4z}} ,

I_{(≥,≠,−)}(z, t) = \frac{1 − z − zt + 2z^{2}t}{(1 − z)(1 − zt)^{2}},  I_{(=,<,−)}(z, t) = \frac{1 − z}{1 − z − zt},
I_{(=,≤,−)}(z, t) = \frac{1}{1 − zt − z^{2}t},  I_{(≥,≤,≠)}(z, t) = \frac{1 − z + z^{3}t}{(1 − z)(1 − zt − z^{2}t)}.

Equations (15) and (16) are restatements of Theorems 51 and 40, respectively, included here for the sake of completeness. By setting t = 1 in the generating functions I_{(R_{1},R_{2},R_{3})}(z, t) in Theorem 52, we obtain expressions for ∑_{n≥0} |I_{n} (R_{1}, R_{2}, R_{3})| z^{n} in each case, from where one can recover the results listed in Table 3.

Pattern (R_{1}, R_{2}, R_{3}) Description of paths in φ (I_{n} (R_{1}, R_{2}, R_{3})) ⊆ R̃_{n}
(<, −, <)  empty path; or E^{r_{1}}(N_{t}^{∗})^{r_{2}}N^{r_{3}}EN^{r_{4}}, where r_{2} = 0, 1 and r_{4} > 0
(≠, <, −)

E^{r}N^{r}; or E^{r_{1}}P E^{r_{2}}N^{r_{3}}, where P is a nonempty path with steps N_{t}^{∗} and N, and r_{1}, r_{2}, r_{3} > 0

(≠, ≤, −)

E^{r}N^{r}; or E^{r_{1}}P EN^{r_{2}}, where P is a nonempty path with steps N_{2}^{∗} and N, and r_{1}, r_{2} > 0

(>, <, −)  any path in R̃_{n}
(>, ≤, −)  contains no N_{t}^{∗} steps for t ≥ 3
(>, ≠, −)  contains at most one marked step N_{t}^{∗}
(≥, ≠, −)

consists of alternating E and vertical (N_{t}^{∗} or N) steps, with exactly one marked step; or P E^{r}N^{r}, where P consists of alternating E and N steps, starting with E and ending with N

(=, <, −)

P E^{r}N^{r}, where P consists of alternating E and vertical (N_{t}^{∗} or N) steps, starting with E and ending with a vertical step, unless it is empty

(=, ≤, −) empty path; or P E^{r}N^{r}, where P consists of alternating E and either N_{2}^{∗} or N steps, starting with E and ending with either N_{2}^{∗} or N, unless it is empty, and r = 1, 2

(≥, ≤, ≠)

empty path; or P E^{r}N^{r}, where P consists of alternating E and either N_{2}^{∗} or N steps, starting with E and ending with either N_{2}^{∗} or N, unless it is empty, and r > 0

Table 4: Characterization of the image of the image of I_{n} (R_{1}, R_{2}, R_{3}) under φ for each of the patterns (R_{1}, R_{2}, R_{3}) in Table 3. Exponents indicate step repetition, and r and r_{i} are arbitrary nonnegative integers unless otherwise specified.

For the pattern (>, ≠, −), the generating function in Theorem 52 is obtained from the characterization in Table 4 using a path decomposition like the one for the patterns (>, <, −) and (>, ≤, −). For the other patterns in Table 4, I_{(R_{1},R_{2},R_{3})}(z, t) is obtained directly from this characterization of φ (I_{n} (R_{1}, R_{2}, R_{3})). For instance, the description of φ (I_{n} (<, −, <)) implies that any R in this set satisfies one of the following:

• R is the empty path, contributing 1 to I_{(<,−,<)}(z, t);

• R = E^{r_{1}+1}N^{r_{4}}, with r_{1} + 1 = r_{4} > 0, contributing \frac{zt}{1−z} to I_{(<,−,<)}(z, t);

• R = E^{r_{1}}N^{r_{3}}EN^{r_{4}}, with r_{1} + 1 = r_{3} + r_{4} and r_{1}, r_{3}, r_{4} > 0, contributing \frac{z^{2}t^{2}}{(1−z)^{2}} to I_{(<,−,<)}(z, t);

• R = E^{r_{1}}N_{t}^{∗}N^{r_{3}}EN^{r_{4}}, with r_{1} = r_{3} + r_{4}; r_{1}, r_{4} > 0; and r_{3} ≥ 0, contributing \frac{z^{3}t^{2}}{(1−z)^{3}} to I_{(<,−,<)}(z, t).

Adding these four contributions, we obtain Equation (14).

It is natural to ask if an analogue of Corollary 41 holds for any of the patterns in Table 3. In addition to (>, ≤, −), the only other pattern on this list for which the distribution of dist on I_{n} (R_{1}, R_{2}, R_{3}) is symmetric is (=, <, −). In this case, I_{(=,<,−)}(z, t) = 1 + ∑_{n≥1} t(t + 1)^{n−1}z^{n}. Computations for small values of n also suggest that the distribution of dist on I_{n} (R_{1}, R_{2}, R_{3}) is unimodal for each of the patterns in Table 3.

References

[1] Juan S. Auli and Sergi Elizalde, Consecutive patterns in inversion sequences, Discrete Math. Theor. Comput. Sci. 21 (2019), #6.

[2] Eric Babson and Einar Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin., 44 (2000), Art. B44b, 547–548.

[3] Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for vincular patterns, Discrete Math., 312 (2012), 1699–1712.

[4] Andrew Baxter and Mark Shattuck, Some Wilf-equivalences for vincular patterns, J. Comb., 6 (2015), 19–45.

[5] Nicholas Beaton, Mathilde Bouvel, Veronica Guerrini, and Simone Rinaldi, Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, Theoret. Comput. Sci. 777 (2019), 69–92.

[6] Jonathan Bloom and Alexander Burstein, Egge triples and unbalanced Wilf-equivalence, Australas. J. Combin., 64 (2016), 232–251.

[7] Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, and Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence, SIAM J. Discrete Math., 32 (2018), 2795–2819.

[8] Alexander Burstein and Walter Stromquist, Unimodal inversion sequences and patternavoiding classes, AMS Fall Central Sectional Meeting, Loyola University, Chicago, 2015.

Slides available at http://www.alexanderburstein.org/tiki-download_file.php?
fileId=35.

[9] Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Appl. Math., 260 (2019), 86–97.

[10] Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, Patterns in inversion sequences I, Discrete Math. Theor. Comput. Sci., 18 (2) (2016). Available

at https://dmtcs.episciences.org/1421.

[11] Tim Dwyer and Sergi Elizalde, Wilf equivalence relations for consecutive patterns, Adv. in Appl. Math., 99 (2018), 134–157.

[12] Sergi Elizalde, A survey of consecutive patterns in permutations, in Recent Trends in Combinatorics (IMA Vol. Math. Appl.), Springer, 2016, pp. 601–618.

[13] Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. in Appl. Math., 30 (2003), 110–125.

[14] Chetak Hossain, Enumerative and algebraic combinatorics of OEIS \underline{A071356}, Conference presentation at Permutation Patterns 2018, Dartmouth College, Hanover, NH.

[15] Anisse Kasraoui, New Wilf-equivalence results for vincular patterns, European J. Combin., 34 (2013), 322–337.

[16] Dongsu Kim and Zhicong Lin, A sextuple equidistribution arising in Pattern Avoidance, J. Combin. Theory Ser. A, 155 (2018), 267–286.

[17] Dongsu Kim and Zhicong Lin, Refined restricted inversion sequences, Sém. Lothar. Combin., 78 (2017).

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

[19] Toufik Mansour and Mark Shattuck, Pattern avoidance in inversion sequences, Pure Math. Appl., 25 (2015), 157–176.

[20] Megan A. Martinez and Carla D. Savage, Patterns in inversion sequences II: Inversion sequences avoiding triples of relations, J. Integer Sequences, 21 (2018), Art. 18.2.2.

[21] Brian Nakamura, Computational approaches to consecutive pattern avoidance in permutations, Pure Math. Appl., 22 (2011), 253–268.

[22] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, published elec-

tronically at https://oeis.org.

[23] Rodica Simion and Frank W. Schmidt, Restricted Permutations, European J. Combin., 6 (1985), 383–406.

[24] Richard P. Stanley, Catalan Numbers. Cambridge University Press, 2015.

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

2010 Mathematics Subject Classification: Primary 5A05; Secondary 05A15, 05A19. Keywords: Inversion sequence, pattern avoidance, pattern of relations, consecutive pattern, Wilf equivalence.

(Concerned with sequences \underline{A000027}, \underline{A000045}, \underline{A000071}, \underline{A000079} \underline{A000085}, \underline{A000108}, \underline{A000124}, \underline{A000325}, \underline{A000522}, \underline{A003422}, \underline{A033321}, \underline{A040000}, \underline{A049774}, \underline{A052169}, \underline{A071356}, \underline{A200403}, \underline{A279561}, \underline{A328357}, \underline{A328358}, \underline{A328429}, \underline{A328430}, \underline{A328431}, \underline{A328432}, \underline{A328433}, \underline{A328434}, \underline{A328435}, \underline{A328436}, \underline{A328437}, \underline{A328438}, \underline{A328439}, \underline{A328440}, \underline{A328441}, and \underline{A328442}.)

Received June 17 2019; revised version received October 16 2019. Published in Journal of Integer Sequences, October 17 2019.

Return to Journal of Integer Sequences home page.