Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations

Megan Martinez Department of Mathematics Ithaca College Ithaca, NY 14850 USA

                 mmartinez@ithaca.edu

Carla Savage Department of Computer Science North Carolina State University Raleigh, NC 27695 USA

                   savage@ncsu.edu

Abstract

Inversion sequences of length n, I_{n}, are integer sequences (e_{1}, …, e_{n}) with 0 ≤ e_{i} < i for each i. The study of patterns in inversion sequences was initiated recently by Mansour-Shattuck and Corteel-Martinez-Savage-Weselcouch through a systematic study of inversion sequences avoiding words of length 3. We continue this investigation by reframing the notion of a length-3 pattern from a “word of length 3,” w_{1}w_{2}w_{3}, to a “triple of binary relations,” (ρ_{1}, ρ_{2}, ρ_{3}), and consider the set I_{n}(ρ_{1}, ρ_{2}, ρ_{3}) consisting of those e ∈ I_{n} with no i < j < k such that e_{i}ρ_{1}e_{j}, e_{j}ρ_{2}e_{k}, and e_{i}ρ_{3}e_{k}. We show that “avoiding a triple of relations” can characterize inversion sequences with a variety of monotonicity or unimodality conditions, or with multiplicity constraints on the elements. We uncover several interesting enumeration results and relate pattern avoiding inversion sequences to familiar combinatorial families. We highlight open questions about the relationship between pattern avoiding inversion sequences and a variety of classes of pattern avoiding permutations. For several combinatorial sequences, pattern avoiding inversion sequences provide a simpler interpretation than otherwise known.

1 Introduction

Pattern avoiding permutations have been studied extensively for their connections in computer science, biology, and other fields of mathematics. Within combinatorics they have proven their usefulness, providing an interpretation that relates a vast array of combinatorial structures. See the comprehensive survey of Kitaev [17].

The notion of pattern avoidance in inversion sequences was introduced by Corteel, Martinez, Savage, and Weselcouch [13] and Mansour and Shattuck [23]. An inversion sequence is an integer sequence (e_{1}, e_{2}, …, e_{n}) satisfying 0 ≤ e_{i} < i for all i ∈ [n] = {1, 2, …, n}. There is a natural bijection Θ : S_{n} → I_{n} from S_{n}, the set of permutations of [n], to I_{n}, the set of inversion sequences of length n. Under this bijection, e = Θ(π) is obtained from a permutation π = π_{1}π_{2} … π_{n} ∈ S_{n} by setting e_{i} = |{j | j < i and π_{j} > π_{i}}|.

The encoding of permutations as inversion sequences suggests that it could be illuminating to study patterns in inversion sequences in the same way that patterns have been studied in permutations. The paper of Corteel, et al. [13] focused on the enumeration of inversion sequences that avoid words of length three and the paper of Mansour and Shattuck [23] targets permutations of length 3. For example, the inversion sequences e ∈ I_{n} that avoid the pattern 021 are those with no i < j < k such that e_{i} < e_{j} > e_{k} and e_{i} < e_{k}. We denote these by I_{n}(021). Similarly, I_{n}(010) is the set of e ∈ I_{n} with no i < j < k such that e_{i} < e_{j} > e_{k} and e_{i} = e_{k}. The results in each of these works [13, 23] related pattern avoidance in inversion sequences to a number of well-known combinatorial sequences including the Fibonacci numbers, Bell numbers, large Schröder numbers, and Euler up/down numbers. They also gave rise to natural sequences that previously had not appeared in the On-Line Encyclopedia of Integer Sequences (OEIS) [15].

In this paper we reframe the notion of a length-3 pattern from a word of length 3 to a triple of binary relations. For a fixed triple of binary relations (ρ_{1}, ρ_{2}, ρ_{3}), we study the set I_{n}(ρ_{1}, ρ_{2}, ρ_{3}) consisting of those e ∈ I_{n} with no i < j < k such that e_{i}ρ_{1}e_{j}, e_{j}ρ_{2}e_{k}, and e_{i}ρ_{3}e_{k}. For example, I_{n}(<, >, <) = I_{n}(021) and I_{n}(<, >, =) = I_{n}(010). As another example, I_{n}(≥ , ≥, ≥) is the set of inversion sequences in I_{n} with no weakly decreasing subsequence of length 3, i.e., those inversion sequences avoiding all of the words in the set {000, 100, 110, 210}.

Table 1 illustrates that avoiding a single triple of relations can characterize inversion sequences with a variety of natural monotonicity or unimodality conditions, or with multiplicity constraints on the appearance of elements in the inversion sequence. Moreover, as will be seen, inversion sequences avoiding a single triple of relations can provide realizations of certain combinatorial sequences that are simpler than known realizations as pattern avoiding permutations or other combinatorial structures.

For this project, we considered all triples of relations in the set {<, >, ≤, ≥, =, ≠, −}^{3}. The relation “−” on a set S is all of S×S; that is, x “−” y for all x, y ∈ S. There are 343 possible triples of relations (patterns). For each pattern, (ρ_{1}, ρ_{2}, ρ_{3}), we can consider the avoidance set, I_{n}(ρ_{1}, ρ_{2}, ρ_{3}), or the avoidance sequence |I_{1}(ρ_{1}, ρ_{2}, ρ_{3})|, |I_{2}(ρ_{1}, ρ_{2}, ρ_{3})|, |I_{3}(ρ_{1}, ρ_{2}, ρ_{3})|, . . .. We say two patterns are equivalent if they give rise to the same avoidance sets and two patterns are Wilf-equivalent if they yield the same avoidance sequence. For example, patterns (≥, ≥, ≥) and (≥, ≥, −) are equivalent, whereas patterns (≥, ≥, −) and (−, ≤, ≥) are inequivalent, but Wilf equivalent (see Section 2.16).

The 343 patterns partition into 98 equivalence classes of patterns. Additionally, we conjecture that there are 63 Wilf-equivalence classes. In this paper, we enumerate a number of avoidance sets either directly or by relating them to familiar combinatorial structures. These relationships establish Wilf-equivalence between a number of inequivalent patterns. However, in many cases, even where enumeration is elusive, Wilf-equivalence can be proved via a bijection. This paper presents the results we have been able to prove, documents what has not yet been settled, and highlights the most intriguing open questions.

We uncovered several interesting enumeration results beyond those discovered in the initial introduction of patterns in inversion sequences [13, 23]. For example, the inversion sequences e with no i < j < k such that e_{i} = e_{j} ≤ e_{k} are counted by the Fibonacci numbers (as are, e.g., permutations avoiding the pair (321, 3412)). Inversion sequences with no i < j < k such that e_{i} < e_{j} ≤ e_{k} are counted by powers of two (as are, e.g., permutations avoiding (213, 312)). Inversion sequences avoiding (−, ≠, =) are counted by the Bell numbers; inversion sequences avoiding (≥, −, >) are counted by the large Schröder numbers; and inversion sequences avoiding (−, ≥, <) are counted by the Catalan numbers. There are the same number of inversion sequences in I_{n} avoiding (≠, ≠, ≠) as there are Grassmannian permutations in S_{n}. I_{n}(≠, <, ≤) is counted by the number of 321-avoiding separable permutations in S_{n}. I_{n}(≠, <, ≠) has the same number of elements as the set of permutations in S_{n} avoiding both of the patterns 321 and 2143.

Since an earlier draft of this paper was posted [24], several conjectures we made have been proven. Inversion sequences avoiding e_{i} > e_{j} ≥ e_{k} were shown to be counted by the “semi-Baxter sequence” as defined by Bouvel, et al. [7]. It was also shown that the semi-Baxter sequence enumerates plane permutations, which are defined as those permutations avoiding the barred pattern 21¯354 or, equivalently, the vincular pattern 2\underline{14}3. Inversion sequences avoiding e_{i} ≥ e_{j} ≥ e_{k} were shown to have the same counting sequence as set partitions avoiding enhanced 3-crossings. This was shown using the obstinate kernel method by Lin [21] and by a bijection that utilizes 0,1 fillings of Ferrers shapes by Yan [31]. Additionally, the set I_{n}(≥, ≥, >) was shown to have the same counting sequence as the Baxter permutations through use of the obstinate kernel method by Kim and Lin [16]. A number of open questions concerning inversion sequences still remain, and these will be highlighted throughout this paper.

Of the 63 conjectured Wilf-equivalence classes, five classes are counted by sequences that are ultimately constant. In the remaining 58 classes, 30 have counting sequences that appear to match already existing sequences in the OEIS. The remaining 28 resulted in new entries in the OEIS.

In Sections 2.1 through 2.30 we present our results and conjectures for the 30 Wilf classes of pattern-avoiding inversion sequences that (appear to) match sequences in the OEIS. Table 2 gives an overview. Even for patterns with a “no” in this table, we are able to prove some Wilf-equivalence results.

For the patterns whose counting sequence did not originally match a sequence in the OEIS we have some limited results on Wilf-equivalence and counting. Table 3 gives an overview of the patterns in these 28 Wilf classes in addition to their newly created OEIS number. Our results and conjectures for a few of these patterns are presented in Section 3.

In Tables 1, 2, and 3, each row represents an equivalence class of patterns whose identifier is given in the last column. A Wilf class of patterns is identified by the number a_{7}, the number of inversion sequences of length 7 avoiding a pattern in the class. Within a Wilf class, equivalence classes are labeled A,B,C, etc. So, for example, there are three equivalence classes of patterns counted by the Catalan numbers and these classes are labeled 429A, 429B, and 429C.

This paper is intended to provide a comprehensive overview of the enumeration sequences for a large number of classes of pattern avoiding inversion sequences. Many classes can be enumerated through basic counting techniques; in these situations, we have omitted the relevant proofs for the sake of brevity.

In the remainder of this section we give some definitions that will be needed throughout this paper, keeping the number of definitions to a minimum so that subsections can be somewhat self-contained. Finally, for completeness, we list the triples of relations whose avoidance sequences are ultimately constant.

1.1 Encodings of permutations

We compare Θ with a few other common encodings of permutations mentioned later in this paper: Lehmer codes, and invcodes, which are reverse Lehmer codes.

For a sequence t = (t_{1}, …, t_{n}), let t^{R} = (t_{n}, t_{n−1}, …, t_{1}), and, for a set of sequences T, let T^{R} = {t^{R} | t ∈ T }. For a permutation π = (π_{1}, …, π_{n}) ∈ S_{n}, let π^{C} = (n + 1 − π_{1}, …, n + 1 − π_{n}), and, for a set of permutations P, let P^{C} = {π^{C} | π ∈ P }. We use the following encodings.

• Define Θ : S_{n} → I_{n} such that e = Θ(π) if and only if e_{i} = |{j | j < i and π_{j} > π_{i}}|.

• Define L : S_{n} → I_{n}^{R} such that e = L(π) if and only if e_{i} = |{j | j > i and π_{j} < π_{i}}|.

• Define invcode : S_{n} → I_{n} such that e = invcode(π) if and only if e^{R} = L(π).

Note that invcode(π) = e if and only if e = Θ((π^{C})^{R}). Additionally, notice that if Θ(π) = e, then i is a descent of π (that is, π_{i} > π_{i+1}), if and only if i is an ascent of e (that is, e_{i} < e_{i+1}).

We will make use of another encoding, ϕ, in Sections 2.24 and 2.29.

1.2 Operations on inversion sequences

For e = (e_{1}, e_{2}, …, e_{n}) ∈ I_{n} and any integer t, define σ_{t}(e) = (e′_{1}, e′_{2}, …, e′_{n}), where e′_{i} = e_{i} if e_{i} = 0, and e′_{i} = e_{i} + t otherwise. So, σ_{t} adds t to the nonzero elements of a sequence (notice that t could be negative).

Concatenation is used to add an element to the beginning or end of an inversion sequence. For e = (e_{1}, e_{2}, …, e_{n}) ∈ I_{n}, we have 0 · e = (0, e_{1}, e_{2}, …, e_{n}) ∈ I_{n+1}, and, if 0 ≤ i ≤ n, we have e · i = (e_{1}, e_{2}, …, e_{n}, i) ∈ I_{n+1}. More generally, x · y denotes the concatenation of two sequences or two words x, y.

1.3 Statistics on inversion sequences

In several cases, statistics on inversion sequences helped to prove or refine the results in Table 2 and make connections with statistics on other combinatorial families. The statistics used in this paper are defined below for an inversion sequence e ∈ I_{n}.

asc(e) = |{i ∈ [n − 1] | e_{i} < e_{i+1}}|
zeros(e) = |{i ∈ [n] | e_{i} = 0}|
dist(e) = |{e_{1}, e_{2}, …, e_{n}}|
repeats(e) = |{i ∈ [n − 1] | e_{i} ∈ {e_{i+1}, …, e_{n}}}| = n − dist(e)
maxim(e) = |{i ∈ [n] | e_{i} = i − 1}|
maxx(e) = max{e_{1}, e_{2}, …, e_{n}}
last(e) = e_{n}.

These statistics are, respectively, the number of ascents, the number of zeros, the number of distinct elements, the number of repeats, the number of maximal elements, the maximum element, and the last element of e.

1.4 Ultimately constant avoidance sequences

It can be easily checked that the following are the equivalence classes whose avoidance sequences are eventually constant.

pattern avoidance sequence

(−, −, −) 1, 2, 0, 0, 0, 0, … (≤, ≤, −) 1, 2, 1, 0, 0, 0, … (−, −, ≠) 1, 2, 2, 1, 1, 1 … (−, −, <) 1, 2, 2, 2, 2, 2, … (−, ≠, −) 1, 2, 2, 2, 2, 2, … (−, ≠, ≠) 1, 2, 3, 3, 3, 3, …

Inversion sequences e satisfying:  are those with no  and are  a_{7},  Sect.
i < j < k such that: counted by:  equiv class

Monotonicity constraints:

e_{1} = e_{2} = … = e_{n−1}  e_{i} ≠ e_{j}  n  7,D  2.1
∃t: e_{1} = … = e_{t} ≤ e_{t+1} = e_{t+2} = … = e_{n}  e_{i} < e_{j} ≠ e_{k}  1 + n(n − 1)/2  22,A  2.4
∃t: e_{1} = … = e_{t} < e_{t+1} < e_{t+2} < … < e_{n}  e_{i} < e_{j} ≥ e_{k}  2^{n−1}  64,C  2.6
e_{1} ≤ e_{2} ≤ … ≤ e_{n−1}  e_{i} > e_{j}  Binom(2n − 2, n − 1) 924  2.18
e_{1} ≤ e_{2} ≤ … ≤ e_{n−1} ≤ e_{n}  e_{j} > e_{k}  Catalan number C_{n}  429,A  2.14
e_{1} ≤ e_{2} < e_{3} < … < e_{n}  e_{j} ≥ e_{k}  n  7,B  2.1
e_{1} < e_{2} < … < e_{n−1}  e_{i} = e_{j}  n  7,C  2.1
e_{2} ≥ e_{3} ≥ … ≥ e_{n}  e_{j} < e_{k}  n  7,A  2.1

Unimodality constraints:

∃t: e_{1} = … = e_{t} ≤ e_{t+1} ≥ 0 = … = 0  e_{i} < e_{j}, e_{i} < e_{k}  1 + n(n − 1)/2  22,B  2.4
∃t: e_{1} = … = e_{t} ≤ e_{t+1} ≥ e_{t+2} ≥ … ≥ e_{n}  e_{i} ≠ e_{j} < e_{k}  Grassmannian perms 121,A  2.7
∃t: e_{1} = … = e_{t} < e_{t+1} > e_{t+2} > … > e_{n}  e_{i} ≠ e_{j} ≤ e_{k}  F_{n+2} − 1  33,A  2.5
∃t: e_{1} ≤ … ≤ e_{t} > e_{t+1} ≥ e_{t+2} ≥ … ≥ e_{n}  e_{i} > e_{j} < e_{k}  A033321  1265  2.20
∃t: e_{1} ≤ … ≤ e_{t} > e_{t+1} > e_{t+2} > … > e_{n}  e_{i} > e_{j} ≤ e_{k}  A071356  1064  2.19
∃t: e_{1} ≤ … ≤ e_{t} ≥ e_{t+1} = e_{t+2} = … = e_{n}  e_{i} > e_{j} ≠ e_{k}  See Section 3  1079,A  3.1.3
∃t: e_{1} < … < e_{t} ≥ e_{t+1} = e_{t+2} = … = e_{n}  e_{i} ≥ e_{j} ≠ e_{k}  1 + n(n − 1)/2  22,C  2.4
∃t: e_{1} < … < e_{t} ≥ e_{t+1} ≥ e_{t+2} ≥ … ≥ e_{n}  e_{i} = e_{j} < e_{k}  2^{n−1}  64,A  2.6
∃t: e_{1} < … < e_{t} ≥ e_{t+1} > e_{t+2} > … > e_{n}  e_{i} = e_{j} ≤ e_{k}  F_{n+1}  21  2.3
∃(t ≤ s): e_{1} < … < e_{t} = … = e_{s} > … > e_{n} e_{i} ≥ e_{j} ≤ e_{k}, e_{i} ≠ e_{k} F_{n+2} − 1  33,B  2.5

Positive elements monotone:

positive entries are strictly decreasing  e_{i} < e_{j} ≤ e_{k}  2^{n−1}  64,B  2.6
positive entries are weakly decreasing  e_{i} < e_{j} < e_{k}  F_{2n−1}  233  2.12
positive entries are strictly increasing  e_{j} ≥ e_{k}, e_{i} < e_{k}  Catalan number C_{n}  429,B  2.14
positive entries are weakly increasing  e_{j} > e_{k}, e_{i} < e_{k}  large Schröder number 1806,A  2.24

Multiplicity constraints:

entries e_{2}, …, e_{n} are all distinct  e_{i} ≤ e_{j} = e_{k}  2^{n−1}  64,D  2.6
|{e_{1}, e_{2}, …, e_{n}}| ≤ 2  e_{i} ≠ e_{j} ≠ e_{k}, e_{i} ≠ e_{k} Grassmannian perms 121,B  2.7
positive entries are distinct  e_{i} < e_{j} = e_{k}  Bell numbers  877,A  2.17
no three entries equal  e_{i} = e_{j} = e_{k}  Euler up/down nos.  1385  2.22
only adjacent entries can be equal  e_{i} ≠ e_{j} ≠ e_{k}, e_{i} ≠ e_{k} Bell numbers  877,C  2.17
e_{s} = e_{t} ⟹ |s − t| ≤ 1  e_{i} = e_{k}  A229046  304  2.13

Table 1: Characterizations of inversion sequences avoiding triples of relations.

Inversion sequences appear to be
with no i < j < k  counted by proven? notes/OEIS description  a_{7},  Sect.
such that:  OEIS seq:  equiv class
e_{i} ≠ e_{j}, e_{i} ≠ e_{k}  A004275  yes  2(n − 1) for n > 1  12,A  2.2
e_{i} ≥ e_{j}, e_{i} ≠ e_{k}  A004275  yes  2(n − 1) for n > 1  12,B  2.2
e_{i} = e_{j} ≤ e_{k}  A000045  yes  Fibonacci numbers, F_{n+1}  21  2.3
e_{i} < e_{j} ≠ e_{k}  A000124  yes  Lazy caterer sequence  22,A  2.4
e_{i} < e_{j}, e_{i} < e_{k}  A000124  yes  Lazy caterer sequence  22,B  2.4
e_{i} ≥ e_{j} ≠ e_{k}  A000124  yes  Lazy caterer sequence  22,C  2.4
e_{i} ≠ e_{j} ≤ e_{k}  A000071  yes  F_{n+2} − 1  33,A  2.5
e_{i} ≥ e_{j} ≤ e_{k}, e_{i} ≠ e_{k} A000071  yes  F_{n+2} − 1  33,B  2.5
e_{i} = e_{j} < e_{k}  A000079  yes  I_{n}(001), 2^{n−1} (see [13])  64,A  2.6
e_{i} < e_{j} ≤ e_{k}  A000079  yes  2^{n−1}  64,B  2.6
e_{i} < e_{j} ≥ e_{k}  A000079  yes  2^{n−1}  64,C  2.6
e_{i} ≤ e_{j} = e_{k}  A000079  yes  2^{n−1}  64,D  2.6
e_{i} ≠ e_{j} < e_{k}  A000325  yes  Grassmannian permutations  121,A  2.7
e_{i} ≠ e_{j} ≠ e_{k}, e_{i} ≠ e_{k} A000325  yes  Grassmannian permutations  121,B  2.7
e_{j} ≥ e_{k}, e_{i} ≠ e_{k}  A000325  yes  Grassmannian permutations  121,C  2.7
e_{i} ≠ e_{j} < e_{k}, e_{i} ≤ e_{k} A034943  yes  321-avoiding separable perms  151  2.8
e_{i} ≠ e_{j} < e_{k}, e_{i} ≠ e_{k} A088921  yes  S_{n}(321, 2143)  185  2.9
e_{i} ≥ e_{k}  A049125  no  ordered trees, internal nodes, adj. to ≤ 1 leaf  187  2.10
e_{i} ≤ e_{j} ≥ e_{k}, e_{i} ≠ e_{k} A005183  yes  S_{n}(132, 4312), n2^{n−1} + 1  193  2.11
e_{i} < e_{j} < e_{k}  A001519  yes  I_{n}(012), F_{2n−1} (see [13, 23])  233  2.12
e_{i} = e_{k}  A229046  no  recurrence → gf?  304  2.13
e_{j} > e_{k}  A000108  yes  Catalan numbers  429,A  2.14
e_{j} ≥ e_{k}, e_{i} < e_{k}  A000108  yes  Catalan numbers  429,B  2.14
e_{i} ≥ e_{j}, e_{i} ≥ e_{k}  A000108  yes  Catalan numbers [16]  429,C  2.14
e_{i} ≠ e_{j} = e_{k}  A047970  yes  S_{n}(¯3¯1542), nexus numbers  523  2.15
e_{j} ≤ e_{k}, e_{i} ≥ e_{k}  A108307  yes  set partitions avoiding enhanced 3-crossings  772,A  2.16
e_{i} ≥ e_{j} ≥ e_{k}  A108307  yes  set partitions avoiding enhanced 3-crossings [21, 31] 772,B  2.16
e_{i} < e_{j} = e_{k}  A000110  yes  I_{n}(011) (see [13]), Bell numbers B_{n}  877,A  2.17
e_{i} = e_{j} ≥ e_{k}  A000110  no  I_{n}(000, 110), B_{n}  877,B  2.17
e_{j} ≠ e_{k}, e_{i} = e_{k}  A000110  yes  I_{n}(010, 101), B_{n}  877,C  2.17
e_{i} ≥ e_{j}, e_{i} = e_{k}  A000110  no  I_{n}(000, 101), B_{n}  877,D  2.17
e_{i} > e_{j}  A000984  yes  central binomial coefficients  924  2.18
e_{i} > e_{j} ≤ e_{k}  A071356  no  certain underdiagonal lattice paths  1064  2.19
e_{i} > e_{j} < e_{k}  A033321  yes  S_{n}(2143, 3142, 4132) (see [8])  1265  2.20
e_{i} > e_{j}, e_{i} ≤ e_{k}  A106228  no  I_{n}(101, 102), S_{n}(4123, 4132, 4213)  1347  2.21
e_{i} = e_{j} = e_{k}  A000111  yes  I_{n}(000) (see [13]), Euler up/down numbers  1385  2.22
e_{i} > e_{j}, e_{i} < e_{k}  A200753  yes  I_{n}(102), [23]  1694  2.23
e_{j} > e_{k}, e_{i} < e_{k}  A006318  yes  I_{n}(021) [13, 23], large Schröder numbers R_{n−1}  1806,A  2.24
e_{i} > e_{j}, e_{i} ≥ e_{k}  A006318  yes  I_{n}(210, 201, 101, 100), R_{n−1}  1806,B  2.24
e_{i} ≥ e_{j}, e_{i} > e_{k}  A006318  yes  I_{n}(210, 201, 100, 110), R_{n−1}  1806,C  2.24
e_{i} ≥ e_{j} ≠ e_{k}, e_{i} ≥ e_{k} A006318  yes  I_{n}(210, 201, 101, 110), R_{n−1}  1806,D  2.24
e_{i} ≥ e_{j} ≥ e_{k}, e_{i} > e_{k} A001181  yes  Baxter permutations [16]  2074  2.25
e_{i} > e_{j}, e_{i} > e_{k}  A098746  no  I_{n}(210, 201, 100), S_{n}(4231, 42513)  2549,A  2.26
e_{i} > e_{j} ≠ e_{k}, e_{i} ≥ e_{k} A098746  no  I_{n}(210, 201, 101), S_{n}(4231, 42513)  2549,B  2.26
e_{i} ≥ e_{j} ≠ e_{k}, e_{i} > e_{k} A098746  no  I_{n}(210, 201, 110), S_{n}(4231, 42513)  2549,C  2.26
e_{j} < e_{k}, e_{i} ≥ e_{k}  A117106  yes  I_{n}(201, 101), S_{n}(21¯354)  2958,A  2.27
e_{i} > e_{j} ≥ e_{k}  A117106  yes  I_{n}(210, 100), S_{n}(21¯354) [7]  2958,B  2.27
e_{i} ≥ e_{j} > e_{k}  A117106  yes  I_{n}(210, 110), S_{n}(21¯354)  2958,C  2.27
e_{j} ≤ e_{k}, e_{i} > e_{k}  A117106  yes  I_{n}(201, 100), S_{n}(21¯354)  2958,D  2.27
e_{j} < e_{k}, e_{i} = e_{k}  A113227  yes  I_{n}(101), S_{n}(1-23-4), (see [13])  3207,A  2.28
e_{i} = e_{j} > e_{k}  A113227  yes  I_{n}(110), S_{n}(1-23-4), (see [13])  3207,B  2.28
e_{i} > e_{j} ≠ e_{k}, e_{i} > e_{k} A212198  yes  I_{n}(201, 210), MMP (0, 2, 0, 2)-avoiding perms  3720  2.28

Table 2: Patterns whose avoidance sequences appear to match sequences in the OEIS. Those marked as “yes” are cited, if known, and otherwise are proven in this paper.

7 Inversion sequences

with no i < j < k comments initial terms a_{1}, … a_{9} a_{7},
such that:  equiv class
e_{j} ≥ e_{k}, e_{i} ≥ e_{k}  I_{n}(000, 010, 011, 021) (A279544)  1, 2, 4, 10, 26, 73, 214, 651, 2040  214
e_{i} ≤ e_{j}, e_{i} ≥ e_{k}  I_{n}(000, 010, 110, 120) (A279551)  1, 2, 4, 10, 27, 79, 247, 816, 2822  247
e_{j} ≥ e_{k}, e_{i} = e_{k}  I_{n}(000, 010) (A279552)  1, 2, 4, 10, 29, 95, 345, 1376, 5966  345
e_{j} ≠ e_{k}, e_{i} ≥ e_{k}  Wilf-eq. to 663B (Sec. 3.2, A279553) 1, 2, 5, 15, 50, 178, 663, 2552, 10071  663,A
e_{i} ≠ e_{j}, e_{i} ≥ e_{k}  Wilf-eq. to 663A (Sec. 3.2, A279553) 1, 2, 5, 15, 50, 178, 663, 2552, 10071  663,B
e_{i} ≠ e_{j} ≠ e_{k}, e_{i} ≥ e_{k} I_{n}(010, 101, 120, 201) (A279554)  1, 2, 5, 15, 51, 188, 733, 2979, 12495  733
e_{j} > e_{k}, e_{i} ≥ e_{k}  Wilf-eq. to 746B (Sec. 3.2, A279555) 1, 2, 5, 15, 51, 189, 746, 3091, 13311  746,A
e_{i} ≠ e_{j} ≥ e_{k}, e_{i} ≥ e_{k} Wilf-eq. to 746A (Sec. 3.2, A279555) 1, 2, 5, 15, 51, 189, 746, 3091, 13311  746,B
e_{i} ≤ e_{j} ≠ e_{k}, e_{i} ≥ e_{k} I_{n}(010, 110, 120) (A279556) 1, 2, 5, 15, 51, 190, 759, 3206, 14180 759
e_{i} ≤ e_{j} > e_{k}, e_{i} ≠ e_{k} counted - See Section 3.1 (A279557) 1, 2, 6, 20, 68, 233, 805, 2807, 9879  805
e_{i} ≠ e_{j} > e_{k}, e_{i} ≥ e_{k} I_{n}(010, 120, 210) (A279558)  1, 2, 5, 15, 52, 200, 830, 3654, 16869  830
e_{i} < e_{j}, e_{i} ≥ e_{k}  I_{n}(010, 120) (A279559)  1, 2, 5, 15, 52, 201, 845, 3801, 18089  845
e_{j} > e_{k}, e_{i} = e_{k}  I_{n}(010) (A263779)  1, 2, 5, 15, 53, 215, 979, 4922, 26992  979
e_{i} > e_{j}, e_{i} ≠ e_{k}  counted - See Section 3.1 (A279560) 1, 2, 6, 21, 76, 277, 1016, 3756, 13998  1016
e_{i} > e_{j} ≠ e_{k}  counted - See Section 3.1 (A279561) 1, 2, 6, 21, 77, 287, 1079, 4082, 15522  1079,A
e_{i} < e_{j} > e_{k}, e_{i} ≠ e_{k} I_{n}(021, 120) (A279561)  1, 2, 6, 21, 77, 287, 1079, 4082, 15522  1079,B
e_{i} > e_{j} ≤ e_{k}, e_{i} ≠ e_{k} I_{n}(100, 102, 201) (A279562)  1, 2, 6, 21, 78, 299, 1176, 4729, 19378  1176
e_{i} > e_{j} ≠ e_{k}, e_{i} ≠ e_{k} I_{n}(102, 201, 210) (A279563)  1, 2, 6, 22, 85, 328, 1253, 4754, 17994  1253
e_{i} ≥ e_{j} = e_{k}  I_{n}(000, 100) (A279564)  1, 2, 5, 16, 60, 260, 1267, 6850, 40572  1267
e_{i} > e_{k}  I_{n}(100, 110, 120, 210, 201) (A279565) 1, 2, 6, 21, 81, 332, 1420, 6266, 28318  1420
e_{i} > e_{j} < e_{k}, e_{i} ≠ e_{k} I_{n}(102, 201) (A279566)  1, 2, 6, 22, 87, 354, 1465, 6154, 26223  1465
e_{j} ≥ e_{k}, e_{i} > e_{k}  I_{n}(100, 110, 120, 210) (A279567)  1, 2, 6, 21, 82, 343, 1509, 6893, 32419  1509
e_{j} ≠ e_{k}, e_{i} > e_{k}  Wilf-eq. to 1833B (Sec. 3.2, A279568) 1, 2, 6, 22, 90, 396, 1833, 8801, 43441  1833,A
e_{i} ≠ e_{j} , e_{i} > e_{k}  Wilf-eq. to 1833A (Sec. 3.2, A279568) 1, 2, 6, 22, 90, 396, 1833, 8801, 43441  1833,B
e_{j} > e_{k}, e_{i} > e_{k}  Wilf-eq. to 1953B (Sec. 3.2, A279569) 1, 2, 6, 22, 91, 409, 1953, 9763, 50583  1953,A
e_{i} ≠ e_{j} ≥ e_{k}, e_{i} > e_{k} Wilf-eq. to 1953A (Sec. 3.2, A279569) 1, 2, 6, 22, 91, 409, 1953, 9763, 50583  1953,B
e_{i} ≤ e_{j} > e_{k}, e_{i} > e_{k} I_{n}(110, 120) (A279570)  1, 2, 6, 22, 92, 423, 2091, 10950, 60120 2091
e_{i} > e_{j} ≤ e_{k}, e_{i} ≥ e_{k} I_{n}(100, 101, 201) (A279571)  1, 2, 6, 22, 92, 424, 2106, 11102, 61436 2106
e_{i} ≠ e_{j} ≠ e_{k}, e_{i} > e_{k} I_{n}(120, 210, 201) (A279572)  1, 2, 6, 23, 101, 484, 2468, 13166, 72630 2468
e_{i} ≠ e_{j} > e_{k}, e_{i} > e_{k} I_{n}(210, 120) (A279573)  1, 2, 6, 23, 102, 499, 2625, 14601, 84847 2625
e_{i} < e_{j}, e_{i} > e_{k}  I_{n}(120) (A263778)  1, 2, 6, 23, 103, 515, 2803, 16334, 100700 2803
e_{i} > e_{j} = e_{k}  I_{n}(100) (A263780)  1, 2, 6, 23, 106, 565, 3399, 22678, 165646 3399
e_{j} < e_{k}, e_{i} > e_{k}  I_{n}(201) (A263777)  1, 2, 6, 24, 118, 674, 4306, 29990, 223668 4306,A
e_{i} > e_{j} > e_{k}  I_{n}(210) Wilf-eq to 4306A [13]  1, 2, 6, 24, 118, 674, 4306, 29990, 223668 4306,B

Table 3: The patterns whose avoidance sequences did not match sequences in the OEIS. (OEIS numbers in parentheses were newly assigned.)

2 Patterns whose sequences appear in the OEIS

2.1 Classes 7(A,B,C,D): n

There are four equivalence classes of patterns whose avoidance sequences are counted by the positive integers. We characterize each, from which it is straightforward to prove that

|I_{n}(−, <, −)| = |I_{n}(−, ≥, −)| = |I_{n}(=, −, −)| = |I_{n}(≠, −, −)| = n,

although these four patterns are not equivalent. The conditions on the entries of inversion sequences in each class are as follows.

• (Class 7A: e_{j} < e_{k}) I_{n}(−, <, −) is the set of e ∈ I_{n} satisfying e_{2} ≥ e_{3} ≥ … ≥ e_{n}.

• (Class 7B: e_{j} ≥ e_{k}) I_{n}(−, ≥, −) is the set of e ∈ I_{n} satisfying e_{1} ≤ e_{2} < e_{3} < … < e_{n}.

• (Class 7C: e_{i} = e_{j}) I_{n}(=, −, −) is the set of e ∈ I_{n} satisfying e_{1} < e_{2} < … < e_{n−1}.

• (Class 7D: e_{i} ≠ e_{j}) I_{n}(≠, −, −) is the set of e ∈ I_{n} satisfying e_{1} = e_{2} = … = e_{n−1}.

Note: Simion and Schmidt [27] showed that |S_{n}(123, 132, 231)| = n. In fact, we get the following relationship between inversion sequences and permutations.

Theorem 1. For every n, Θ(S_{n}(123, 132, 231)) = I_{n}(=, −, −).

2.2 Classes 12(A,B): 2(n − 1) for n > 1

In the following theorem, we show that classes 12A (e_{i} ≠ e_{j} and e_{i} ≠ e_{k}) and 12B (e_{i} ≥ e_{j} and e_{i} ≠ e_{k}) are Wilf-equivalent, but not equivalent.

Theorem 2. |I_{n}(≠, −, ≠)| and |I_{n}(≥, −, ≠)| are both counted by 1 if n = 1 and by 2(n − 1) for n > 1. However, I_{n}(≠, −, ≠) ≠ I_{n}(≥, −, ≠) for n > 2.

Proof. For n = 1 this is clear. For n > 1 this follows by noting that any e ∈ I_{n} with no i < j < k such that e_{i} ≠ e_{j} and e_{i} ≠ e_{k} can be (0, 0, …, 0) or can be of the form (0, 0, …, t, 0) or (0, 0, …, 0, s) where t ∈ [n − 2] and s ∈ [n − 1]. On the other hand, any e ∈ I_{n} with no i < j < k such that e_{i} ≥ e_{j} and e_{i} ≠ e_{k} must have the form (0, 1, 2, …, n − 2, t) for t = 0, …, n − 1 or the form (0, 1, 2, …, t − 1, t, t, …, t) for t = 0, …, n − 3.

2.3 Class 21: F_{n+1}

Let F_{n} be the n-th Fibonacci number, where F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1}+F_{n−2} for n ≥ 2. The Fibonacci numbers count pattern-avoiding permutations such as S_{n}(123, 132, 213) [27]. Class 21 (e_{i} = e_{j} ≤ e_{k}) is counted by the (n + 1)-th Fibonacci number, as shown below.

Observation 3. The inversion sequences e ∈ I_{n} with no i < j < k such that e_{i} = e_{j} ≤ e_{k} are those satisfying, for some t ∈ [n],

e_{1} < e_{2} < … < e_{t} ≥ e_{t+1} > … > e_{n}.  (1)

Theorem 4. |I_{n}(=, ≤, −)| = F_{n+1}

Proof. This is clear for n = 1, 2. For n ≥ 3, any e ∈ I_{n}(=, ≤, −) must have the form (0, e_{1} + 1, …, e_{n−1} + 1) for (e_{1}, …, e_{n−1}) ∈ I_{n−1}(=, ≤, −) or (0, e_{1} + 1, …, e_{n−2} + 1, 0) for (e_{1}, …, e_{n−2}) ∈ I_{n−2}(=, ≤, −). Conversely, strings of either of these forms are in I_{n}(=, ≤ , −).

Among the 343 patterns checked, it can be shown that the six patterns whose avoidance sequence is counted by F_{n+1} are equivalent. Observation 5. All of the following patterns are equivalent to (=, ≤, −): (=, −, ≤), (=, ≤, ≤), (≥, −, ≤), (≥, ≤, −), (≥, ≤, ≥).

2.4 Classes 22(A,B,C): Lazy caterer sequence, \binom{n}{2} + 1

We show that there are three inequivalent patterns that are all counted by the sequence \binom{n}{2} + 1, which also counts S_{n}(132, 321) [27].

2.4.1 Class 22A: Avoiding e_{i} < e_{j} ≠ e_{k}

It is not hard to see that inversion sequences avoiding e_{i} < e_{j} ≠ e_{k} are characterized by the following. Observation 6. The inversion sequences e ∈ I_{n} with no i < j < k such that e_{i} < e_{j} ≠ e_{k} are those satisfying, for some t where 1 ≤ t ≤ n,

0 = e_{1} = e_{2} = … = e_{t−1} ≤ e_{t} = e_{t+1} = … = e_{n}.  (2)

That is, either e = (0, 0, …, 0) or, for some t : 2 ≤ t ≤ n and j : 1 ≤ j ≤ t − 1, e consists of a string of t − 1 zeros followed by a string of n − t + 1 copies of j. This gives the following.

Theorem 7. |I_{n}(<, ≠, −)| = \binom{n}{2} + 1.

The sequence whose nth entry is \binom{n}{2} + 1 is sequence A000124 in the OEIS, where it is called the Lazy Caterer sequence [15] because its nth entry is the maximum number of pieces that can be formed by making n−1 straight cuts in a pizza. This is also the avoidance sequence for certain pairs of permutation patterns, as was shown by Simion and Schmidt [27].

Theorem 8 (Simion-Schmidt [27]). |S_{n}(α, β)| = \binom{n}{2}+1 for any of the following pairs (α, β) of patterns:

(132, 321), (123, 231), (123, 312), (213, 321).

We can relate these permutations to the inversion sequences in I_{n}(<, ≠, −). Recall the bijection Θ(π) : S_{n} → I_{n} for π = π_{1} … π_{n} ∈ S_{n} defined by Θ(π) = (e_{1}, e_{2}, …, e_{n}), where e_{i} = |{j | j < i and e_{j} > e_{i}}|.

Theorem 9. I_{n}(<, ≠, −) = Θ(S_{n}(213, 321)).

Proof. Note that e ∈ I_{n} satisfies (2) if and only if π = Θ^{−1}(e) satisfies

π_{1} < π_{2} < … < π_{t} > π_{t+1} < π_{t+2} < … < π_{n},

where π_{t}, π_{t+1}, …, π_{n} are consecutive integers. Such permutations are precisely the ones that avoid both 213 and 321.

The patterns (<, −, <) and (≥, ≠, −) are Wilf-equivalent to the pattern (<, ≠, −) on inversion sequences, although the three patterns are pairwise inequivalent. This is clear from the following characterizations.

2.4.2 Class 22B: Avoiding e_{i} < e_{j} and e_{i} < e_{k}

Observation 10. The inversion sequences e ∈ I_{n} with no i < j < k such that e_{i} < e_{j} and e_{i} < e_{k} are those satisfying, for some t where 1 ≤ t ≤ n,

0 = e_{1} = e_{2} = … = e_{t−1} ≤ e_{t} ≥ e_{t+1} = … = e_{n} = 0.  (3)

2.4.3 Class 22C: Avoiding e_{i} ≥ e_{j} ≠ e_{k}

Observation 11. The inversion sequences e ∈ I_{n} with no i < j < k such that e_{i} ≥ e_{j} ≠ e_{k} are those satisfying, for some t where 1 ≤ t ≤ n,

e_{1} < e_{2} < … < e_{t−1} ≥ e_{t} = e_{t+1} = … = e_{n}.  (4)

2.5 Classes 33(A,B): F_{n+2} − 1

We show that 33A: (≠, ≤, −) and 33B: (≥, ≤, ≠) are inequivalent Wilf-equivalent patterns whose avoidance sequences are counted by F_{n+2} − 1.

2.5.1 Class 33A: Avoiding e_{i} ≠ e_{j} ≤ e_{k}

Theorem 12. |I_{n}(≠, ≤, −)| = F_{n+2} − 1.

Proof. Observe that the inversion sequences e ∈ I_{n} with no i < j < k such that e_{i} ≠ e_{j} ≤ e_{k} are those satisfying, for some t where 1 ≤ t ≤ n + 1,

0 = e_{1} = e_{2} = … = e_{t−1} < e_{t} > e_{t+1} > … > e_{n}.  (5)

We can partition the inversion sequences in I_{n}(≠, ≤, −) into three disjoint sets: {(0, 0, …, 0)}, A = {e ∈ I_{n}(≠, ≤, −) | e_{n} ≠ 0}, and B = {e ∈ I_{n}(≠, ≤, −) | e ≠ 0, e_{n} = 0}. Any inversion sequence in A can be constructed by taking any e′ = (e_{1}, e_{2}, …, e_{n−1}) ∈ I_{n−1}(≠, ≤, −) and letting t be the index of the first nonzero entry (if there is no nonzero entry, set e_{t} = e_{n−1}). Then we can use the characterization given by (5) to verify that (0, e_{1}, e_{2}, …, e_{t−1}, e_{t} + 1, …, e_{n−1} + 1) is an element of A.

Any element of B can be constructed by taking some e′′ = (e_{1}, e_{2}, …, e_{n−2}) ∈ I_{n−2}(≠, ≤ , −) and letting t be the index of the first nonzero entry (again, if no such entry exists, set e_{t} = e_{n−2}). Then (0, e_{1}, …, e_{t−1}, e_{t} + 1, …, e_{n−2} + 1, 0) is an element of B.

Setting a_{n} = |I_{n}(≠, ≤, −)|, this gives a_{n} = a_{n−1} + a_{n−2} + 1, with initial conditions a_{1} = 1, a_{2} = 2. So a_{n} = F_{n+2} − 1.

2.5.2 Class 33B: Avoiding e_{i} ≥ e_{j} ≤ e_{k} and e_{i} ≠ e_{k}

Theorem 13. |I_{n}(≥, ≤, ≠)| = F_{n+2} − 1.

Proof. The inversion sequences e ∈ I_{n} with no i < j < k such that e_{i} ≥ e_{j} ≤ e_{k} and e_{i} ≠ e_{k} are those satisfying, for some t, s where 1 ≤ t ≤ s ≤ n,

e_{1} < e_{2} < … < e_{t−1} < e_{t} = e_{t+1} = … = e_{s} > e_{s+1} > … > e_{n}.  (6)

The following is a bijection mapping I_{n}(≥, ≤, ≠) to I_{n}(≠, ≤, −). For e ∈ I_{n}(≥, ≤, ≠), let s be the first index, if any, such that e_{s} > e_{s+1}; if e is weakly increasing, set s = n. To obtain an element of I_{n}(≠, ≤, −), set e_{i} = 0 for i = 1, …, s − 1.

2.6 Classes 64(A,B,C,D): 2^{n−1}

2.6.1 Class 64A: Avoiding e_{i} = e_{j} < e_{k}

Corteel, et al. [13] characterized I_{n}(=, <, −) = I_{n}(001) as the set of e ∈ I_{n} satisfying, for some t ∈ [n],

e_{1} < e_{2} < … < e_{t} ≥ e_{t+1} ≥ e_{t+2} ≥ … ≥ e_{n}.

They showed that |I_{n}(001)| = 2^{n−1} by showing that the bijection Θ : S_{n} → I_{n} restricts to a bijection from S_{n}(132, 231) to I_{n}(001). Simion and Schmidt [27] showed that permutations avoiding both 132 and 231 are enumerated by 2^{n−1}.

We show that three other patterns are Wilf-equivalent, though inequivalent, to class 64A.

2.6.2 Class 64B: Avoiding e_{i} < e_{j} ≤ e_{k}

Theorem 14. The number of e ∈ I_{n} with no i < j < k such that e_{i} < e_{j} ≤ e_{k} is 2^{n−1}.

Proof. First observe that the inversion sequences e with no i < j < k such that e_{i} < e_{j} ≤ e_{k} are those whose positive entries form a strictly decreasing sequence.

Let B_{n} = I_{n}(<, ≤, −). Notice that |B_{1}| = |{(0)}| = 1; we will show that for n > 1, |B_{n}| = 2|B_{n−1}|. Recall that σ_{1}(e) adds 1 to each positive element in e.

An e ∈ B_{n} has no “1” if and only if it has the form 0 · σ_{1}(e′) for some e′ ∈ B_{n−1}, so there are |B_{n−1}| such e. An e ∈ B_{n} has a “1” if and only if it has the form e′ · 0 for some e′ ∈ B_{n−1} containing a “1” or the form e′ · 1 for some e′ ∈ B_{n−1} not containing a “1”, so there are also |B_{n−1}| elements of B_{n} containing a “1”.

2.6.3 Class 64C: Avoiding e_{i} < e_{j} ≥ e_{k}

Theorem 15. The number of e ∈ I_{n} with no i < j < k such that e_{i} < e_{j} ≥ e_{k} is 2^{n−1}.

Proof. The inversion sequences avoiding the pattern e_{i} < e_{j} ≥ e_{k}, where i < j < k, are those e ∈ I_{n} satisfying, for some t ∈ [n],

0 = e_{1} = e_{2} = ⋯ = e_{t} < e_{t+1} < e_{t+2} < ⋯ < e_{n}.

Map e ∈ I_{n}(<, ≥, −) to the set consisting of its nonzero values. Clearly this is a bijection from I_{n}(<, ≥, −) to 2^{[n−1]}.

In fact, we can show that I_{n}(<, ≥, −) is the image under Θ of S_{n}(213, 312).

Theorem 16. Θ(S_{n}(213, 312)) = I_{n}(<, ≥, −).

Proof. It is straightforward to prove that S_{n}(213, 312) consists of the unimodal permutations where

π_{1} < π_{2} < ⋯ < π_{t} = n > π_{t+1} > ⋯ > π_{n}.

The inversion sequences avoiding the pattern e_{i} < e_{j} ≥ e_{k}, where i < j < k, are those e ∈ I_{n} satisfying, for some t ∈ [n],

0 = e_{1} = e_{2} = ⋯ = e_{t} < e_{t+1} < e_{t+2} < ⋯ < e_{n}.

It immediately follows that Θ(S_{n}(213, 312)) = I_{n}(<, ≥, −).

2.6.4 Class 64D: Avoiding e_{i} ≤ e_{j} = e_{k}

Theorem 17. The number of e ∈ I_{n} with no i < j < k such that e_{i} ≤ e_{j} = e_{k} is 2^{n−1}.

Proof. The inversion sequences avoiding the pattern e_{i} ≤ e_{j} = e_{k}, where i < j < k, are those e ∈ I_{n} in which all of the entries e_{2}, e_{3}, …, e_{n} are distinct.

Let D_{n} = I_{n}(≤, =, −). Then |D_{1}| = |{(0)}| = 1. We show that for n > 1, |D_{n}| = 2|D_{n−1}|. An e ∈ D_{n} ends in n − 1 if and only if e = e′ · (n − 1) for some e′ ∈ D_{n−1}, so there are |D_{n−1}| such e. An e ∈ D_{n} ends in d ≠ n − 1 if and only if e = e′ · d where e′ ∈ D_{n−1} and d is the unique element in {0, 1, …, n − 2} \ {e_{2}, …, e_{n−1}}, so there are again |D_{n−1}| such e.

2.7 Classes 121(A,B,C): Grassmannian permutations, 2^{n} − n

Permutations with at most one descent were called Grassmannian by Lascoux and Schützenberger [20], who also characterized them in terms of their Lehmer codes. Grassmannian permutations of length n are counted by 2^{n} − n and relate to three equivalence classes of patterns for inversion sequences.

2.7.1 Class 121A: Avoiding e_{i} ≠ e_{j} < e_{k}

Theorem 18. |I_{n}(≠, <, −)| = 2^{n} − n.

Proof. First observe that those e ∈ I_{n} with no i < j < k such that e_{i} ≠ e_{j} < e_{k} are exactly those with at most one ascent.

Using the mapping Θ : S_{n} → I_{n}, recall that π has a descent in a position i if and only if Θ(π) has an ascent in position i. Thus Θ restricts to a bijection from Grassmannian permutations of [n] to I_{n}(≠, <, −).

The inversion sequences in I_{n}(≠, <, −) correspond to the Grassmannian Lehmer codes used by Lascoux and Schützenberger [20] via the natural bijection (reversal) between inversion sequences and Lehmer codes.

2.7.2 Class 121B: Avoiding e_{i} ≠ e_{j} ≠ e_{k} and e_{i} ≠ e_{k}

Theorem 19. |I_{n}(≠, ≠, ≠)| = 2^{n} − n.

Proof. Note that inversion sequences with no i < j < k such that e_{i} ≠ e_{j} ≠ e_{k} and e_{i} ≠ e_{k} are those with at most 2 distinct entries; precisely, |{e_{1}, …, e_{n}}| ≤ 2.

The theorem is clear for n = 1. Now consider some e ∈ I_{n}(≠, ≠, ≠) when n > 1. Note that (e_{1}, …, e_{n−1}) ∈ I_{n−1}(≠, ≠, ≠). It follows that either (1) |{e_{1}, …, e_{n−1}}| = 2, and e_{n} is one of the two elements occurring in (e_{1}, …, e_{n−1}); or (2) |{e_{1}, …, e_{n−1}}| = 1, and e_{n} ∈ {0, 1, …, n − 1}. Furthermore, the only inversion sequence in I_{n−1}(≠, ≠, ≠) where |{e_{1}, …, e_{n−1}}| = 1 is the zero inversion sequence. This gives the recurrence |I_{n}(≠, ≠, ≠)| = 2(|I_{n−1}(≠, ≠, ≠)| − 1) + n which has the claimed solution.

2.7.3 Class 121C: Avoiding e_{j} ≥ e_{k} and e_{i} ≠ e_{k}

Theorem 20. |I_{n}(−, ≥, ≠)| = 2^{n} − n.

Proof. Inversion sequences with no i < j < k such that e_{j} ≥ e_{k} and e_{i} ≠ e_{k} are those satisfying

e_{1} = … = e_{i−1} < e_{i} < … < e_{n}

or, if e_{i+1} = 0,

e_{1} = … = e_{i−1} < e_{i} < e_{i+2} < … < e_{n},

for some i with 2 ≤ i ≤ n + 1.

To count these, for each t = 1, …, n − 1, and for any t-element subset x_{1} < x_{2} < … < x_{t} of [n − 1], associate the length n inversion sequence (0, 0, …, 0, x_{1}, x_{2}, …, x_{t}) and, unless {x_{1}, …, x_{t}} = {n − t, n − t + 1, …, n − 1}, also associate the length n inversion sequence (0, 0, …, 0, x_{1}, 0, x_{2}, …, x_{t}), giving 2^{n−1} + (2^{n−1} − n) = 2^{n} − n.

2.8 Class 151: 321-avoiding separable permutations

We show that the avoidance sequence for this pattern satisfies the recurrence a_{n} = 3a_{n−1} − 2a_{n−2} +a_{n−3} with initial conditions a_{1} = 1, a_{2} = 2, and a_{3} = 5. This coincides with sequence A034943 in the OEIS, where, among other things, it is said to count 321-avoiding separable permutations (OEIS entry by Vince Vatter) [15]. A separable permutation is one that avoids 2413 and 3142. Moreover, we show that (≠, <, ≤)-avoiding inversion sequences have a simple characterization.

Theorem 21. Let A_{n} = I_{n}(≠, <, ≤) and a_{n} = |A_{n}|. Then a_{n} = 3a_{n−1} − 2a_{n−2} + a_{n−3} with initial conditions a_{1} = 1, a_{2} = 2, and a_{3} = 5.

Proof. First, it can be shown that the set of e ∈ I_{n} such that there is no i < j < k for which e_{i} ≠ e_{j} < e_{k} and e_{i} ≤ e_{k} is the set of e ∈ I_{n} where the nonzero elements are weakly decreasing and equal nonzero elements are consecutive. That is, (1) if e_{i} < e_{j}, then e_{i} = 0 and (2) if 0 < e_{i} = e_{j} for some i < j, then e_{i} = e_{i+1} = … = e_{j}.

Define X_{n}, Y_{n}, Z_{n} by

X_{n} = {e ∈ A_{n} | e_{i} ≠ 1, for all 1 ≤ i ≤ n},
Y_{n} = {e ∈ A_{n} | e_{n} = 1},
Z_{n} = {e ∈ A_{n} | e_{n} = 0 and e_{i} = 1 for some i < n}.

Then A_{n} is the disjoint union A_{n} = X_{n} ∪ Y_{n} ∪ Z_{n}. Recall that the operator σ_{1} adds 1 to the positive elements of an inversion sequence. To get a recurrence, note that |X_{n}| = |A_{n−1}| = a_{n−1} since e ∈ A_{n−1} if and only if 0 · σ_{1}(e) ∈ X_{n}. Also, (e_{1}, …, e_{n−1}, 0) ∈ Z_{n} if and only if (e_{1}, …, e_{n−1}) ∈ Y_{n−1}∪Z_{n−1} = A_{n−1}−X_{n−1}; so |Z_{n}| = |A_{n−1}|−|X_{n−1}| = a_{n−1}−a_{n−2}. Finally, (e_{1}, …, e_{n−1}, 1) ∈ Y_{n} if and only if (e_{1}, …, e_{n−1}) ∈ A_{n−1} − Z_{n−1}, so |Y_{n}| = a_{n−1} − |Z_{n−1}| = a_{n−1} − (a_{n−2} − a_{n−3}). Putting this together,

a_{n} = |A_{n}| = |X_{n}| + |Y_{n}| + |Z_{n}| = 3a_{n−1} − 2a_{n−1} + a_{n−3}

and the result follows by checking the initial conditions.

2.9 Class 185: 321-avoiding vexillary permutations, 2^{n+1} − \binom{n+1}{3} − 2n − 1

Vexillary permutations, studied by Lascoux and Schützenberger [20], are 2143-avoiding permutations. The 321-avoiding vexillary permutations arose in work of Billey, Jockush and Stanley [4] on the combinatorics of Schubert polynomials. It was shown that |S_{n}(321, 2143)| = 2^{n+1} − \binom{n+1}{3} − 2n − 1 which is entry A088921 in the OEIS. In this entry, it is noted that the 321-avoiding vexillary permutations are exactly the Grassmannian permutations (see Section 2.7) and their inverses.

We show that the (≠, <, ≠)-avoiding inversion sequences are counted by the same function as the 321-avoiding vexillary permutations.

Lemma 22. I_{n}(≠, <, ≠) = I_{n}(≠, ≠, ≠) ∪ I_{n}(≠, <, −).

Proof. If e ∈ I_{n}(≠, <, ≠), then either e ∈ I_{n}(≠, <, −) or for any i < j < k such that e_{i} ≠ e_{j} < e_{k}, e_{i} = e_{k} and therefore e ∈ I_{n}(≠, ≠, ≠).

Conversely, if, for some i < j < k, e_{i} ≠ e_{j} < e_{k} and e_{i} ≠ e_{k}, then e contains both (≠, <, −) and (≠, ≠, ≠).

Theorem 23. |I_{n}(≠, <, ≠)| = 2^{n+1} − \binom{n+1}{3} − 2n − 1.

Proof. By Theorem 19, |I_{n}(≠, ≠, ≠)| = 2^{n} − n and by Theorem 18, |I_{n}(≠, <, −)| = 2^{n} − n. From the characterizations of these sets in the proof of Theorems 18 and 19, I_{n}(≠, ≠, ≠ ) ∩ I_{n}(≠, <, −) is the set of inversion sequences with at most one ascent and at most two distinct elements, that is, the set of e ∈ I_{n} satisfying, for some 1 ≤ t < a < b ≤ n + 1,

0 = e_{1} = … = e_{a−1}; t = e_{a} = … = e_{b−1}; 0 = e_{b} = … = e_{n},

which is counted by \binom{n+1}{3}, together with (0, 0, …, 0). Thus

|I_{n}(≠, ≠, ≠) ∩ I_{n}(≠, <, −)| = \binom{n + 1}{3} + 1

and the result follows.

2.10 Class 187: Conjectured to be counted by A049125

It appears that the number of e ∈ I_{n} avoiding this pattern is given by A049125 in the OEIS, where it is described by David Callan to be the number of ordered trees with n edges in which every non-leaf non-root vertex has at most one leaf child. However, we have not yet proven it. We can prove a characterization of the avoidance set and, from that, derive a 4-parameter recurrence that allows us to check against A049125 for several terms.

Observation 24. The sequences e ∈ I_{n} having no i < j < k with e_{i} ≥ e_{k} are those for which e_{i} > max{e_{1}, …, e_{i−2}} for i = 3, …, n. For e ∈ I_{n}, this is equivalent to the conditions e_{3} > e_{1} and, for 4 ≤ i ≤ n, e_{i} > max{e_{i−2}, e_{i−3}}.

2.11 Class 193: S_{n}(132, 4312), (n − 1)2^{n−2} + 1

Sequence (n − 1)2^{n−2} + 1 appears as A005183 in the OEIS, where Pudwell indicates that it counts S_{n}(132, 4312) [15]. We show it also counts I_{n}(≤, ≥, ≠).

Theorem 25. |I_{n}(≤, ≥, ≠)| = (n − 1)2^{n−2}

Proof. Observe that if e ∈ I_{n} has no i < j < k such that e_{i} ≤ e_{j} ≥ e_{k} and e_{i} ≠ e_{k} then e must have the form

e = (0, …, 0, e_{a}, 0, …, 0, e_{n−b+1}, e_{n−b+2}, …, e_{n}}

where 1 ≤ a < n + 1 and b < n − a + 2 and 1 ≤ e_{a} < e_{n−b+1} < e_{n−b+2} < … < e_{n} < n.

If e_{a} > 1 then e = 0 · σ_{1}(e′) for some e′ ∈ I_{n−1}(≤, ≥, ≠). Otherwise, e_{a} = 1 and e can be obtained by first choosing a b-element subset of {2, …, n − 1} to place (sorted) in locations n − b + 1, …, n, and then choosing one of the locations 2, …, n − b to be the location a such that e_{a} = 1. Thus the number of sequences containing a 1 is:

∑_{b=0}^{n−2} \binom{n − 2}{b}(n − 1 − b) = n2^{n−3}.

This gives the recurrence

|I_{n}(≤, ≥, ≠)| = |I_{n−1}(≤, ≥, ≠)| + n2^{n−3},

where |I_{1}(≤, ≥, ≠)| = 1, whose solution is as claimed in the theorem.

2.12 Class 233: I_{n}(012), F_{2n−1}

It was shown by Corteel, et al. [13] that the inversion sequences e ∈ I_{n}(<, <, −) = I_{n}(012) are those in which the positive elements of e are weakly decreasing. From that characterization, it was proven that

|I_{n}(<, <, −)| = |I_{n}(012)| = F_{2n−1}.

The sequence F_{2n−1} also counts the Boolean permutations, given by S_{n}(321, 3412) [30, 25].

2.13 Class 304: Conjectured to be counted by A229046

We derive a recurrence to count the (−, −, =)-avoiding inversion sequences. This sequence appears to be sequence A229046 in the OEIS. If true, this would give a combinatorial interpretation of A229046 which so far is defined only by a generating function and summation.

Note that I_{n}(−, −, =) is the set of e ∈ I_{n} with at most two copies of any entry and any equal entries must be adjacent.

Let S_{n,k} be the set of e ∈ I_{n}(−, −, =) with k distinct elements; that is, S_{n,k} consists of the inversion sequences e = (e_{1}, e_{2}, …, e_{n}) ∈ I_{n}(−, −, =) such that |{e_{1}, …, e_{n}}| = k. Let s(n, k) = |S_{n,k}|.

Theorem 26. for 1 ≤ k ≤ n,

s(n, k) = (n − 1 + k)s(n − 1, k − 1) + (n − k)s(n − 2, k − 1),

with initial conditions s(1, 1) = s(2, 1) = s(2, 2) = 1 and otherwise s(n, k) = 0 for k = 1 or n ≤ 2.

Proof. Let A_{n,k} be the subset of S_{n,k} consisting of those e in which e_{n} is unrepeated. Let B_{n,k} = S_{n,k} \ A_{n,k}. We can extend some e ∈ S_{n,k} to strings in S_{n+1,k} and S_{n+1,k+1} in the following ways.

If e ∈ B_{n,k}, then e · n ∈ A_{n+1,k+1}. Additionally, if x is one of the n − k values in {0, 1, …, n − 1} not used in e, then e · x ∈ A_{n+1,k+1}.

If e ∈ A_{n,k}, then e · n ∈ A_{n+1,k+1}. Furthermore, if x is one of the n − k values in {0, 1, …, n − 1} not used in e, then e · x ∈ A_{n+1,k+1}. Finally, if e_{n} = y, then e · y ∈ B_{n+1,k}. Letting a(n, k) = |A_{n,k}| and b(n, k) = |B_{n,k}|, we have

s(n, k) = a(n, k) + b(n, k);
b(n + 1, k) = a(n, k);
a(n + 1, k + 1) = (n − k + 1)b(n, k) + (n − k + 1)a(n, k)
= (n − k + 1)s(n, k).

So,

s(n, k) = a(n, k) + b(n, k)
= a(n, k) + a(n − 1, k)
= (n − k + 1)s(n − 1, k − 1) + (n − k)s(n − 2, k − 1).

Then |I_{n}(−, −, =)| = s(n, 1) + … + s(n, n). It is an open question to show that this theorem provides a refinement of A229046. Additionally, an interesting question is whether there is a natural description of the set Θ^{−1}(I_{n}(−, −, =)).

2.14 Classes 429(A,B,C): Catalan numbers

It is known that for any π ∈ S_{3}, |S_{n}(π)| is the Catalan number C_{n} = \binom{2n}{n}/(n + 1) [22, 27]. There are three inequivalent triples of relations ρ = (ρ_{1}, ρ_{2}, ρ_{3}) ∈ {≥, ≤, <, >, =, ≠, −}^{3} such that |I_{n}(ρ)| = C_{n}. The first corresponds naturally under Θ : S_{n} → I_{n} to a pattern π ∈ S_{3}.

2.14.1 Class 429A: Avoiding e_{j} > e_{k}

Theorem 27. I_{n}(−, >, −) = Θ(S_{n}(213)).

Proof. Observe that an e ∈ I_{n} has no i < j < k with e_{j} > e_{k} if and only if e is weakly increasing. Similarly, it can be checked that π ∈ S_{n} avoids 213 if and only if Θ(π) is weakly increasing.

2.14.2 Class 429B: Avoiding e_{j} ≥ e_{k} and e_{i} < e_{k}

Theorem 28. |I_{n}(−, ≥, <)| = C_{n}.

Proof. Observe that some e ∈ I_{n} has no i < j < k with e_{i} < e_{k} and e_{j} ≥ e_{k} if and only if the positive elements of e are strictly increasing.

Let I(x) = ∑_{n≥0} I_{n}(−, ≥, <)x^{n}. We will show that

I(x) = 1 + xI^{2}(x),  (7)

which has the solution \frac{1−\sqrt{1−4x}}{2x}; recall that this is the generating function for C_{n}.

Given any e ∈ I_{n}(−, ≥, <), consider the last maximal entry e_{t}; this is the largest t such that e_{t} = t − 1. The string (e_{1}, e_{2}, …, e_{t−1}) is an element of I_{t−1}(−, ≥, <). Additionally, it is straightforward to show that the string σ_{1−t}(e_{t+1}, e_{t+2}, …, e_{n}) (where t−1 is subtracted from each positive value) is an element of I_{n−t}(−, ≥, <). Conversely, any element of I_{n}(−, ≥, <) with last maximal entry in position t is of the form e′·(t−1)·σ_{1−t}(e′′) where e′ ∈ I_{t−1}(−, ≥, <) and e′′ ∈ I_{n−t}(−, ≥, <). This accounts for the “xI^{2}(x)′′ term of equation 7. Since this construction doesn’t account for the length 0 inversion sequence, we must also add a “1.”

Alternatively, it can be checked that the following map from I_{n}(−, >, −) to I_{n}(−, ≥, <) is a bijection. Send e ∈ I_{n}(−, >, −) to e′, defined by e′_{i} = 0 if e_{i} ∈ {e_{1}, …, e_{i−1}} and otherwise e′_{i} = e_{i}.

2.14.3 Class 429C: Avoiding e_{i} ≥ e_{j} and e_{i} ≥ e_{k}

In [24] we conjectured that |I_{n}(≥, −, ≥)| = C_{n}. This has been proven by Kim and Lin [16] where they also prove the following conjectures from the first version of this paper [24]:

• The number of e ∈ I_{n}(≥, −, ≥) with last(e) = k is equal to the number of standard tableaux of shape (n − 1, k) (ballot numbers A009766 in OEIS [15]).

• The number of e ∈ I_{n}(≥, −, ≥) with dist(e) = k is equal to the number of π ∈ S_{n}(123) with k − 1 descents (A166073 in the OEIS [15]). (The number of distinct elements is dist(e) = |{e_{1}, …, e_{n}}|.)

2.15 Class 523: S_{n}(¯3¯1542) and the nexus numbers

In this section we show that inversion sequences avoiding the pattern (≠, =, −) are equinumerous with permutations avoiding ¯3¯1542. Note that a permutation π avoids the pattern ¯3¯1542 if any occurrence of 542 in π is contained in an occurrence of 31542. We do this by proving that the (≠, =, −)-avoiding inversion sequences with k distinct entries are counted by the nexus numbers, (n + 1 − k)^{k} − (n − k)^{k}.

Observe that the sequences e ∈ I_{n} with no i < j < k satisfying e_{i} ≠ e_{j} = e_{k} are those in which the nonzero elements are distinct and once a nonzero element has occurred, at most one more 0 can appear in e. We use this characterization to show that I_{n}(≠, =, −) is counted by the sequence A047970 which counts diagonal sums of nexus numbers [15]. This sequence also counts permutations in S_{n} avoiding the barred pattern ¯3¯1542 (conjectured by Pudwell, and proved by Callan [11]).

Let T_{n,k} be the set of e ∈ I_{n}(≠, =, −) with k distinct elements. We prove the following refinement, which gives a new combinatorial interpretation of the nexus numbers, (n + 1 − k)^{k} − (n − k)^{k} (see A047969 in the OEIS [15]).

Theorem 29. For 1 ≤ k ≤ n, |T_{n,k}| = (n + 1 − k)^{k} − (n − k)^{k}.

Proof. We count T_{n,k} directly. When k = 1, |T_{n,k}| = 1 and the result follows. When k ≥ 2, any e ∈ T_{n,k} will contain some e_{t} such that 0 = e_{1} = e_{2} = … = e_{t−1} < e_{t} and there are no repeated values among e_{t}, e_{t+1}, …, e_{n}. Therefore, if e has k distinct values, there are two cases: (1) e begins with n − k + 1 zeros and contains no other zeros; or (2) e begins with n − k zeros and contains one further zero after e_{n−k+1} (which is the first nonzero entry).

For Case (1), the values e_{n−k+2}, e_{n−k+3}, …, e_{n} must all be distinct and nonzero. So, there are n − k + 1 possibilities for each, giving (n − k + 1)^{k−1} inversion sequences.

For Case (2), e_{n−k+1} must be nonzero, so there are n − k choices for this entry. Additionally, each of e_{n−k+1}, e_{n−k+2}, e_{n−k+3}, …, e_{n} must be distinct, though zero could appear after e_{n−k+1}. In total, this gives (n−k)(n−k+1)^{k−1} possible inversion sequences. Finally, we must remove any inversion sequence that does not include a zero among e_{n−k+2}, e_{n−k+3}, …, e_{n}; there are (n − k)^{k} such sequences. As a result, there are (n − k)(n − k + 1)^{k−1} − (n − k)^{k} inversion sequences that are part of Case (2).

Adding Cases (1) and (2), we have |T_{n,k}| = (n−k+1)^{k−1}+(n−k)(n−k+1)^{k−1}−(n−k)^{k} = (n − k + 1)^{k} − (n − k)^{k}, as desired.

2.16 Classes 772(A,B): Set partitions avoiding enhanced 3-cross-ings

In the first version of this paper [24], we conjectured that the avoidance sets for the patterns (−, ≤, ≥) and (≥, ≥, −) are counted by A108307. It was shown by Bousquet-Mélou and Xin that A108307 gives the number of set partitions of [n] avoiding enhanced 3-crossings [6].

The following theorem was proven by Lin through use of generating trees and the obstinate kernel method [21] and by Yan through construction of a bijection with 0,1 fillings of Ferrers shapes [31]. Lin’s proof makes use of our characterization of I_{n}(≥, ≥, −) in Observation 31.

Theorem 30 (Lin [21], Yan [31]). |I_{n}(≥, ≥, −)| is the number set partitions of [n] that avoid enhanced 3-crossings (or 3-nestings).

It follows that (≥, ≥, −) is indeed counted by A108307. We can additionally show that there is a bijection that not only proves Wilf-equivalence of the patterns 772A and 772B below, but also preserves a number of statistics. First consider the following characterizations of each class.

Observation 31. The inversion sequences with no i < j < k such that e_{i} ≥ e_{j} ≥ e_{k} are precisely those that can be partitioned into two increasing subsequences.

Proof. Suppose e has such a partition e_{a_{1}} < e_{a_{2}} < ⋯ < e_{a_{t}} and e_{b_{1}} < e_{b_{2}} < ⋯ < e_{b_{n−t}}. If there exists i < j < k such that e_{i} ≥ e_{j} ≥ e_{k}, then no two of i, j, k can both be in {a_{1}, …, a_{t}} or both be in {b_{1}, …, b_{n−t}}, so e avoids (≥, ≥, −). Conversely, if e avoids (≥, ≥, −), let a = (a_{1}, …, a_{t}) be the sequence of left-to-right maxima of e. Then e_{a_{1}} < e_{a_{2}} < ⋯ < e_{a_{t}}. Consider i, j ∉ {a_{1}, …, a_{t}} where i < j. The fact that e_{i} is not a left-to-right maxima implies there exists some e_{s} such that s < i and e_{s} ≥ e_{i}. Thus to avoid (≥, ≥, −), we must have e_{i} < e_{j}.

Observation 32. Let (e_{1}, e_{2}, …, e_{n}) ∈ I_{n}. Additionally, for any i ∈ [n], let M_{i} = max(e_{1}, e_{2}, …, e_{i−1}). Then e ∈ I_{n}(−, ≤, ≥) if and only if for every i ∈ [n], the entry e_{i} is a left-to-right maximum, or for every j where i < j, we have e_{i} > e_{j} or M_{i} < e_{j}.

Proof. Let e ∈ I_{n} satisfy the conditions of Observation 32 and, to obtain a contradiction, assume there exist i < j < k such that e_{j} ≤ e_{k} and e_{i} ≥ e_{k} (that is e_{j} ≤ e_{k} ≤ e_{i}). Notice that M_{j} = max{e_{1}, e_{2}, …, e_{j−1}} ≥ e_{i}. It follows that M_{j} ≥ e_{k} ≥ e_{j}, which contradicts our assumption.

Conversely, if (e_{1}, e_{2}, …, e_{n}) ∈ I_{n}(−, ≤, ≥), consider any e_{i}. If e_{i} is not a left-to-right maximum, then there exists some maximum value M_{i} = e_{s} such that s < i and e_{s} ≥ e_{i}. Therefore, in order to avoid a 201 pattern, any e_{j} where j > i must have e_{i} > e_{j} or e_{j} > M_{i} = e_{s}.

Theorem 33. For n ≥ 1, |I_{n}(≥, ≥, −)| = |I_{n}(−, ≤, ≥)|.

Proof. We exhibit a bijection based on the characterizations in Observations 31 and 32.

Given e ∈ I_{n}(≥, ≥, −), define f ∈ I_{n}(−, ≤, ≥) as follows. Let e_{a_{1}} < e_{a_{2}} < ⋯ < e_{a_{t}} be the sequence of left-to-right maxima of e and let e_{b_{1}} < e_{b_{2}} < ⋯ < e_{b_{n−t}} be the subsequence of remaining elements of e.

For i = 1, …, t, set f_{a_{i}} = e_{a_{i}}. For each j = 1, 2, …, n − t, we extract an element of the multiset B = {e_{b_{1}}, e_{b_{2}}, …, e_{b_{n−t}}} and assign it to f_{b_{1}}, f_{b_{2}}, …, f_{b_{n−t}} as follows:

f_{b_{j}} = max{k | k ∈ B − {f_{b_{1}}, f_{b_{2}}, …, f_{b_{j−1}}} and k < max(e_{1}, …, e_{b_{j}−1})}.

By definition, f satisfies the characterization property in Observation 32 of I_{n}(−, ≤, ≥).

The bijection in Theorem 33 preserves a number of statistics, as is shown below.

Corollary 34. All of the following statistics have the same distribution over I_{n}(−, ≤, ≥) and I_{n}(≥, ≥, −).

• the number of locations i such that e_{i} = i − 1;

• the largest entry of e; • the number of zeros of e (there can be at most two in either class);

• the number of distinct elements of e (and therefore the number of repeats in e);

• the number of left-to-right maxima of e.

An interesting future direction would be to relate these statistics on the classes 772A and 772B of inversion sequences to corresponding statistics on set partitions avoiding enhanced 3-crossings.

2.17 Classes 877(A,B,C,D): Bell numbers and Stirling numbers

The Bell number B_{n} is the number of partitions of the set [n] into nonempty blocks. The Stirling number of the second kind, S_{n,k} is the number of partitions of [n] into k blocks.

Among the triples of relations under consideration in this paper, four equivalence classes of patterns have avoidance sets that appear to be counted by the Bell numbers. We have shown this to be true for the classes 877A and 877C, whose inversion sequences have a similar character. We have not confirmed this for the classes 877B and 877D, nor have we confirmed that 877B and 877D are Wilf-equivalent, even though our experiments show that there is likely a bijection that preserves several statistics.

It is interesting to note that B(n) counts permutations avoiding 4¯132 and several other barred patterns of length 4, as shown by Callan [9]. Can any of these be related to one of the four patterns 877(A,B,C,D)?

2.17.1 Class 877A: Avoiding e_{i} < e_{j} = e_{k}

These are the 011-avoiding sequences. It was observed by Corteel, et al. [13] that these are the e ∈ I_{n} in which the positive elements of e are distinct, and that the 011-avoiding sequences in I_{n} with k zeros are counted by the Stirling number of the second kind, S_{n,k}. (This also appears in Stanley’s Enumerative Combinatorics, Vol. 1 [28].) Thus I_{n}(011) is counted by the Bell numbers.

2.17.2 Class 877B: Avoiding e_{i} = e_{j} ≥ e_{k}

The set I_{n}(=, ≥, −) consists of all e ∈ I_{n} such that no element appears more than twice and if an element, x, is repeated, all elements following the second occurrence of x must be larger than x.

From our calculations, it appears that I_{n}(=, ≥, −) is counted by the Bell numbers and, in fact, that the number of e ∈ I_{n}(=, ≥, −) with k repeats is given by A124323, the number of set partitions of [n] with k blocks of size larger than 1, but we have not proven this.

2.17.3 Class 877C: Avoiding e_{i} ≠ e_{j} ≠ e_{k} and e_{i} = e_{k}

Observe that these are the e ∈ I_{n} in which only adjacent elements of e can be equal.

Theorem 35. The number of e ∈ I_{n} in which only adjacent elements of e can be equal is B_{n}, the nth Bell number.

Proof. It can be checked that the following map from I_{n}(≠, ≠, =) to I_{n}(011) is a bijection. Send e ∈ I_{n}(≠, ≠, =) to e′, defined by e′_{i} = 0 if e_{i} ∈ {e_{1}, …, e_{i−1}} and otherwise e′_{i} = e_{i}.

2.17.4 Class 877D: Avoiding e_{i} ≥ e_{j} and e_{i} = e_{k}

I_{n}(≥, −, =) is the set of e ∈ I_{n} such that no element appears more than twice and if an element x is repeated, all elements between the two occurrences of x must be larger than x (Note the similarity to 877B).

From our calculations, it appears that I_{n}(≥, −, =) is also counted by the Bell numbers. Moreover, it appears that all of the following statistics are equally distributed over the classes 877B and 877D:

• the number of locations i such that e_{i} = i − 1;

• the largest entry of e;

• the number of zeros of e (there can be at most two in either class);

• the number of distinct elements of e (and therefore the number of repeats in e, which appears to be A124323).

2.18 Class 924: Central binomial coefficients

Theorem 36. |I_{n}(>, −, −)| = \binom{2n−2}{n−1}.

Proof. I_{n}(>, −, −) is the set of e ∈ I_{n} with e_{1} ≤ … ≤ e_{n−1} (counted by the Catalan number C_{n−1} as shown in Section 2.14) and with e_{n} chosen arbitrarily from {0, …, n − 1}. Thus

|I_{n}(>, −, −)| = nC_{n−1} = n (\frac{1}{n}\binom{2n − 2}{n − 1}) = \binom{2n − 2}{n − 1}.

2.19 Class 1064: Conjectured to be counted by A071356

Class 1064 are those inversion sequences with no i < j < k such that e_{i} > e_{j} ≤ e_{k}. These are the inversion sequences e ∈ I_{n} satisfying, for some t such that 1 < t ≤ n,

e_{1} ≤ … ≤ e_{t} > e_{t+1} > … > e_{n}.

Our experiments suggest that these are counted by A071356 in the OEIS, which Emeric Deutsch notes counts the number of underdiagonal lattice paths from (0, 0) to the line x = n using only steps R = (1, 0), V = (0, 1), and D = (1, 2) [15].

It also appears from our experiments that the distribution of the number of distinct elements of e is symmetric and unimodal on I_{n}(<, ≤, −). The number of e ∈ I_{n}(<, ≤, −) with dist(e) = k is given in the table below for n = 1, … 7.

1

1 1
1 4 1
1 9 9 1
1 16 38 16 1
1 25 110 110 25 1
1 36 255 480 255 36 1

If these observations are true in general, this provides a new simple combinatorial interpretation for A071356 with a natural refinement via a symmetric statistic.

2.20 Class 1265: S_{n}(2143, 3142, 4132)

Observe that I_{n}(>, <, −) is the set of e ∈ I_{n} satisfying, for some t with 1 < t ≤ n,

e_{1} ≤ e_{2} ≤ … ≤ e_{t} > e_{t+1} ≥ … ≥ e_{n}.

Our experiments suggested that I_{n}(>, <, −) is counted by A033321, which counts S_{n}(2143, 3142, 4132), as well as permutations avoiding several other triples of 4-permutations. Burstein and Stromquist confirmed this by recognizing a natural bijection between S_{n}(2143, 3142, 4132) and I_{n}(>, <, −) [8]. Their theorem is as follows. Recall from Section 1 that invcode : S_{n} → I_{n} is the reverse of the Lehmer code.

Theorem 37 (Burstein, Stromquist [8]). For n ≥ 1, invcode(S_{n}(2143, 3142, 4132)) = I_{n}(> , <, −).

From Section 1, invcode(π) = e if and only if e = Θ((π^{C})^{R}), giving the following.

Corollary 38. Θ(S_{n}(2143, 3142, 3241)) = I_{n}(>, <, −).

2.21 Class 1347: Conjectured to be counted by S_{n}(4123, 4132, 4213)

Our calculations suggest that I_{n}(>, −, ≤) is counted by A106228 in the OEIS, which was recently shown to count S_{n}(4123, 4132, 4213) by Albert, Homberger, Pantone, Shar and Vatter [3]. We have not been able to confirm that our avoidance sequence is A106228.

2.22 Class 1385: I_{n}(000) and the Euler up/down numbers

I_{n}(=, =, −) is the set of inversion sequences avoiding the pattern “000”. It was shown by Corteel, et al. [13] that |I_{n}(000)| = E_{n+1}, where E_{n} is the Euler up/down number which counts the number of π ∈ S_{n} such that π_{1} < π_{2} > π_{3} < π_{4} > · · ·. The proof was via a bijection with n-vertex 0-1-2 increasing trees, which are also counted by E_{n+1}.

Another family of permutations counted by E_{n+1} is the number of simsun permutations of [n], introduced by Simion and Sundaram [29]. A simsun permutation is one with no double descents, even after the removal of the elements {n, n − 1, …, k} for any k. It was shown that the number of e ∈ I_{n}(000) with n − k distinct elements is the number of simsun permutations of n with k descents [13]. The method of proof was to show that they satisfy the same recurrence. Recenty, Kim and Lin proved bijectively that the joint distribution of asc(π) and last(π) over simsun permutations π of [n] is the same as the joint distribution of dist(e) and last(e) + 1 for e ∈ I_{n}(000).

An interesting question is whether there is a natural bijection between I_{n}(000) and updown (or down-up) permutations of [n + 1]. For example, our calculations suggest that the number of e ∈ I_{n}(000) with e_{n} = k − 1 is the number of down-up permutations π of [n + 1] with π_{1} = k + 1.

2.23 Class 1694: I_{n}(102)

It was suggest by Corteel, et al. [13] that I_{n}(>, −, <) is counted by A200753 in the OEIS [15], a sequence defined by the generating function

A(x) = 1 + (x − x^{2})(A(x))^{3}.  (8)

This was confirmed by Mansour and Shattuck [23] who derived an explicit formula for |I_{n}(102)|.

Theorem 39 (Mansour-Shattuck [23]). The generating function ∑_{n≥0} |I_{n}(102)|x^{n} satisfies (8).

It would be interesting to find a direct combinatorial argument.

2.24 1806(A,B,C,D): large Schröder numbers

The large Schröder number R_{n} is the number of Schröder n-paths; that is, the number of paths in the plane from (0, 0) to (2n, 0) never venturing below the x-axis, and using only the steps (1, 1) (up), (1, −1) (down) and (2, 0) (flat).

In the area of pattern avoiding permutations, R_{n−1} counts the separable permutations S_{n}(2413, 3142), as well as S_{n}(α, β) for many other pairs (α, β) of patterns of length 4 [19]. We have four inequivalent triples of relations whose avoidance sets are counted by the large Schröder numbers, two of which (1806B and 1806D) correspond in natural ways to a pair of patterns of length 4.

2.24.1 Class 1806A: Avoiding e_{j} > e_{k} and e_{i} < e_{k}

These are the sequences avoiding 021. It was shown by Corteel, et al. [13] that e ∈ I_{n} avoids 021 if and only if its positive entries are weakly increasing. It was also proven in [13] that |I_{n}(021)| = R_{n−1}.

The following refinements were shown:

• The number of 021-avoiding inversion sequences e in I_{n} with k positions i such that e_{i} = i − 1 is equal to the number of Schröder (n − 1)-paths with k − 1 initial up steps.

• The number of 021-avoiding inversion sequences e in I_{n} with k zeros is equal to the number of Schröder (n − 1)-paths with k − 1 peaks (or k − 1 flat steps).

It was also shown that the ascent polynomial for I_{n}(021) is palindromic and corresponds to sequence A175124 in the OEIS.

2.24.2 Class 1806B: Avoiding e_{i} > e_{j} and e_{i} ≥ e_{k}

It is known that S_{n}(2134, 2143) is counted by R_{n−1} [19]. This is a member of “Class VI” in Kitaev’s book [17]; we use this fact to count I_{n}(>, −, ≥).

Theorem 40. |I_{n}(>, −, ≥)| = R_{n−1}.

Proof. We show that Θ(S_{n}(2134, 2143)) = I_{n}(>, −, ≥).

Let e ∈ I_{n} satisfy e_{i} > e_{j} and e_{i} ≥ e_{k} for some i < j < k. Let π = Θ^{−1}(e). Then min{π_{j}, π_{k}} > π_{i} and, since e_{i} > e_{j}, there must exist a < i such that both π_{a} > π_{i} and min{π_{j}, π_{k}} > π_{a}. Thus π_{a}π_{i}π_{j}π_{k} forms either a 2134 or a 2143.

Conversely, suppose, for some π ∈ S_{n}, that π_{a}π_{i}π_{j}π_{k} is one of the patterns 2134 or 2143 and let e = Θ(π). Let j′ be the smallest index larger than i for which π_{j′} > π_{a}. Then π_{i+1}, …, π_{j′−1} are all smaller than π_{a} < π_{j′} and so e_{i} > e_{j′}. Let k′ be the smallest index larger than j′ such that π_{k′} > π_{a}. Then, with the possible exception of π_{j′}, all of π_{i+1}, …, π_{k′−1} are smaller than π_{k′} (since these entries are necessarily smaller than π_{a}). In addition, since π_{i} < π_{a} < π_{k′}, we have e_{i} ≥ e_{k′}. Thus e has the pattern (>, −, ≥).

From our calculations, it appears that the ascent polynomial for I_{n}(>, −, ≥) is the same as that for 1806A, which was palindromic. This has been confirmed by Kim and Lin [16]. Since Θ sends descents to ascents, this implies that the descent polynomial for S_{n}(2134, 2143) is palindromic. This is not true in general for permutations avoiding pairs of patterns of length 4, even those counted by the large Schröder numbers. For example, it is not true of S_{n}(1234, 2134) or S_{n}(1324, 2314). However Fu, Lin, and Zeng have recently shown that the descent polynomial for the separable permutations S_{n}(2413, 3142) is γ-positive and therefore palindromic [14].

2.24.3 Class 1806C: Avoiding e_{i} ≥ e_{j} and e_{i} > e_{k}

Theorem 41. |I_{n}(≥, −, >)| = R_{n−1}.

Proof. We will construct a generating function for I_{n}(≥, −, >).

Let E(x) = ∑_{i=1}^{∞} |I_{n}(≥, −, >)|x^{n}. We will show that E(x) satisfies

E(x) = x + xE(x) + E^{2}(x),

whose solution is

E(x) = \frac{1 − x − \sqrt{x^{2} − 6x + 1}}{2}.

This implies that |I_{n}(≥, −, >)| is the (n − 1)th large Schröder number.

Let e = e_{1}e_{2} … e_{n} ∈ I_{n}(≥, −, >). Let e_{t} be the latest maximal entry of e; that is, max{i | e_{i} = i − 1}. If t = 1, then either e = (0) or e = (0, f_{1}, f_{2}, …, f_{n−1}) for some (f_{1}, f_{2}, … f_{n−1}) ∈ I_{n−1}(≥, −, >).

Now consider the case where t > 1. Notice that e_{t+1} ≤ t−1 since e_{t+1} cannot be maximal. This implies that (e_{1}, e_{2}, …, e_{t−1}, e_{t+1}) is an inversion sequence of length t. Furthermore, it is straightforward to show that (e_{1}, e_{2}, …, e_{t−1}, e_{t+1}) ∈ I_{n}(≥, −, >).

Additionally, for all e_{j} where j > t + 1, we must have e_{j} ≥ t − 1; if this is not the case, and there exists some j where e_{j} < t − 1, then we have t < t + 1 < j where e_{t} ≥ e_{t+1} and e_{t} > e_{j}. Therefore (e_{t} − t + 1, e_{t+2} − t + 1, …, e_{n} − t + 1) ∈ I_{n−t}(≥, −, >).

Conversely, for any sequences (e_{1}, e_{2}, …, e_{t}) ∈ I_{t}(≥, −, >) and (f_{1}, f_{2}, …, f_{n−t}) ∈ I_{n−t}(≥ , −, >), we can construct the inversion sequence

(e_{1}, e_{2}, …, e_{t−1}, f_{1} + t − 1, e_{t}, f_{2} + t − 1, f_{3} + t − 1, …, f_{n−t} + t − 1).

It is straightforward to show that this inversion sequence is in I_{n}(≥, −, >) and the last maximal entry is in the t-th position.

2.24.4 Class 1806D: Avoiding e_{i} ≥ e_{j} ≠ e_{k} and e_{i} ≥ e_{k}

Due to a result of Kremer [19], we know that |S_{n}(4321, 4312)| = R_{n−1}. We can prove that |I_{n}(≥, ≠, ≥)| is also enumerated by R_{n−1} by constructing a bijection between S_{n} and I_{n} that restricts to a bijection between S_{n}(4321, 4312) and I_{n}(≥, ≠, ≥). This bijection is useful for another class of inversion sequences: it will be used later to prove results related to I_{n}(>, ≠, >) (classified as 3720).

Definition 42. Let π ∈ S_{n} and define ϕ(π) = e_{1}e_{2} … e_{n} ∈ I_{n} as follows, starting with e_{n} and defining entries in reverse order.

1. e_{n} = π_{n} − 1

2. For 1 ≤ i < n,

(a) if π_{i} ≤ i, then e_{i} = π_{i} − 1.

(b) otherwise, if π_{i} is the k-th largest element of {π_{1}, …, π_{i}} then e_{i} is the k-th

smallest element of the set {e_{i+1}, ..., e_{n}}.

Lemma 43. For π ∈ S_{n}, ϕ(π) ∈ I_{n}.

Proof. To show that ϕ(π) ∈ I_{n}, we need to prove that 0 ≤ e_{i} ≤ i − 1 for every i ∈ [n]. We will use an inductive argument, starting with e_{n}, to show this. We defined e_{n} = π_{n} − 1; since 1 ≤ π_{n} ≤ n, it follows that 0 ≤ e_{n} ≤ n − 1, as desired. Now consider e_{i} and assume that for all e_{j} among e_{i+1}e_{i+2} … e_{n}, 0 ≤ e_{j} ≤ j − 1. If π_{i} ≤ i, then e_{i} = π_{i} − 1 and it immediately follows that 0 ≤ e_{i} ≤ i − 1.

If instead π_{i} > i, assume that π_{i} is in the k-th largest element of {π_{1}, …, π_{i}}. Notice that each value of {e_{i+1}, ..., e_{n}} corresponds to an entry π_{j} where i < j and π_{j} ≤ j (any entry π_{j} where π_{j} > j will repeat a value). So, there are n − π_{i} − k + 1 entries π_{j} such that i < j and π_{j} > π_{i}; in turn, this implies that there are (n − i) − (n − π_{i} − k + 1) = π_{i} − (i + 1) + k entries π_{j} such that i < j and π_{j} < π_{i}. At a maximum, π_{i} − (i + 1) of these entries are greater than i; this leaves k entries occurring after π_{i} that are less than or equal to i. Each of these entries corresponds to a value in {e_{i+1}, ..., e_{n}} that is less than or equal to i − 1. It follows, that e_{i} ≤ i − 1, as desired.

Lemma 44. ϕ : S_{n} → I_{n} is a bijection.

Proof. Let e = e_{1}e_{2} … e_{n} ∈ I_{n}. We can define the inverse image of e, ϕ^{−1}(e) = π_{1}π_{2} … π_{n} in reverse order, starting with π_{n} so that π_{n} = e_{n} + 1. For 1 ≤ i < n, if e_{i} ≠ e_{j} for all j where i < j ≤ n, then π_{i} = e_{i} + 1; otherwise, if e_{i} is the k-th smallest value of {e_{i+1}, …, e_{n}}, π_{i} is the k-th largest value of [n] that does not appear among π_{i+1}, …, π_{n}.

It is interesting to note that for any π ∈ S_{n}, exc(π) = repeats(ϕ(π)), where exc(π) is the number of positions i such that π_{i} > i.

Now, we show that ϕ restricts to a bijection between S_{n}(4321, 4312) and I_{n}(≥, ≠, ≥) by proving the following:

Theorem 45. ϕ(S_{n}(4321, 4312)) = I_{n}(≥, ≠, ≥)

Proof. Consider some π ∈ S_{n} that contains an occurrence of 4321 or 4312. So, there exists some a < i < j < k such that π_{a}π_{i}π_{j}π_{k} form a 4321 or 4312 pattern. We will show that there exists an occurrence of the pattern (≥, ≠, ≥) in ϕ(π) = e.

We must consider two cases. If π_{i} ≤ i, then j > π_{i} > π_{j} and k > π_{i} > π_{k}. Therefore, e_{i} = π_{i} − 1, e_{j} = π_{j} − 1 and e_{k} = π_{k} − 1. So, since π_{i} > max{π_{j}, π_{k}} and π_{j} ≠ π_{k}, e_{i}, e_{j}, e_{k} forms an occurrence of (≥, ≠, ≥).

Now assume π_{i} > i. Recall that e_{i} is the t-th smallest element of {e_{i+1}, …, e_{n}} if π_{i} is the t-th largest element of {π_{1}, π_{2}, …, π_{i}}. Since π_{a} is larger than and occurs before π_{i}, we know that t is at least 2. So, if e_{j′} and e_{k′}, where j′ < k′, are the two smallest distinct values in the set {e_{i+1}, …, e_{n}}, we are guaranteed that e_{i} ≥ e_{j′} and e_{i} ≥ e_{k′}; so, e_{i}, e_{j′}, e_{k′} form the pattern (≥, ≠, ≥).

For the converse, let π ∈ S_{n} such that e = ϕ(π) has indices i < j < k such e_{i} ≥ e_{j}, e_{i} ≥ e_{k}, and e_{i} ≠ e_{k}. We show that π contains 4321 or 4312.

If e_{i} ∈ {e_{i+1}, …, e_{n}} then, by definition of ϕ, π_{i} > i and e_{i} is the kth smallest element of {e_{i+1}, …, e_{n}} for some k ≥ 2, noting that the distinct elements e_{j} and e_{k} are both at most e_{i}. Then, again by definition of ϕ, π_{i} is the kth largest element of {π_{1}, …, π_{i}}, so there is some a < i with π_{a} > π_{i}. To show that π contains one of the patterns 4321 or 4312, it remains to show there are at least two elements of {π_{i+1}, …, π_{n}} that are smaller than π_{i}. The number of elements in π that are larger than π_{i} is n − π_{i} < n − i. At least one of these is to the left of π_{i} in π. Thus at most n − i − 2 can be in the n − i positions to the right of π_{i}.

If e_{i} ∉ {e_{i+1}, …, e_{n}} then, by definition of ϕ, π_{i} ≤ i and e_{i} = π_{i} −1. Since e_{j} ≤ e_{i} ≤ i < j and e_{k} ≤ e_{i} ≤ i < k, we have e_{j} = π_{j} − 1 and e_{k} = π_{k} − 1, so that π_{i}π_{j}π_{k} has the pattern 321 or 312. To show that π contains 4321 or 4312, it remains to show there is an a < i such that π_{a} > π_{i}. Note that there are n − π_{i} ≥ n − i elements of π larger than π_{i}. The n − i positions to the right of π_{i} hold at least two elements smaller that π_{i}. So there must be a larger element to the left of π_{i}, that is, an a < i such that π_{a} > π_{i}.

Our calculations suggested that the ascent polynomial for the inversion sequences in I_{n}(≥, ≠, ≥) is the same as the (symmetric) ascent polynomial for 1806A. This has been proven by Kim and Lin in [16]. It also appears that the number of these inversion sequences with k “repeats” is counted by A090981, the number of Schröder paths with k ascents.

2.25 Class 2074: Baxter numbers

In the earlier version of this paper [24], it was conjectured that the avoidance sequence for the pattern (≥, ≥, >) is A001181 in the OEIS. This sequence counts the Baxter permutations, which is a result of Chung, et al. in [12]. A Baxter permutation π is one that avoids the vincular patterns 3\underline{14}2 and 2\underline{41}3; that is, there is no i < j < k such that π_{j} < π_{k} < π_{i} < π_{j+1} or π_{j} > π_{k} > π_{i} > π_{j+1}.

Kin and Lin prove this via the so-called obstinate kernel method [16]:

Theorem 46 ([16]). |I_{n}(≥, ≥, >)| is the number of Baxter permutations of [n].

Note that the Baxter permutations contain the separable permutations S_{n}(3142, 2413) which are counted by the large Schröder numbers. Similarly, I_{n}(≥, ≥, >) contains the inversion sequences I_{n}(≥, −, >) (which define class 1806C) which are also counted by the large Schröder numbers. It would be nice to find a bijection between (≥, ≥, >)-avoiding inversion sequences and Baxter permutations that restricts to a bijection between (≥, −, >)-avoiding inversion sequences and separable permutations.

2.26 Classes 2549(A,B,C): Conjectured to be counted by S_{n}(4231, 42513)

Albert, et al. [1] showed that

|S_{n}(4231, 42513)| = ∑_{i=0}^{n} \frac{n − i}{2i + n}\binom{2i + n}{i},

which is sequence A098746 in the OEIS [15]. It appears from our calculations that the inequivalent classes I_{n}(>, −, >), I_{n}(>, ≠, ≥), and I_{n}(≥, ≠, >) have the same avoidance sequence A098746. We will show at least that the classes 2549A (I_{n}(>, −, >)) and 2549C (I_{n}(≥, ≠, >)) are Wilf-equivalent.

Theorem 47. The patterns (>, −, >) and (≥, ≠, >), defining classes 2549A and 2549C respectively, are Wilf-equivalent.

The proof relies on Theorem 53 in the next section and will be given there.

2.27 Classes 2958(A,B,C,D): Plane permutations and the semi-Baxter numbers

In an earlier version of this paper [24], we conjectured that all four pattern equivalence classes 2958(A,B,C,D) have avoidance sets equinumerous with the plane permutations, S_{n}(21¯354). These are permutations in which every occurrence of the pattern 2154 is contained in an occurrence of 21354. We showed that the classes 2958(B,C,D) are Wilf-equivalent (Theorems 53 and 54 below); additionally, we provided a characterization of the inversion sequences avoiding 2958B (Observation 50 below) and proved a recurrence for the avoidance sequence of 2958B.

We can now make use of a recent paper of Bouvel, Guerrini, Rechnitzer, and Rinaldi [7] to confirm our conjecture.

Bouvel, et al. coined the term “semi-Baxter” for the sequence of integers that enumerates the class of permutations avoiding the vincular pattern 2\underline{41}3 (an occurrence of 2\underline{41}3 is an occurrence of 2413 where the “4” and “1” occur consecutively) [7]. They derived a functional equation and used it to get a closed-form formula for the semi-Baxter sequence.

Moreover, Bouvel, et al. showed that semi-Baxter permutations are equinumerous with plane permutations: they used generating trees and proved that both classes of permutations are generated by the same succession rule Ω_{semi}. Therefore, their formula for semi-Baxter numbers also enumerates plane permutations, which fulfills a challenge posed by Bousquet-Mélou and Butler [5].

Then, using our characterization of the inversion sequences avoiding 2958B, Bouvel, et al. showed that those inversion sequences are also generated by the succession rule Ω_{semi} and are therefore equinumerous with plane and semi-Baxter permutations. This result, together with our proof below of the Wilf-equivalence of 2958(B,C,D), establishes that all three patterns give rise to avoidances sets that are equinumerous with plane permutations.

To complete the picture and confirm our original conjecture, we will show that inversion sequences avoiding the pattern 2958A also grow according to the succession rule Ω_{semi}.

2.27.1 Class 2958A: Avoiding e_{j} < e_{k} and e_{i} ≥ e_{k}

Bouvel, et al. utilize generating trees to relate distinct combinatorial objects to the semi-Baxter sequence, providing a succession rule for the sequence. To use this succession rule, each combinatorial object is identified with a label, (h, k), which is based on the properties of the object. The rule then describes the labels of those members of the same class of objects that can be obtained by systematically adding one atom. For our purposes, adding one atom will correspond to adding a new last entry to an inversion sequence.

The semi-Baxter sequence follows the succession rule:

Ω_{semi} = \begin{cases}(1, 1) \\ (h, k) ⇝ & (1, k + 1), …, (h, k + 1) \\ & (h + k, 1), …, (h + 1, k). \end{cases}

The top line of the succession rule gives the label for the “root” object (which will be the inversion sequence (0) in our case) and the second line shows the labels of the inversion sequences obtained by systematically adding a new last entry.

We show how to define the labels (h, k) for inversion sequences avoiding (−, <, ≥) in such a way that those sequences grow according to the succession rule Ω_{semi}.

Theorem 48. I_{n}(−, <, ≥) = I_{n}(101, 201) grows according to the succession rule Ω_{semi} and is therefore enumerated by the semi-Baxter sequence.

Proof. For each e ∈ I_{n}(−, <, ≥), we will account for all e′ ∈ I_{n+1}(−, <, ≥) obtainable by appending a new last entry e_{n+1}. Define an active site for e to be a value c such that (e_{1}, e_{2}, …, e_{n}, c) ∈ I_{n+1}(−, <, ≥). Now, for any inversion sequence e, let h denote the number of active sites less than or equal to maxx(e), and let k denote the number of active sites greater than maxx(e). First notice that for e = (0) ∈ I_{1}(−, <, ≥), since maxx(e) = 0, the set of active sites is {0, 1}, with 0 ≤ maxx(e) and 1 > maxx(e), so (h, k) = (1, 1).

For n ≥ 2, let e ∈ I_{n}(−, <, ≥). Let e_{n+1} be the value of one of the active sites for e and consider e′ = (e_{1}, …, e_{n+1}) ∈ I_{n+1}(−, <, ≥).

If e_{n+1} ≤ maxx(e), then since e′ must only avoid 101 and 201, an active site for e′ must either be less than or equal to e_{n+1} or greater than maxx(e) = maxx(e′). So, the labels of the inversion sequences we obtain by appending such an active site e_{n+1} to e are (1, k + 1), (2, k + 1), …, (h, k + 1).

If e_{n+1} > maxx(e), again since e′ must only avoid 101 and 201, all sites active for e are also active for e′. Additionally, e′ will have a new active site: n + 1. Since maxx(e′) > maxx(e), some active sites for e that were counted with k will now be counted with h when finding the label for e′. The labels of the inversion sequences we obtain by appending such an active site e_{n+1} to e are (h + k, 1), (h + k − 1, 2), …, (h + 1, k).

It follows that I_{n}(−, <, ≥) grows by the succession rule Ω_{semi} and is therefore enumerated by the semi-Baxter sequence.

2.27.2 Class 2958B: Avoiding e_{i} > e_{j} ≥ e_{k}

Note that I_{n}(>, ≥, −) = I_{n}(210, 100). It was shown by Corteel, et al. [13] that the inversion sequences avoiding 210 (class 4306A) have the following useful characterization.

Define a weak left-to-right maximum in an inversion sequence e to be a position j such that e_{i} ≤ e_{j} for all i ∈ [j − 1].

For e ∈ I_{n}, let a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{t} be the sequence of weak left-to-right maxima of e. Let b_{1} < b_{2} < ⋯ < b_{n−t} be the sequence of remaining indices in [n]. Let e^{top} = (e_{a_{1}}, e_{a_{2}}, …, e_{a_{t}}) and top(e) = e_{a_{t}}. Let e^{bottom} = (e_{b_{1}}, e_{b_{2}}, …, e_{b_{n−t}}) and bottom(e) = e_{b_{n−t}}. If every entry of e is a weak left-to-right maximum, then e^{bottom} is empty and we set bottom(e) = −1.

Observation 49 ([13]). The inversion sequence e avoids 210 if and only if e^{top} and e^{bottom} are weakly increasing sequences.

We can extend this to I_{n}(210, 100).

Observation 50. The inversion sequence e avoids both 210 and 100 if and only if e^{top} is weakly increasing and and e^{bottom} is strictly increasing.

Using Observation 50, Bouvel, et al. showed the following (where SB_{n} denotes the nth semi-Baxter number):

Theorem 51 ([7]. Theorem 20). There are as many inversion sequences of size n avoiding 210 and 100 as plane permutations of size n. In other words |I_{n}(210, 100)| = SB_{n}.

The characterization in Observation 50 can be used to derive a recurrence.

Theorem 52. Let S_{n,a,b} be the number of e ∈ I_{n}(201, 100) with top(e) = a and bottom(e) = b. Then

S_{n,a,b} = ∑_{i=−1}^{b−1} S_{n−1,a,i} + ∑_{j=b+1}^{a} S_{n−1,j,b},

with initial conditions S_{n,a,b} = 0 if a ≥ n and S_{n,a,−1} = \frac{n−a}{n} \binom{n−1+a}{a}.

From Theorem 52 we get:

|I_{n}(210, 100)| = ∑_{a=0}^{n−1} ∑_{b=−1}^{a−1} S_{n,a,b} = \frac{1}{n + 1}\binom{2n}{n} + ∑_{a=0}^{n−1} ∑_{b=0}^{a−1} S_{n,a,b}.  (9)

2.27.3 Class 2958C: Avoiding e_{i} ≥ e_{j} > e_{k}

Now we will show that the class 2958B is Wilf-equivalent to 2958C.

Theorem 53. The patterns (−, <, ≥) and (≥, >, −), defining classes 2958B and 2958C respectively, are Wilf-equivalent.

Proof. The avoidance sets for classes 2958B and 2958C are I_{n}(100, 210) and I_{n}(110, 210), respectively. We describe a bijection

α : I_{n}(110, 210) → I_{n}(100, 210).

For e ∈ I_{n}(110, 210), let α(e) = e′ = (e′_{1}, …, e′_{n}) where, for 1 ≤ j ≤ n,

e′_{j} = \{ \begin{matrix}max\{e_{1}, …, e_{j}\}, & if e_{j} = e_{k} for some k > j; \\ e_{j}, & otherwise. \end{matrix}  (10)

Note that for 1 ≤ j ≤ n,

e′_{j} ≤ max{e_{1}, …, e_{j}} = max{e′_{1}, …, e′_{j}}  (11)

and if e′_{j} ≠ e_{j} then

e′_{j} = max{e_{1}, …, e_{j}} ≥ e′_{i} for 1 ≤ i < j.  (12)

To see that e′ avoids 100, suppose e′_{i} > e′_{j} = e′_{k} for some i < j < k. Then by (12), we must have e′_{j} = e_{j} and e′_{k} = e_{k}. But from the definition of α (10), if e_{j} = e_{k} where j < k then e′_{j} = max{e_{1}, …, e_{j}} ≥ e′_{i}, which is a contradiction.

To see that e′ avoids 210, suppose that e′_{i} > e′_{j} > e′_{k} for some i < j < k. Again by (12), e′_{j} = e_{j} and e′_{k} = e_{k}. Since e avoids 210, e′_{i} ≠ e_{i} so e′_{i} = max{e_{1}, …, e_{i}} = e_{s} for some s ∈ [i]. But then e_{s} > e_{j} > e_{k} is a 210 in e.

Thus e′ = α(e) ∈ I_{n}(100, 210). To show that α is a bijection, we define its inverse β. First we make an observation. Consider some e ∈ I_{n}(110, 210) and an entry e_{j} such that

e′_{j} ≠ e_{j} in α(e) = e′. This implies that there exists some index k with j < k and e_{j} = e_{k} = m for some value m. Additionally, it must be the case that m < M = max{e_{1}, …, e_{j−1}} = e_{i} where i ∈ [j −1] (else, e′_{j} = m). Then, since e avoids 210, we must have m = min{e_{j}, …, e_{n}}. Thus, for e′ = α(e) we have

e′_{i} = e_{i} = M = e′_{j} > e_{j} = m = min{e_{j}, …, e_{n}} = min{e′_{j}, …, e′_{n}}.

So, we can reconstruct e from e′ by defining β : I_{n}(100, 210) → I_{n}(110, 210) as follows. For e ∈ I_{n}(100, 210), let β(e) = e′ = (e′_{1}, …, e′_{n}) where for 1 ≤ j ≤ n

e′_{j} = \{ \begin{matrix}min\{e_{j}, …, e_{n}\}, & if e_{i} = e_{j} for some i < j; \\ e_{j}, & otherwise. \end{matrix}

Then β(α(e)) = e. We can check similarly that β(e) ∈ I_{n}(110, 210) and α(β(e)) = e.

We now return to the proof of the Wilf-equivalence of the classes 2549A and 2549C from the previous section.

Proof of Theorem 47. Observe that 2549C ⪯ 2958C and 2549A ⪯ 2958B in the following sense:

2549C : I_{n}(≥, ≠, >) = I_{n}(110, 210, 201) ⊆ I_{n}(110, 210) = I_{n}(≥, >, −) : 2958C
2549A : I_{n}(>, −, >) = I_{n}(100, 210, 201) ⊆ I_{n}(100, 210) = I_{n}(>, ≥, −) : 2958B

We check that the mapping α (10) restricts to a bijection between inversion sequences in class 2549C and in class 2549A.

Let e ∈ I_{n}(110, 210) and let e′ = α(e). Suppose e avoids the pattern 201, but that for some i < j < k, e′_{i} > e′_{j} < e′_{k} and e′_{i} > e′_{k}. Then by (12), e′_{j} = e_{j} and e′_{k} = e_{k}. But, since e avoids 201, e′_{i} ≠ e_{i}. Then, by definition of α, there is an s ∈ [i − 1] such that e′_{i} = e_{s}. But then e_{s}e_{j}e_{k} forms a 201 pattern in e, a contradiction.

For the converse, let e ∈ I_{n}(100, 210) and let e′ = β(e). Suppose there is i < j < k such that e′_{i}e′_{j}e′_{k} form a 201. We show e must also contain 201. By definition of β, since e′_{i} > e′_{j}, e_{i} = e′_{i}. Also, there exists s : j ≤ s ≤ n such that e′_{j} = e_{s} and t : k ≤ t ≤ n such that e′_{k} = e_{t}. Since e avoids 210, it must be that s < t. But then e_{i}e_{s}e_{t} is a 201 in e.

2.27.4 2958D: Avoiding e_{j} ≤ e_{k} and e_{i} > e_{k}

Theorem 54. The patterns (>, ≥, −) and (−, ≤, >), defining classes 2958B and 2958D respectively, are Wilf-equivalent.

Proof. The inversion sequences in classes 2958B and 2958D are defined by I_{n}(210, 100) and I_{n}(201, 100), respectively. It was shown in [13], Theorem 5, that the following gives a bijection from I_{n}(210) to I_{n}(201). It can be checked that this mapping preserves 100-avoidance and therefore restricts to a bijection from I_{n}(210, 100) to I_{n}(201, 100).

Given e ∈ I_{n}(210), define f ∈ I_{n}(201) as follows. Let e_{a_{1}} ≤ e_{a_{2}} ≤ ⋯ ≤ e_{a_{t}} be the sequence of weak left-to-right maxima of e and let e_{b_{1}}, e_{b_{2}}, …, e_{b_{n−t}} be the subsequence of remaining elements of e. Since e avoids both 210 and 100, e_{b_{1}} < e_{b_{2}} < ⋯ < e_{b_{n−t}}.

For i = 1, …, t, set f_{a_{i}} = e_{a_{i}}. For each j = 1, 2, …, n − t, we extract an element of the multiset B = {e_{b_{1}}, e_{b_{2}}, …, e_{b_{n−t}}} and assign it to f_{b_{1}}, f_{b_{2}}, …, f_{b_{n−t}} as follows:

f_{b_{j}} = max{k | k ∈ B − {f_{b_{1}}, f_{b_{2}}, …, f_{b_{j−1}}} and k < max(e_{1}, …, e_{b_{j}−1})}.

This is the same mapping that was used in Section 2.16 to show that the patterns 772A and 772B are Wilf-equivalent. Note that

772B : I_{n}(210, 110, 100, 000) ⊆ I_{n}(210, 100) : 2958B;

772A : I_{n}(201, 101, 100, 000) ⊆ I_{n}(201, 100) : 2958D.

By the Wilf-equivalencies between classes B, C, and D, we know that all of 2958(A,B,C,D) are enumerated by the semi-Baxter numbers.

2.28 Classes 3207(A,B): I_{n}(101), I_{n}(110)

It was shown by Corteel, et al. [13] that both I_{n}(<, −, =) = I_{n}(101) and I_{n}(=, >, −) = I_{n}(110) are counted by the sequence A113227 in the OEIS [15], where it is said to count S_{n}(1\underline{23}4). S_{n}(1\underline{23}4) is the set of permutations with no i < j < k < ℓ such that π_{i} < π_{j} < π_{k} < π_{ℓ} and k = j + 1.

It was proven by David Callan in [10], that S_{n}(1\underline{23}4) is in bijection with increasing ordered trees with n + 1 vertices whose leaves, taken in preorder, are also increasing. He showed that if u_{n,k} is the number of such trees with n + 1 vertices in which the root has k children then

u_{n,k} = u_{n−1,k−1} + k ∑_{j=k}^{n−1} u_{n−1,j}  (13)

with initial conditions u_{0,0} = 1 and u_{n,k} = 0 if k > n, or n > 0 and k = 0.

It was shown by Corteel, et al. [13] that the number of e ∈ I_{n}(101) with exactly k zeros is u_{n,k}, as is the number of e ∈ I_{n}(110) with exactly k zeros. As a consequence, 101 and 110 are Wilf-equivalent and both avoidance sets are counted by A113227.

2.29 Class 3720: Quadrant Marked Mesh Patterns

In this section we prove that I_{n}(>, ≠, >) is counted by the sequence A212198 in the OEIS [15] where it is said to count permutations avoiding a particular marked mesh pattern.

Kitaev and Remmel [18] introduced the idea of quadrant marked mesh patterns, a definition of which is given below.

Definition 55. Let π = π_{1}π_{2} … π_{n} ∈ S_{n}. Consider the graph of π, G(π), consisting of the points (i, π_{i}) for all i ∈ [n]. The entry π_{i} is said to match the quadrant marked mesh pattern MMP(a, b, c, d), if in G(π) there are at least a points to the northeast of (i, π_{i}), at least b points to the northwest of (i, π_{i}), at least c points to the southwest of (i, π_{i}), and at least d points to the southeast of (i, π_{i}). The order in which we consider quadrants proceeds counterclockwise, beginning with the top right quadrant.

Let S_{n}(MMP(a, b, c, d)) denote the set of permutations of length n where no π_{i} matches MMP(a, b, c, d). We will prove that |S_{n}(MMP(0, 2, 0, 2))| = |I_{n}(>, ≠, >)| for all n. By symmetry established by Kitaev and Remmel [18], this implies that |I_{n}(>, ≠, >)| = |S_{n}(MMP(2, 0, 2, 0))|. In our proof, we make use of the bijection ϕ from Section 2.24, whose definition was given in Definition 42. Specifically, we can prove the following:

Theorem 56. For all n, ϕ(S_{n}(MMP(0, 2, 0, 2))) = I_{n}(>, ≠, >).

Proof. This proof is very similar to the proof of Theorem 45. Consider some π ∈ S_{n} such that there exists some π_{i} that matches MMP(0, 2, 0, 2). This implies that there exist indices a < b < i < j < k such that min{π_{a}, π_{b}} > π_{i} > max{π_{j}, π_{k}}. We will show that there exists an occurrence of the pattern (>, ≠, >) in ϕ(π) = e.

We must consider two cases. If π_{i} ≤ i, then j > π_{i} > π_{j} and k > π_{i} > π_{k}. Therefore, e_{i} = π_{i} − 1, e_{j} = π_{j} − 1 and e_{k} = π_{k} − 1. So, since π_{i} > max{π_{j}, π_{k}} and π_{j} ≠ π_{k}, e_{i}, e_{j}, e_{k} forms an occurrence of (>, ≠, >).

Now assume π_{i} > i. Recall that e_{i} is the t-th smallest element of {e_{i+1}, …, e_{n}} if π_{i} is the t-th largest element of {π_{1}, π_{2}, …, π_{i}}. Since π_{a}, π_{b} are larger than and occur before π_{i}, we know that t is at least 3. If e_{j′} and e_{k′} are the two smallest distinct values in the set {e_{i+1}, …, e_{n}}, we are guaranteed that e_{i} > e_{j′} and e_{i} > e_{k′}; so, e_{i}, e_{j′}, e_{k′} form the pattern (>, ≠, >).

For the converse, let π ∈ S_{n} such that e = ϕ(π) has indices i < j < k such e_{i} > e_{j}, e_{i} > e_{k}, and e_{i} ≠ e_{k}. We show that π contains an entry that matches MMP(0, 2, 0, 2).

If e_{i} ∈ {e_{i+1}, …, e_{n}} then, by definition of ϕ, π_{i} > i and e_{i} is the kth smallest element of {e_{i+1}, …, e_{n}} for some k ≥ 2, noting that the distinct elements e_{j} and e_{k} are both less than e_{i}. Then, again by definition of ϕ, π_{i} is the kth largest element of {π_{1}, …, π_{i}}, so there is some a, b < i with π_{a}, π_{b} > π_{i}. To show that π_{i} matches MMP(0, 2, 0, 2) it remains to show there are at least two elements of {π_{i+1}, …, π_{n}} that are smaller than π_{i}. The number of elements in π that are larger than π_{i} is n − π_{i} < n − i. At least two of these are to the left of π_{i} in π. Thus at most n − i − 2 can be in the n − i positions to the right of π_{i}.

If e_{i} ∉ {e_{i+1}, …, e_{n}} then, by definition of ϕ, π_{i} ≤ i and e_{i} = π_{i} − 1. Since e_{j} ≤ e_{i} ≤ i < j < k and e_{k} ≤ e_{i} ≤ i < k, we have e_{j} = π_{j} − 1 and e_{k} = π_{k} − 1, so that π_{i}π_{j}π_{k} has the pattern 321 or 312. To show that π_{i} matches MMP(0, 2, 0, 2), it remains to show there is an a < i and b < i such that π_{a}, π_{b} > π_{i}. Note that there are n − π_{i} ≥ n − i elements of π larger than π_{i}. The n − i positions to the right of π_{i} hold at least two elements smaller that π_{i}. So there must be two larger element to the left of π_{i}, as desired.

The bijection ϕ turns out to be a versatile tool, giving interesting results when restricted to S_{n}(MMP(k, 0, k, 0)) for any positive integer k. In this case, ϕ(S_{n}(MMP(k, 0, k, 0))) maps to inversion sequences that avoid a particular set of length k + 1 patterns.

2.30 Class 5040: n!

The last equivalence class of patterns in this section is the set of those avoided by all inversion sequences. There are 41 such patterns among our 343, including the representative below. One such class is all inversion sequences with no i > j > k such that e_{i} = e_{j} = e_{k} and e_{i} ≠ e_{k}.

3 Results about patterns whose sequences don’t appear in the OEIS [15]

Table 3 lists all equivalence classes of the patterns ρ ∈ {<, >, ≤, ≥, =, ≠, −}^{3} whose avoidance sequences did not appear in the OEIS (and have subsequently been entered). We were able to derive the avoidance sequences for a few of these patterns and prove Wilf-equivalence of some others. In this section we describe our results and leave identification of the avoidance sequences of the remaining patterns in Table 3 as questions for future study.

3.1 Counting results

3.1.1 Class 805: Avoiding e_{i} ≤ e_{j} > e_{k} and e_{i} ≠ e_{k}

We were able to prove that I_{n}(≤, >, ≠) (A279557) is counted by a sum of Catalan numbers. Recall that C_{n} = \frac{1}{n+1} \binom{2n}{n} and C(x) = ∑_{n≥0} C_{n}x^{n} = \frac{1−\sqrt{1−4x}}{2x}.

Observe that I_{n}(≤, >, ≠) is the set of e ∈ I_{n} satisfying, for some t with 1 < t ≤ n and k with t < k < n,

0 = e_{1} = e_{2} = … = e_{t−1} < e_{t} ≤ e_{k} ≤ e_{k+1} ≤ … ≤ e_{n}

with 0 = e_{t+1} = ⋯ = e_{k−1}.

Lemma 57. Let A(x) = ∑_{n≥0} |I_{n}(≤, >, ≠)|x^{n}. Then A(x) = \frac{(1−2x)(1−2x−\sqrt{1−4x})}{2x^{2}(1−x)}.

Proof. For any e = (e_{1}, e_{2}, …, e_{n}) ∈ I_{n}(≤, >, ≠), e satisfies one of the following three cases:

1. e = ∅ or e has no maximal entries,

2. e = (0, 0, …, 0, e_{t}, e_{t+1}, …, e_{n}) where t is the index of the last occurrence of a maximal entry of e, or

3. e = (0, 0, …, 0, e_{t}, …, e_{j}, …, e_{n}) where e_{t} ≠ 0 and j is the index of the last occurrence of a maximal entry of e.

The generating function for case 1 is (1+xA(x)), since any inversion sequence in I_{n}(≤, > , ≠) with no maximal entries can be constructed by appending a 0 to the front of an inversion sequence in I_{n−1}(≤, >, ≠).

Let f = (f_{1}, f_{2}, …, f_{k}) be an inversion sequence that avoids (−, >, −) (that is, f is an inversion sequence with weakly increasing entries, as seen in Section 2.14). Recall that |I_{n}(−, >, −)| = C_{n}. Then any inversion sequence in case 2 is of the form (0, 0, …, f_{1}, t − 1, σ_{t−1}(f_{2}, f_{3}, …, f_{k})), where t − 1 occurs in position t (and is therefore maximal). Notice that, in order for this construction to fall in case 2, f must have length greater than zero. It follows that the generating function for case 2 is \frac{x}{1−x} · (C(x) − 1).

Finally, case 3 consists of all inversion sequences of the form e′.(j − 1).(f + j − 1) where e′ ∈ (I_{j−1}(≤, >, ≠)\{(0, 0, …, 0)}) and (f + j − 1) denotes the sequence obtained by adding j − 1 to each entry of some f ∈ I_{n−t}(−, >, −). The generating function for this case is (A(x) − \frac{x}{1−x}) · x · C(x).

From these three disjoint cases, we have

A(x) = 1 + xA(x) + \frac{x}{1 − x} · (C(x) − 1) + (A(x) − \frac{x}{1 − x}) · x · C(x).

Solving for A(x) gives

A(x) = \frac{1 − 2x}{(1 − x)(1 − x − xC(x))}

By substituting the known expression for C(x), and through conjugation and algebraic rearrangement, the result follows.

Theorem 58. |I_{n}(≤, >, ≠)| = C_{n+1} − ∑_{i=1}^{n} C_{i}, where C_{n} = \frac{1}{n+1} \binom{2n}{n}.

Proof. Let B_{n} = C_{n+1} − ∑_{i=1}^{n} C_{i}. Then ∑_{n≥0} B_{n}x^{n} = \frac{C(x)−1}{x} − \frac{C(x)−1}{1−x}. By substituting C(x) = \frac{1−\sqrt{1−4x}}{2x} and simplifying, it follows that A(x) = B(x) and therefore B_{n} = |I_{n}(≤, > , ≠)|.

3.1.2 Class 1016: Avoiding e_{i} > e_{j} and e_{i} ≠ e_{k}

We can show that the counting sequence for |I_{n}(>, −, ≠)| (A279560) is as follows. We omit the details since we hope to find a simpler formula and nicer explanation.

|I_{n}(>, −, ≠)| = \binom{2(n − 1)}{n − 1} + ∑_{k=2}^{n−2} ∑_{i=1}^{k−1} ∑_{u=1}^{i} ∑_{d=0}^{u−1} \frac{i − d + 1}{i + 1}\binom{i + d}{d}.

3.1.3 1079(A,B): sum of binomial coefficients

The sequences in I_{n}(>, ≠, −) (Class 1079A, A279561)) have a nice unimodality characterization. They are the inversion sequences e ∈ I_{n} satisfying for some t:

e_{1} ≤ e_{2} ≤ … ≤ e_{t} ≥ e_{t+1} = e_{t+2} = … = e_{n}.

From this characterization, we can show the following.

Theorem 59. |I_{n}(>, ≠, −)| = 1 + ∑_{i=1}^{n−1} \binom{2i}{i−1}.

Additionally, we conjecture that I_{n}(<, >, ≠) (Class 1079B) is Wilf-equivalent, but have not proven this.

3.1.4 4306A,B: I_{n}(210), I_{n}(201)

The sets I_{n}(−, <, >) = I_{n}(201) and I_{n}(>, >, −) = I_{n}(210) were shown to be Wilf-equivalent by Corteel, et al. [13] via a bijection, which we made use of in Section 2.27. An alternate proof of this fact was discovered by Mansour and Shattuck [23]. A recurrence to compute |I_{n}(201)| was also derived in [13] .

3.2 Wilf-equivalence results

In the remainder of the section we show that the bijection α described in (10) of Section 2.27 proves Wilf-equivalence of all of the following pairs of patterns: 663A,B; 746A,B; 1833A,B; and 1953A,B.

3.2.1 Class 1953A: Avoiding e_{j} > e_{k} and e_{i} > e_{k}, and Class 1953B: Avoiding e_{i} ≠ e_{j} ≥ e_{k} and e_{i} > e_{k}

Theorem 60. The patterns (−, >, >) and (≠, ≥, >), defining classes 1953A and 1953B respectively, are Wilf-equivalent.

Proof. The inversion sequences in classes 1953A and 1953B are those in I_{n}(110, 210, 120) and I_{n}(100, 210, 120), respectively. Notice that these are the inversion sequences in I_{n}(110, 210) (class 2958C) and I_{n}(100, 210) (class 2958A), respectively, that avoid 120. So it suffices to show that both α : I_{n}(110, 210) → I_{n}(100, 210) and β = α^{−1} preserves 120-avoidance.

Suppose e ∈ I_{n}(110, 210) avoids 120, but for e′ = α(e) there exist i < j < k such that e′_{i} < e′_{j} > e′_{k} and e′_{i} > e′_{k}. By (12), e′_{k} = e_{k}. Notice that we cannot have both e′_{i} = e_{i} and e′_{j} = e_{j}, since this would create a 120 in e.

Suppose first that e′_{j} = e_{j}. Since e avoids 120, e′_{i} ≠ e_{i} so, by definition of α, there is an s ∈ [i − 1] such that e_{s} = e′_{i}. But then e_{s}e_{j}e_{k} forms a 120 in e.

So, assume that e′_{i} = e_{i}. Then, since e avoids 120, e′_{j} ≠ e_{j}. So, there must be a t ∈ [j − 1] such that e_{t} = e′_{j}. If i < t < k then e_{i}e_{t}e_{k} is a 120 in e. Otherwise, t < i < k and e_{t}e_{i}e_{k} is a 210 in e, which is impossible.

Finally, if both e′_{i} ≠ e_{i} and e′_{j} ≠ e_{j}, then let s and t be as above. If s < t then e_{s}e_{t}e_{k} forms a 102 in e. Otherwise, e_{t}e_{s}e_{k} forms a 210 in e. Both cases lead to a contradiction.

If both e′_{i} ≠ e_{i} and e′_{j} ≠ e_{j}, then let s ∈ [i − 1] and j ∈ [j − 1] be indices such that e′_{i} = e_{s} and e′_{j} = e_{t}. Since e′_{i} = max{e_{1}, e_{2}, …, e_{i}} and e′_{j} = max{e_{1}, e_{2}, …, e_{j}}, and we have e′_{i} < e′_{j}, it must be the case the e_{s} < e_{t} and s < t. Therefore e_{s}e_{t}e_{k} is an occurrence of 120 in e, giving a contradiction.

It follows that α preserves 120-avoidance. Showing that β preserves 120-avoidance is similar.

3.2.2 Class 1833A: Avoiding e_{j} ≠ e_{k} and e_{i} > e_{k}, and Class 1833B: Avoiding e_{i} ≠ e_{j} and e_{i} > e_{k}

Theorem 61. The patterns (−, ≠, >) and (≠, −, >), defining classes 1833A and 1833B respectively, are Wilf-equivalent.

Proof. The inversion sequences in classes 1833A and 1833B are those in I_{n}(110, 210, 120, 201) and I_{n}(100, 210, 120, 201), respectively. It was shown in Section 2.27 that the bijection α : I_{n}(110, 210) → I_{n}(100, 210) preserves 201-avoidance, as does its inverse β. It follows from Theorem 60 that α and β preserves 120-avoidance as well. So α(I_{n}(−, ≠, >)) = I_{n}(≠ , −, >).

3.2.3 Class 746A: Avoiding e_{j} > e_{k} and e_{i} ≥ e_{k}, and Class 746B: Avoiding e_{i} ≠ e_{j} ≥ e_{k} and e_{i} ≥ e_{k}

Theorem 62. The patterns (−, >, ≥) and (≠, ≥, ≥), defining classes 746A and 746B respectively, are Wilf-equivalent.

Proof. The inversion sequences in classes 746A and 746B are those in I_{n}(110, 210, 120, 010) and I_{n}(100, 210, 120, 010), respectively. These are, in turn, the inversion sequences in I_{n}(110, 210, 120) (class 1953A) and I_{n}(100, 210, 120) (class 1953B), respectively, that avoid 010. By Theorem 60, α : I_{n}(110, 210) → I_{n}(100, 210) and α^{−1} = β preserve 120-avoidance. So it suffices to show that both α : I_{n}(110, 210) → I_{n}(100, 210) and α^{−1} = β preserves 010avoidance.

Suppose e ∈ I_{n}(110, 210) avoids 010, but for e′ = α(e) there exist i < j < k such that e′_{i} < e′_{j} > e′_{k} and e′_{i} = e′_{k}. By (12), e′_{k} = e_{k}. Since e avoids 010, it follows that we cannot have both e′_{i} = e_{i} and e′_{j} = e_{j}.

Suppose first that e′_{j} = e_{j}. Since e avoids 010, e′_{i} ≠ e_{i} so, by definition of α there is an s ∈ [i − 1] such that e_{s} = e′_{i}. But then e_{s}e_{j}e_{k} forms a 010 in e.

So, assume that e′_{i} = e_{i}. Then, since e avoids 010, e′_{j} ≠ e_{j}. So, there must be a t ∈ [j − 1] such that e_{t} = e′_{j}. If i < t < k then e_{i}e_{t}e_{k} is a 010 in e. Otherwise, t < i < k and e_{t}e_{i}e_{k} is a 100 in e, which is impossible.

If both e′_{i} ≠ e_{i} and e′_{j} ≠ e_{j}, then let s ∈ [i − 1] and t ∈ [j − 1] be indices such that e′_{i} = e_{s} and e′_{j} = e_{t}. Since e′_{i} = max{e_{1}, e_{2}, …, e_{i}} and e′_{j} = max{e_{1}, e_{2}, …, e_{j}}, and we have e′_{i} < e′_{j}, it must be the case the e_{s} < e_{t} and s < t. Additionally, e_{s} = e′_{i} = e′_{k} = e_{k}. Therefore e_{s}e_{t}e_{k} is an occurrence of 010 in e, giving a contradiction.

It follows that α preserves 010-avoidance. Showing that β preserves 010-avoidance is similar.

3.2.4 Class 663A: Avoiding e_{j} ≠ e_{k} and e_{i} ≥ e_{k}, and Class 663B: Avoiding e_{i} ≠ e_{j} and e_{i} ≥ e_{k}

Theorem 63. The patterns (−, ≠, ≥) and (≠, −, ≥), defining classes 663A and 6633B respectively, are Wilf-equivalent.

Proof. The inversion sequences in classes 663A and 663B are those in I_{n}(110, 210, 120, 201,

010) and I_{n}(100, 210, 120, 201, 010), respectively. It was shown in Section 2.27 that the bijection α : I_{n}(110, 210) → I_{n}(100, 210) preserves 201-avoidance, as does its inverse. It follows from Theorem 60 that α, β preserve 120-avoidance and from Theorem 62 that they preserve 010-avoidance as well. So α(I_{n}(−, ≠, ≥)) = I_{n}(≠, −, ≥).

4 Concluding remarks

The results in this work demonstrate that inversion sequences avoiding a triple of relations have connections to a vast array of pattern-avoiding classes and combinatorial sequences. Moreoever, as a pattern to avoid, a triple of relations can be more expressive than a single word of length 3, even though it is always equivalent to an avoidance set of words of length 3.

On the other hand, I_{n}(001, 210) is not the avoidance set of any triple of relations considered in this paper. In ongoing work, we construct and examine the partially ordered set whose elements are the avoidance sets I_{n}(S), ordered by inclusion, where

S ⊆ {000, 001, 010, 100, 011, 101, 110, 123, 132, 213, 231, 312, 321}.

Several interesting questions remain for future work, such those highlighted in Table 2 with a “no” in column 3. For instance, is I_{n}(>, −, >) equinumerous with S_{n}(4231, 42513) and is I_{n}(>, −, ≤) equinumerous with S_{n}(4123, 4132, 4213)? Are I_{n}(=, ≥, −) and I_{n}(≥, =, −) counted by the Bell numbers?

Another fascinating open question is whether there is a bijective mapping to relate the Baxter permutations in S_{n} to I_{n}(≥, ≥, >). There are also a number of lingering open enumeration problems: can enumeration formulas be found for some of the avoidance sets in Table 3, such as I_{n}(010), I_{n}(100), I_{n}(120), or I_{n}(201) = I_{n}(210)?

Pattern avoidance can be studied in more general s-inversion sequences. For a given sequence s = (s_{1}, s_{2}, …, s_{n}) of positive integers, the s-inversion sequences I_{n}^{(s)} are defined by

I_{n}^{(s)} = {(e_{1}, e_{2}, …, e_{n}) ∈ Z^{n} | 0 ≤ e_{i} < s_{i}, 1 ≤ i ≤ n}.

When s = (1, 2, …, n), these are the usual inversion sequences. For s = (2, 4, …, 2n), there is a statistics-preserving bijection between I_{n}^{(s)} and signed permutations of [n]. See [26] for other interesting families of s-inversion sequences, and for an overview of their combinatorial and geometric relationships to s-lecture hall partitions and cones.

5 Acknowledgments

Thanks to Sylvie Corteel for helpful discussions about several of the sequences herein. Thanks to Michael Weselcouch for independently verifying our computations of the avoidance sequences for the 343 patterns. Thanks to the referee of this paper for a careful reading of the manuscript and many helpful suggestions. Thanks to Michael Albert for making his PermLab software freely available [2]. Thanks to the Simons Foundation for Collaboration Grant No. 244963 to the second author which supported the travel of the first author for collaboration. Some of this material is based upon work supported by the National Science Foundation under Grant No. 1440140, while the second author was in residence at the Mathematical Sciences Research Institute in Berkeley, California, during the fall semester of 2017.

We once again extend sincere thanks to Neil Sloane and the OEIS Foundation, Inc. The On-Line Encyclopedia of Integer Sequences [15] was an invaluable resource for this project.

References

[1] M. H. Albert, R. E. L. Aldred, M. D. Atkinson, H. P. van Ditmarsch, C. C. Handley, and D. A. Holton, Restricted permutations and queue jumping, Discrete Math. 287 (2004), 129–133.

[2] Michael Albert, Permlab: Software for permutation patterns, 2012.

http://www.cs.otago.ac.nz/staffpriv/malbert/permlab.php.

[3] Michael H. Albert, Cheyne Hamburger, Jay Pantone, Nathaniel Shar, and Vincent Vatter, Generating permutations with restricted containers, (2015).

http://arxiv.org/pdf/1510.00269.pdf.

[4] Sara C. Billey, William Jockusch, and Richard P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), 345–374.

[5] Mireille Bousquet-Mélou and Steve Butler, Forest-like permutations, Ann. Comb. 11 (2007), 335–354.

[6] Mireille Bousquet-Mélou and Guoce Xin, On partitions avoiding 3-crossings, Sém. Lothar. Combin. 54 (2005/07), Art. B54e.

[7] Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, and Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence, (2017).

https://arxiv.org/pdf/1702.04529.pdf.

[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-index.php?page=Papers+and+Talks/uis-chigago-talk-5.pdf.

[9] David Callan, A combinatorial interpretation of the eigensequence for composition, J. Integer Sequences 9 (2006), Article 06.1.4.

[10] David Callan, A bijection to count (1-23-4)-avoiding permutations, preprint, 2010.

    Available at http://arxiv.org/abs/1008.2375.

[11] David Callan, The number of ¯2¯1542-avoiding permutations, preprint, 2011. Available

    at http://arxiv.org/abs/1111.3088.

[12] F. R. K. Chung, R. L. Graham, V. E. Hoggatt, Jr., and M. Kleiman, The number of Baxter permutations, J. Combin. Theory Ser. A 24 (1978), 382–394.

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

[14] Shishuo Fu, Zhicong Lin, and Jiang Zeng, Two new unimodal descent polynomials,

    2015. http://arxiv.org/abs/1507.05184.

[15] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2011. Available

    at http://oeis.org.

[16] Dongsu Kim and Zhicong Lin, Refined restricted inversion sequences, preprint, 2017.

    Available at https://arxiv.org/pdf/1706.07208.pdf.

[17] Sergey Kitaev, Patterns in Permutations and Words, Monographs in Theoretical Computer Science, Springer, 2011.

[18] Sergey Kitaev and Jeffrey Remmel, Quadrant marked mesh patterns, J. Integer Sequences 15 (2012), Article 12.4.7.

[19] Darla Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discrete Math. 218 (2000), 121–130.

[20] Alain Lascoux and Marcel-Paul Schützenberger, Schubert polynomials and the Littlewood-Richardson rule, Lett. Math. Phys. 10 (1985), 111–124.

[21] Zhicong Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions,

    preprint, 2017. Available at https://arxiv.org/pdf/1706.07213.pdf.

[22] Percy A. MacMahon, Combinatory Analysis, Chelsea Publishing Co., New York, 1960.

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

[24] Megan Martinez and Carla Savage, Patterns in inversion sequences II: Inversion sequences avoiding triples of relations [v1], preprint, 2016. Available at

    https://arxiv.org/pdf/1609.08106v1.pdf.

[25] T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, J. Comb. 6 (2015), 145–178.

[26] Carla D. Savage, The mathematics of lecture hall partitions, J. Combin. Theory Ser. A 144 (2016), 443–475.

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

[28] Richard P. Stanley, Enumerative combinatorics. Vol. 1, Vol. 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, 1997.

[29] Sheila Sundaram, The homology of partitions with an even number of blocks, J. Algebraic Combin. 4 (1995), 69–92.

[30] Bridget Eileen Tenner, Pattern avoidance and the Bruhat order, J. Combin. Theory Ser. A 114 (2007), 888–905.

[31] Sherry H. F. Yan, Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions, preprint, 2017. Available at https://arxiv.org/pdf/1707.02408.pdf.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A19. Keywords: inversion sequence, pattern avoidance, triple of relations, Catalan number, Schröder number, Baxter number.

(Concerned with sequences \underline{A000045}, \underline{A000071}, \underline{A000079}, \underline{A000108}, \underline{A000110}, \underline{A000111}, \underline{A000124}, \underline{A000325}, \underline{A000984}, \underline{A001181}, \underline{A001519}, \underline{A004275}, \underline{A005183}, \underline{A006318}, \underline{A009766}, \underline{A033321}, \underline{A034943}, \underline{A047969}, \underline{A047970}, \underline{A049125}, \underline{A071356}, \underline{A088921}, \underline{A090981}, \underline{A091156}, \underline{A098746}, \underline{A106228}, \underline{A108307}, \underline{A108759}, \underline{A113227}, \underline{A117106}, \underline{A124323}, \underline{A166073}, \underline{A175124}, \underline{A200753}, \underline{A212198}, \underline{A229046}, \underline{A263777}, \underline{A263778}, \underline{A263779}, \underline{A263780}, \underline{A279544}, \underline{A279551}, \underline{A279552}, \underline{A279553}, \underline{A279554}, \underline{A279555}, \underline{A279556}, \underline{A279557}, \underline{A279558}, \underline{A279559}, \underline{A279560}, \underline{A279561}, \underline{A279562}, \underline{A279563}, \underline{A279564}, \underline{A279565}, \underline{A279566}, \underline{A279567}, \underline{A279568}, \underline{A279569}, \underline{A279570}, \underline{A279571}, \underline{A279572}, and \underline{A279573}.)

Received May 2 2017; revised version received January 5 2018; January 21 2018. Published in Journal of Integer Sequences, February 23 2018.

Return to Journal of Integer Sequences home page.