# Patterns in inversion sequences I.

Permutations that avoid given patterns have been studied in great depth for their connections to other fields of mathematics, computer science, and biology. From a combinatorial perspective, permutation patterns have served as a unifying interpretation that relates a vast array of combinatorial structures. In this paper, we introduce the notion of patterns in inversion sequences. A sequence ([e.sub.1], [e.sub.2],[??] , en) is an inversion sequence if 0 [less than or equal to] a < i for all i [member of] [n]. Inversion sequences of length n are in bijection with permutations of length n; an inversion sequence can be obtained from any permutation [pi] = [[pi].sub.1][[pi].sub.2] .. . [[pi].sub.n] by setting [e.sub.i] = |{j | j < i and [[pi].sub.j] > [[pi].sub.i]}|. This correspondence makes it a natural extension to study patterns in inversion sequences much in the same way that patterns have been studied in permutations. This paper, the first of two on patterns in inversion sequences, focuses on the enumeration of inversion sequences that avoid words of length three. Our results connect patterns in inversion sequences to a number of well-known numerical sequences including Fibonacci numbers, Bell numbers, Schroder numbers, and Euler up/down numbers.Keywords: inversion sequences, pattern avoidance, enumeration, Schroder numbers

1 Overview

A permutation [pi] = [[pi].sub.1][[pi].sub.2][??] [[pi].sub.n] [member of] [S.sub.n] is said to contain a pattern [sigma] = [[sigma].sub.1][[sigma].sub.2][??] [[sigma].sub.k] [member of] [S.sub.k] if there exist indices [i.sub.1] < [i.sub.2] < [??] < [i.sub.k] such that for every a, b [member of] {1, 2,[??] , k}, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if [[sigma].sub.a] < [[sigma].sub.b]. Otherwise, [pi] is said to avoid the pattern [sigma]. Let [S.sub.n]([sigma]) = {[pi] [member of] [S.sub.n] | [pi] avoids [sigma]}. Given any [sigma] [member of] [S.sub.k], the avoidance sequence of [sigma] is the integer sequence,

|[S.sub.1]([sigma])|, |[S.sub.2]([sigma])|, |[S.sub.3]([sigma])|,[??] .

The avoidance sequences for various [sigma] count a great number of well-known combinatorial structures. As a result, the study of permutation patterns provides a unifying interpretation for a number of disparate discrete structures. Early work of MacMahon [15] enumerating permutations avoiding 123 and of Knuth [12, 13] on 231 and stack-sortable permutations established by 1973 that for every [sigma] [member of] [S.sub.3], [S.sub.n]([sigma]) is counted by the Catalan numbers. In 1985 Simion and Schmidt published the first systematic study of pattern avoidance in permutations [23]. Thirty years later, there is a rich body of work demonstrating the connections between pattern avoidance and many areas of mathematics and computation. See, for example, the survey of Kitaev [11].

Recently, the s-inversion sequences, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], defined for a positive integer sequence s = ([s.sub.1],[??] , [s.sub.n]) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

were introduced in [20] to enumerate certain families of partitions via Ehrhart theory. For a variety of sequences s, natural statistics on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have the same distribution as natural statistics on other equinumerous combinatorial families, a phenomenon that was used to settle an open question about Coxeter groups in [21].

The words of length n over the alphabet {0, 1,[??] , k - 1} can be viewed as the inversion sequences [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When s = (1, 2,[??] ,n), the s-inversion sequences [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have been used in various ways to encode permutations [S.sub.n]. For example, the map [theta]([pi]): [S.sub.n] [right arrow] [I.sub.n] defined for [pi] = [[pi].sub.1] [??] [[pi].sub.n] [member of] [S.sub.n] by [theta]([pi]) = ([e.sub.1],[e.sub.2],[??] , [e.sub.n]), where [e.sub.i] = |{j | j < i and [e.sub.j] > [e.sub.i]}|, is a bijection with several nice properties. These connections to words and permutations make it natural to study pattern avoidance in inversion sequences in the same way that pattern avoidance has been studied in words and permutations.

Given a word p = [p.sub.1][p.sub.2] [??] [p.sub.k] [member of] {0,1,[??] , k = 1[}.sup.k], define the reduction of p to be the word obtained by replacing the ith smallest entries of p with i - 1. For instance, the reduction of 3052662 is 2031441. We say that an inversion sequence e [member of] [I.sub.n] contains the pattern p, if there exist some indices [i.sub.1] < [i.sub.2] < [??] < [i.sub.k] such that the reduction of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is p. Otherwise, e is said to avoid p. Let [I.sub.n] (p) = {e [member of] [I.sub.n] | e avoids p}. The avoidance sequence of p is the integer sequence

|[I.sub.1](p)|, |[I.sub.2](p)|, |[I.sub.3](p)|,[??] .

Our focus in this paper is a study of inversion sequences avoiding a three-letter word p. We discover a surprisingly rich collection of enumerative results, as well as intriguing conjectures. There will be several examples where pattern-avoiding inversion sequences provide more natural models of combinatorial sequences than previously known.

This paper is one of the firs[t.sup.(i)] systematic studies of pattern avoidance in inversion sequences, although in [7] Duncan and Steingrlmsson considered pattern avoidance in ascent sequences, introduced in [3], and obtained interesting enumerative results. (An ascent sequence is an integer sequence ([e.sub.1], [e.sub.2],[??] , [e.sub.n]) in which [e.sub.1] = 0 and [e.sub.i] is a nonnegative integer at most one more than the number of ascents in the sequences ([e.sub.1]; [e.sub.2],[??] , [e.sub.i-1]). The ascent sequences of length n thus form a subset of [I.sub.n]) Some of the open questions posed in [7] were settled by Mansour and Shattuck in [17].

Our approach in this paper is combinatorial. For each pattern p, we first observe an alternate characterization of the p-avoiding inversion sequences. For example: the inversion sequences avoiding 011 are those whose positive elements are distinct (see Section 3.3). We then use the observation to define the structure of the p-avoiding inversion sequences and relate them to equinumerous combinatorial families via bijections, recurrences or generating functions. In the process, we discover and prove refinements via correspondences between natural statistics. For example, the number of 011-avoiding inversion sequences in [I.sub.n] with k zeros is equal to the number of partitions of an n-element set into k nonempty blocks (Section 3.3).

In Section 2 we consider inversion sequences [I.sub.n] avoiding a given 3-letter permutation of {0, 1, 2}. We show that the number of inversion sequences avoiding 012 is given by the odd-indexed Fibonacci numbers and that the inversion sequences avoiding 021 are counted by the large Schroder numbers. We prove that the patterns 201 and 210 are Wilf equivalent, i.e. that they have the same avoidance sequence. This sequence does not appear in the OEIS, but we derive a recurrence for it. Enumerative results for the patterns 012, 021, 201, 102, and 210 also appear in [16], where Mansour and Shattuck additionally prove that the number of inversion sequences avoiding 102 is given by the sequence A200753 in the On-Line Encyclopedia of Integer Sequences (OEIS) [10]. The number of inversion sequences avoiding 120 does not appear in the OEIS and counting them remains an open problem.

In Section 3 we consider inversion sequences [I.sub.n] avoiding a given 3-letter pattern with repeated symbols. We prove that the inversion sequences avoiding 000 are counted by the Euler up/down numbers. We show that the inversion sequences avoiding 001 are counted by powers of two, and those avoiding 011 are counted by the Bell numbers. Additionally, we prove that the number of inversion sequences avoiding 101 is the same as the number avoiding 110 and this is the same as the number of permutations avoiding the vincular pattern 1-23-4. The avoidance sequence for the pattern 010 does not appear in the OEIS nor does the number of inversion sequences avoiding 100. Counting either of these sets is an open problem.

In Section 4, we return to 021-avoiding inversion sequences. We examine the correspondence between [I.sub.n](021) and Schroder (n - 1)-paths, and between [I.sub.n](021) and certain binary trees by introducing two further bijections. Eachbijection succeeds in relating a variety of different statistics in inversion sequences and those combinatorial families. Surprisingly, the ascent statistic in [I.sub.n] (021) is symmetric, and we prove this by defining a bijection between [I.sub.n](021) and a tree structure that is known to be counted by the Schroder numbers. Section 4 is a testament to the rich combinatorial structure that can be uncovered when examining a class of pattern-avoiding inversion sequences in-depth.

The results on inversion sequences avoiding permutations and words of length 3 are summarized in Table 1. In the last column of the table, we use |[I.sub.7](p) as an identifier for the avoidance sequence of [I.sub.n](p).

This paper is the first part of a larger study on patterns in inversion sequences. In subsequent work, we consider a generalization of pattern-avoiding inversion sequences that includes many more surprising results and conjectures.

Throughoutthis paper, we let [n] = {1, 2,[??] , n}. For an inversion sequence e = ([e.sub.i], [e.sub.2],[??] , [e.sub.n]) [member of] [I.sub.n], let [[sigma].sub.t](e) = ([e'.sub.1]; [e'.sub.2],[??] , [e'.sub.n]) where [e'.sub.i] = 0 if [e.sub.i] = 0 and otherwise [e'.sub.i] = [e.sub.i] +1 (we allow for negative t). This operation will also be applied to substrings of an inversion sequence.

We use concatenation to add an element to the beginning or end of an inversion sequence: 0 * e is the inversion sequence (0, [e.sub.1]; [e.sub.2],[??] , [e.sub.n]) andfor 0 [less than or equal to] i [less than or equal to] n, e * i is the inversion sequence ([e.sub.1]; [e.sub.2],[??] , [e.sub.n], i).

2 Inversion sequences avoiding permutations

2.1 Avoiding 012: [F.sub.2n]-i] and Boolean permutations

Let [F.sub.n] denote the nth Fibonacci number, where [F.sub.0] = 0, [F.sub.1] = 1 and for n [greater than or equal to] 2, [F.sub.n] = [F.sub.n-1] + [F.sub.n-2]. Note that [a.sub.n] = [F.sub.2n-1] satisfies the recurrence [a.sub.n] = 3[a.sub.n-1] - [a.sub.n-2], with initial conditions [a.sub.1] = 1, [av2] = 2.

Permutations avoiding both 321 and 3412 are known as Boolean permutations [18, 25] and are counted by [F.sub.2n-1]. In this section we show that [I.sub.n] (012) is the number of Boolean permutations of [n].

Observation 1 The inversion sequences avoiding 012 are those whose positive elements form a weakly decreasing sequence.

Theorem 1 |[I.sub.n] (012)| = [F.sub.2n-1].

Proof: By Observation 1, if e [member of] [I.sub.n-1] (012), the following are all in [I.sub.n](012): e * 0, e 1, and 0 * [[sigma].sub.1](e). Every element in [I.sub.n](012) arises from an element of [I.sub.n-1](012) in at least one of these three ways, but certain elements are counted twice, namely those of the form 0 * x * 0 where x [member of] [I.sub.n-2](012). Thus |[I.sub.n](012)| satisfies the recurrence [a.sub.n] = 3[a.sub.n-1] - [a.sub.n-2], with initial conditions [a.sub.1] = 1, [a.sub.2] = 2. This is the same recurrence satisfied by [F.sub.2n-1].

In view of the connection between Boolean permutations and Coxeter groups highlighted in the recent paper of Petersen and Tenner [18], it would be nice to have a simple bijection encoding them as 012-avoiding inversion sequences.

2.2 Avoiding 021: the large Schroder numbers

A Schroder n-path is a path in the plane from (0,0) to (2n, 0), never going below the x-axis, using only the steps (1,1) (up), (1, -1) (down) and (2,0) (flat). For example, using U, D, and F for up, down, and flat steps, respectively, the Schroder 14-path p = UUDUFUDUFDDDUUDUDDUUUFDDD is shown in Figure 1.

[FIGURE 1 OMITTED]

Let [R.sub.n] denote the set of Schroder n-paths and let [r.sub.n] = |[R.sub.n]|. It is well known that the generating function for [r.sub.n] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

To relate Schroder paths to inversion sequences, first note that the 021-avoiding inversion sequences have the following simple characterization.

Observation 2 An inversion sequence avoids 021 if and only if its positive entries are weakly increasing.

Using this characterization, we show that the elements of [I.sub.n](021) are in bijection with the Schroder paths in [R.sub.n-1].

Theorem 2 Forn [greater than or equal to] 1, |[I.sub.n] (021) | = [r.sub.n-1].

Proof: Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We show that E(x) satisfies

E(x) = x + xE(x) + [E.sup.2](x), (2)

which has solution

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and the result will follow from (1).

Given e [member of] [I.sub.n](021), consider the last position j + 1 suchthat [e.sub.j+1] attains its maximal value j. If j =0, then either e = (0) or e = 0 * e' for some e' [member of] [I.sub.n-1] (021). This accounts for the x + xE(x) in (2). We show that the e for which j > 0 are counted by [E.sup.2] (x).

If j > 0, then ([e.sub.1],[??] , [e.sub.j]) [member of] [I.sub.j] (021). As for ([e.sub.j+2],[??] , [e.sub.n]), we know that for i = 2,[??] , n - j, by Observation 2 and by choice of j, either [e.sub.j+i] =0 or

j less than or equal to] [e.sub.j+i] < j + i - 1.

It follows that subtracting j -1 from the positive entries of ([e.sub.j]+2],[??] , [e.sub.n]) and adding a 0 to the beginning of the sequence gives an element of [I.sub.n-j] (021). Conversely, for any sequences ([e.sub.1],[??] , [e.sub.j]) [member of] [I.sub.j] (021) and f [member of] [I.sub.n-j] (021), if we add j - 1 to all the positive elements of f and remove the initial 0 of f, we can append the result to ([e.sub.1];[??] , [e.sub.j], j) to obtain an element of [I.sub.n](021) in which j + 1 is the last position whose entry attains its maximal value.

We recall the operation [[sigma].sub.k] defined in Section 1 to facilitate describing a bijection. If e is an inversion sequence, and ([e.sub.i]; [e.sub.i+1],[??] , [e.sub.j]) is a substring of e in which all positive entries are larger than k, then [[sigma].sub.-k] ([e.sub.i]; [e.sub.i+1],[??] , [e.sub.j]) is the sequence obtained by subtracting k from the positive entries of ([e.sub.i], [e.sub.i+1],[??] , [e.sub.j]).

The proof of Theorem 2 gives rise to the following recursive bijection [rho] from [I.sub.n](021) to Schroder (n - 1)-paths. For e [member of] [I.sub.n](021), let j + 1 be the last position such that [e.sub.j+1] attains its maximal value j. Set [rho](0) to be the empty path. Then the Schroder path p - [rho](e) is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For example, p - [rho](0,1,0,1,0,2, 5,7, 7,7, 9,0,10,11,12) is the Schroder 14-path shown in Figure 1. By definition, [rho] gives the following result.

Theorem 3 For n [greater than or equal to] 1, the number of 021 -avoiding inversion sequences of length n with k maximal elements is the same as the number of Schroder (n - 1) -paths with k--1 initial up steps.

The number of Schroder (n - 1)-paths with k initial up steps is counted by sequence A132372 in the OEIS [10].

Ira Gessel considered in [9] the generating function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where flat (p) is the number of flat steps in a Schroder path p. He showed that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Similarly define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where zeros(e) is the number of zeros in the inversion sequence e. Following the proof of Theorem 2, we have

E(x, z) - xz + xzE(x, z) + [E.sup.2](x, z)/z.

Solving, and comparing to (3) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This proves the following.

Theorem 4 For n [greater than or equal to] 1, the number of 021 -avoiding inversion sequences of length n with k zeros is the same as the number of Schroder (n - 1) -paths with k - 1 flat steps.

Note that the number of Schroder (n - 1)-paths with k - 1 flat steps is equal to the number of Schroder (n - 1)-paths with k - 1 peaks (where a peak is an occurrence of UD). This can be seen by applying an involution that replaces every UD with F and every F with UD. This gives us the following.

Corollary 1 For n [greater than or equal to] 1, the number of 021 -avoiding inversion sequences of length n with k zeros is the same as the number of Schroder (n - 1) -paths with k - 1 peaks.

In Section 4 we provide a second bijection relating different statistics in 021-avoiding inversion sequences and Schroder paths. We also show a correspondence with certain trees counted by the Schroder numbers and use this to prove that the ascent statistic on 021-avoiding inversion sequences is symmetric.

2.3 The patterns 201 and 210

In this section we prove that the patterns 201 and 210 are Wilf equivalent on inversion sequences. This has also been shown in [16]. The avoidance sequence for these patterns did not appear in the OEIS, (it has now been assigned A263777) but we derive a recurrence to compute it.

For e [member of] [I.sub.n], call position j a weak left-to-right maximum if [e.sub.i] [less than or equal to] [e.sub.j] for all 1 [less than or equal to] i < j.

Observation 3 The 210 -avoiding inversion sequences are precisely those that can be partitioned into two weakly increasing subsequences.

Proof: Suppose e has such a partition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If there exists i < j < k such that [e.sub.i] > [e.sub.j] > [e.sub.k], then no two of i, j, k can both be in {[a.sub.1],[??] , [a.sub.t]} or both be in {[b.sub.1];[??] , [b.sub.n-t]}, so e avoids 210. Conversely, if e avoids 210, let a - ([a.sub.1],[??] , [a.sub.t]) be the sequence of weak left-to-right maxima of e. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII. Consider i,j G {[a.sub.1],[??] ,[a.sub.t]} where i < j. The fact that [e.sub.i] is not a weak left-to-right maxima implies there exists some [e.sub.s] such that s < i and [e.sub.s] > [e.sub.i]. Thus to avoid 210, we must have [e.sub.i] [less than or equal to] [e.sub.j].

Observation 4 Let ([e.sub.1], [e.sub.2],[??] , [e.sub.n]) [member of] [I.sub.n]. Additionally, for any i [member of] [n], let [M.sub.i] - max([e.sub.1], [e.sub.2],[??] , [e.sub.i-1]). Then e [member of] [I.sub.n](201) if and only if for every i [member of] [n], the entry [e.sub.i] is a weak left-to-right maximum, or for everyj > i, we have [e.sub.j] < [e.sub.i] or [e.sub.j] > [M.sub.i].

Proof: Let e [member of] [I.sub.n] satisfy the conditions of Observation 4 and, to obtain a contradiction, assume there exist i < j < k such that [e.sub.i][e.sub.j][e.sub.k] forms a 201 pattern (i.e. [e.sub.j] < [e.sub.k] < [e.sub.i]). Notice that [M.sub.j] - max{[e.sub.1],[e.sub.2],[??] ,[e.sub.j-1]} [greater than or equal to] [e.sub.i]. It follows that [M.sub.j] > [e.sub.k] > [e.sub.j], which contradictions our assumption.

Conversely, if ([e.sub.1], [e.sub.2],[??] , [e.sub.n]) [member of] [I.sub.n](201), consider any [e.sub.i]. If [e.sub.i] is not a weak left-to-right maximum, then there exists some maximum value [M.sub.i] - [e.sub.s] such that s < i and [e.sub.s] > [e.sub.i]. Therefore, in order to avoid a 201 pattern, any [e.sub.j] where j > i must have [e.sub.i] [greater than or equal to] [e.sub.j] or [e.sub.j] [greater than or equal to] [M.sub.i] - [e.sub.s].

Theorem 5 Forn [less than or equal to] 1, |[I.sub.n](210)| = |[I.sub.n](201)|.

Proof: We exhibit a bijection based on the characterizations in Observations 3 and 4.

Given e [member of] [I.sub.n](210), define f [member of] [I.sub.n](201) as follows. Let [e.sub.a1] [less than or equal to] [e.sub.a2] [less than or equal to] [??] [less than or equal to] [e.sub.at] be the sequence of weak left-to-right maxima of e and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII be the subsequence of remaining elements of e.

for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII, we extract an element of the multiset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and assign it to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By definition, f will satisfy the characterization property in Observation 4 of [I.sub.n](210).

In order to get a recurrence that allows us to compute a few terms of |[I.sub.n](210)| = |[I.sub.n] (201) |, we define two statistics, top and bottom, on e [member of] [I.sub.n](210) based on the decomposition of e described in Observation 3. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the sequence of weak left-to-right maxima of e and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the subsequence of remaining elements of e. then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If e is weakly increasing, then t = n so we define bottom (e) = -1.

Theorem 6 Let [T.sub.n,a,b] be the number of e [member of] [I.sub.n](201) with top (e) = a and bottom(e) = b. then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with initial conditions [T.sub.n,a,b] = 0 if a [greater than or equal to] n and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: [T.sub.n,a,-1] is the number of weakly increasing inversion sequences with [e.sub.n] = a. This is the number of Dyck paths whose last horizontal step is at height a which is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For b [greater than or equal to] 0, an inversion sequence e of length n with top (e) = a and bottom (e) = b can be obtained by adding b to an e' of length n - 1 with top (e') = a and bottom (e') [less than or equal to] b; or by adding a to an e' of length n - 1 with b < top (e') [less than or equal to] a and bottom (e') = b.

From Theorems 5 and 6 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

The first 12 terms of the sequence |[I.sub.n] (210) | are

1, 2, 6, 24,118, 674, 4306, 29990, 223668,1763468,14558588,124938648.

This sequence did not appear in the OEIS, but has now been assigned A263777.

A different recurrence to compute |[I.sub.n](210) | = |[I.sub.n](201| is derived in [16]. It is more complicated than (4) due to the choice of statistics. Nevertheless it is used to produce a generating function. Can (4) be used to derive a simpler generating function?

2.4 Inversion sequences avoiding 102

Our calculations showed that the number of inversion sequences in [I.sub.n] avoiding 102 is:

1, 2, 6, 22, 89, 381, 1694, 7744, 36168,[??] .

We checked for n [less than or equal to] 9 that this matches the sequence A200753 in the OEIS [10], whose generating function is given by

A(x) = 1 + (x - [x.sup.2])(A(x)) (3) (6)

but we were unable to prove this.

In [16], Mansour and Shattuck used a delicate generating function argument to confirm that the generating function [[SIGMA].sub.n>0] |[I.sub.n](102)|[x.sup.n] does satisfy (6) and from that they provide an explicit formula for |[I.sub.n](102)|.

Is there a direct combinatorial argument to show that the generating function for the 102-avoiding inversion sequences satisfies (6)?

2.5 Avoiding 120

Our calculations show that the number of inversion sequences avoiding the pattern 120 is given by:

1, 2, 6, 23, 103, 515, 2803, 16334, 100700,[??] ,

but this sequence did not appear in the OEIS (it has now been assigned A263778) and we do not yet know how to count it. This remains an open question.

3 Avoiding patterns with repeated letters

3.1 Avoiding 000: the Euler numbers and simsun permutations

The Euler up/down number [E.sub.n] is the number of permutations [pi] of [n] such that [[pi].sub.1] < [[pi].sub.2] > [[pi].sub.3] < [[pi].sub.4] > [??] . This is a well-known interpretation of the coefficients in the Taylor series expansion of tan(x) + sec(x):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Several families are known to be in bijection with the up/down permutations, including 0-1-2-increasing trees [14]. These are n-vertex rooted unordered trees in which each vertex has at most two children. Each vertex has a distinct label from the set [n] and labels increase along any path from the root to a leaf.

Theorem 7 |[I.sub.n](000)| = |[E.sub.n+i]|

Proof: Observe that e [member of] [I.sub.n] avoids 000 if and only if no entry occurs more than twice. We consider 0-1-2-increasing trees T with n + 1 vertices labeled 0, 1,[??] , n, which are counted by [E.sub.n+1]. It is easy to check that the mapping sending such a tree T to the inversion sequence e, where [e.sub.i] is the parent of i in T, is a bijection between these trees and [I.sub.n] (000).

For an example of this bijection, see Figure 2. The bijection of Theorem 7 shows that the set of labels on the internal vertices of T is exactly the set {[e.sub.1],[??] , [e.sub.n]}.

[FIGURE 2 OMITTED]

Theorem 8 Let [E.sub.nk] be the number of 000-avoiding inversion sequences of length n with k distinct entries. then

[E.sub.n,k] = (n - k + 1)[E.sub.n-1,k-1] + (2k - n + 1)[E.sub.n-1,k]

with initial conditions [E.subn,0] = 1 and [E.sub.nk] = 0 for k > n or k < [(n/2)].

Proof: Elements of [I.sub.n] (000) with k distinct entries can be constructed either by appending an unused entry to end of an e [member of] [I.sub.n-1] (000) with k - 1 distinct entries or by appending a used (but unrepeated) entry to the end of an e [member of] [I.sub.n-1] (000) with k distinct entries.

If e [member of] [I.sub.n-1] (000) has k - 1 distinct entries, then n - k of the possible entries are unused and available for en. Additionally, since [e.sub.n] = n - 1 is also possible, there are a total of n - k + 1 choices.

If e [member of] [I.sub.n-1] (000) has k distinct entries, then the other n - 1 - k are repeats. To append a used entry to e, while avoiding 000, [e.sub.n] must be one of the k - (n - 1 - k) used, but unrepeated, elements. This gives a total of 2k - n +1 choices. The recurrence follows.

Another family counted by the Euler up-down numbers is the set R[S.sub.n] of simsun permutations [24]. A permutation is simsun if it has no double descents, even after removing n, n - 1,[??] , k for any k. For example, 25637814 is not simsun: removing 8, 7, 6 yields the permutation 25314, where 5 < 3 < 1 is a double descent. It is known (e.g. [5]) that if r[s.sub.n,k] is the number of simsun permutations of [n] with k descents then

r[s.sub.n,k] = (k + 1)r[s.sub.n-1,k] + (n - 2k + 1)r[s.sub.n-1,k-1] (7)

with initial conditions r[s.sub.0,0] = 1 and r[s.sub.n,k] =0 for k > [??].

We have the following relationship between simsun permutations and 000-avoiding inversion sequences.

Corollary 2 The number of 000-avoiding inversion sequences in [I.sub.n] with n - k distinct entries is the number of simsun permutations of [n] with k descents.

Proof: The number of e [member of] [I.sub.n](000) with n - k distinct entries is obtained by replacing k by n - k in the recurrence of the previous theorem. Let [F.sub.n,k] = [E.sub.n,n-k] be the number of 000-avoiding inversion sequences in [I.sub.n] with n - k distinct entries. This gives:

[F.sub.n,k] = (n - (n - k) + 1)[F.sub.n-1,k] + (2(n - k) - n +1)[F.sub.n-1,k-1] = (k +1)[F.sub.n-1,k] + (n - 2k +1)[F.sub.n-1,k-1]

with initial conditions [F.sub.0,0] = 1 and [F.sub.n,k] =0 for k > [ (n/2)], the same recurrence satisfied by r[s.sub.n,k].

It would be interesting to have a natural bijection for Corollary 2.

The Entringer numbers, [d.sub.n,k], count the number of down/up permutations of [n + 1] with first entry equal to k + 1. (These are A008281 in the OEIS [10].) They satisfy the recurrence

[d.sub.n,k] = [d.sub.n,k-1] + [d.sub.n-1,n-k].

Our calculations suggest the following.

Conjecture 1 For n [greater than or equal to] 1 and 0 [less than or equal to] k [less than or equal to] n - 1, [d.sub.n,k] is the number of e [member of] [I.sub.n](000) with [e.sub.n] = k - 1.

3.2 Avoiding 001: [2.sup.n-1] and [S.sub.n](132,231)

In this section, we show that the 001-avoiding inversion sequences are counted by powers of 2. This indicates a natural connection between [I.sub.n](001) and permutations of length n avoiding certain patterns of length 3: the permutations in Sn avoiding both 213 and 312 are counted by [2.sup.n-1], as are nine other pairs of permutations of 123. This was shown by Simion and Schmidt in [23]. Rotem in [19] showed the (231,312) case.

Theorem 9 (Simion-Schmidt) |[S.sub.n]([alpha], [beta])| = [2.sup.n-1] for any of the following pairs ([alpha], [beta]) of patterns:

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

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

Observation 5 For n [greater than or equal to] 1, [I.sub.n](001) is the set of e [member of] [I.sub.n] satisfying, for some t [member of] [n],

[e.sub.i] < [e.s.sub.2] < [??] < [e.sub.t] [greater than or equal to] [e.sub.t+i] [greater than or equal to] [e.sub.t+2] [greater than or equal to] [??] [greater than or equal to] en. (8)

Theorem 10 Forn [greater than or equal to] 1, |[I.sub.n](001)| = [2.sup.n-1].

Proof: We give two proofs based on Observation 5.

First proof. In an inversion sequence e satisfying (8) for some t, it must be the case that [e.sub.i] is maximal (i.e. [e.sub.i] = i - 1) whenever 1 [less than or equal to] i [less than or equal to] t. It follows that the rest of the sequence p = ([e.sub.t+1],[??] , [e.sub.n]) can be viewed as a partition that fits in an n - t by t - 1 box, of which there are [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Summing over t from 1 to n gives the result.

Second proof. Recall from Section 1 the bijection [theta]([pi]) : [S.sub.n] [right arrow] [I.sub.n] for [pi] = [[pi].sub.1][??] [[pi].sub.n] [member of] [S.sub.n] defined by [theta][pi] = ([e.sub.1], [e.sub.2],[??] , [e.sub.n]), where [e.sub.i] = |{j | j < i and [e.sub.j] > [e.sub.i]}|. Note that e [member of] [I.sub.n] satisfies (8) if and only if [pi] = [[theta].sup._1](e) satisfies

[[pi].sub.1] > [[pi].sub.2] > [??] > [[pi].sub.t+1] < [[pi].sub.t+2] < [??] < [[pi].sub.n].

Such permutations are the ones that avoid both 132 and 231, so the result follows by Theorem 9.

3.3 Avoiding 011: the Bell numbers

In this section we show that the 011 -avoiding inversion sequences are counted by the Bell numbers.

The Bell number [B.sub.n] is the number of ways to partition an n-element set into nonempty subsets called blocks. The numbers [S.sub.n,k] of such set partitions into k blocks are known as the Stirling numbers of the second kind and they satisfy the recurrence [S.sub.n,k] = k[S.sub.n-1,k] + [S.sub.n-1,k-1] with initial conditions

Observation 6 The 011 -avoiding inversion sequences are those in which the positive entries are distinct.

Theorem 11 The number of 011-avoiding inversion sequences in [I.sub.n] with k zeros is [S.sub.n,k].

Proof: An inversion sequence e [member of] [I.sub.n](011) with k zeros can arise from an inversion sequence in [I.sub.n-1](011) in one of two ways. If [e.sub.n] =0 then ([e.sub.1],[??] , [e.sub.n-1]) [member of] [I.sub.n-1](011) has k - 1 zeros. Otherwise, ([e.sub.1],[??] , [e.sub.n-1]) [member of] [I.sub.n-1] has k zeros and, by Observation 6, it has n - 1 - k distinct positive entries (out of the possible n - 2 positive elements of [n - 2].) This means that any of the remaining k - 1 positive elements can be assigned to [e.sub.n], as well as the new possibility n - 1, for a total of k. Since the only e [member of] [I.sub.n](011) with one zero is (0,1, 2,[??] , n) and the only e [member of] [I.sub.n](011) with n zeros is (0,0,[??] , 0), the recurrence of the Stirling numbers is satisfied with the same initial conditions.

A restricted growth function is a finite integer sequence v = (v1,[??] ,vn) with [v.sub.1] = 1 andfor 1 < i [less than or equal to] v, [v.sub.i] [less than or equal to] 1 + max{[v.sub.1],[??] , [v.sub.i-1]}. Let [G.sub.n] be the set of restricted growth functions of length n. Elements of [G.sub.n] encode partitions of [n]: given a partition [product] of [n], order the blocks of [product] as [B.sub.1],[??] , [B.sub.k] so that min([B.sub.i]) < min([B.sub.i+1]) for 1 [less than or equal to] i < k. Then v [member of] [G.sub.n] corresponds to the set partition [product] where i is in block [B.sub.b] of [product] if and only [v.sub.i] = b. The number of distinct entries of v is the number of blocks of [product].

For example if v = (1, 2, 3, 1, 3, 2, 4, 5,6, 3,4, 2) then

[product] = ({1, 4}, {2, 6, 12}, {3, 5,10}, {7,11}, {8}, {9}).

The proof of Theorem 11 gives rise to a bijection from [I.sub.n](011) to [G.sub.n]. For an integer sequence s, let zeros(s) be the number of zeros in s. Let I(011) be the set of all 011-avoiding inversion sequences, regardless of length and G the set of all restricted growth sequences.

Define a map [kappa]: I(011) [right arrow] G for e [member of] I(011) recursively. If |e| = 1, then e = (0) and we define [kappa](e) = (1). For |e| = n > 1, assume [kappa]([e.sub.1],[??] , [e.sub.n-1]) has been defined and let [kappa] = zeros(e). Recall from the proof of Theorem 11 that since e [member of] [I.sub.n](011), if [e.sub.n] > 0 then [e.sub.n] must be one of the [kappa] elements of [n - 1] - {[e.sub.1,[??] ] [e.sub.n-1]}, call them [a.sub.1] < [a.sub.2] < [??] < [a.sub.[kappa]]. So with that notation, we define [kappa](e) = [kappa]([e.sub.1],[??] , [e.sub.n-1]) * [v.sub.n] where [v.sub.n] = [kappa] + 1 if [e.sub.n] = 0 and [v.sub.n] = i if 0 < [e.sub.n] = [a.sub.i].

For example, [kappa](0,0,0,1,4,3,0,0,0,6, 8,5) = (1,2, 3,1, 3,2,4,5, 6,3,4, 2)

It is not hard to prove by induction that if e = ([e.sub.1],[??] , [e.sub.n]) [member of] I(011) and [kappa]([e.sub.1],[??] , [e.sub.n]) = ([v.sub.1],[??] , [v.sub.n]) then 1 [less than or equal to] [v.sub.i] [less than or equal to] zeros([e.sub.1],[??] , [e.sub.i]) for all i, from which it clearly follows that ([v.sub.1],[??] , [v.sub.n]) [member of] G. It is straightforward to reverse [kappa], giving a length-preserving bijection between I(011) and G.

3.4 Wilf-equivalent patterns 101 and 110: [S.sub.n](1-23-4)

Our calculations suggested that the patterns 101 and 100 are Wilf equivalent on inversion sequences. The avoidance sequence for both patterns agree with sequence A113227 in the OEIS [10], where it is said to be |[S.sub.n](1-23-4)|, the number of permutations avoiding the pattern 1-23-4, that is, with no i < j < [kappa] such that [[pi].sub.i] < [[pi].sub.j] < [[pi].sub.j+1] < [[pi].sub.k]. The asymptotics of |[S.sub.n] (1-23-4) | were studied by Elizalde in [8], where he established good upper and lower bounds.

The OEIS led us to a paper of David Callan [4], which shows that permutations of [n] avoiding 1-23-4 are in bijection with increasing ordered trees with n + 1 vertices whose leaves, taken in preorder, are also increasing. Callan showed that if [u.sub.n,k] is the number of such trees with n +1 vertices in which the root has k children then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

with initial conditions [u.sub.0,0] = 1 and [u.sub.n,k] = 0 if k > n, or n > 0 and k = 0.

Theorem 12 |[I.sub.n](101)| = |[S.sub.n](1-23-4)|.

Proof: Let [Z.sub.n,k] be the number of e [member of] [I.sub.n](101) with exactly k zeros and let [z.sub.n,k] = |[Z.sub.n,k]|. We show that [z.sub.n,k] satisfies (9) with the same initial conditions.

Let [??] be the number of e [member of] [Z.sub.n,k] with exactly [??] ones. Recall that applying [[sigma].sub.-1] to an inversion sequence decreases the positive entries by 1.

Define [gamma]: [I.sub.n] [right arrow] [I.sub.n-1] by [gamma] ([e.sub.1], [??] ,[e.sub.n]) = [[sigma].sub.-1]([e.sub.2],[??] , [e.sub.n]). Note that [??]. In fact, if [??] is a bijection between [Z.sub.n,k,0] and [Z.sub.n-1,k-1]. However, if [??], each element of [Z.sub.n-1,k-1] is the image under [gamma] of k elements of [??]. To see this, let e [member of] [??] and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], be the subsequence of e consisting of the zeros and ones in e. Note [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and, since e avoids 101, the [??] ones in [??] must be consecutive. There are k such ways to place the ones in [??], namely as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Clearly [z.sub.0,0] = 1 and [z.sub.n,k] =0 if k > n, or n > 0 and k = 0. Re-indexing the summation gives (9).

Comparing the proof of the recurrence for [z.sub.n,k] here with Callan's proof of the recurrence for [u.sub.n,k] gives rise to a bijection between 101 -avoiding inversion sequences with k zeros and ordered increasing trees with increasing leaves in which the root has k children. We omit the details for now.

Theorem 13 |[I.sub.n](101)| = |[I.sub.n](110)|.

Proof: We observe that the number of e [member of] [I.sub.n](110) with k zeros and I ones satisfies the same recurrence (9). The proof follows the same process as that of Theorem 12 to the point of considering the substring of 0's and 1's for some e [member of] [I.sub.n](110). Since e now avoids 110, in the substring [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], consisting of its zeros and ones, all but the first I ones must be in the last [??] positions of [??]. This leaves k possible positions for the first one: [b.sub.2], [b.sub.3],[??] , [b.sub.k+1].

Using the recursion (9) for [u.sub.n,k+1] and [u.sub.n,k], if we take k[u.sub.n,k+1] and subtract (k + 1)[u.sub.n,k] the result is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Is there a simple interpretation for this in terms of inversion sequences, trees, or permutations?

3.5 Avoiding 010, avoiding 100

Our calculations show that the number of inversion sequences avoiding the pattern 010 is given by:

1, 2, 5,15, 53, 215, 979,4922, 26992,[??] ,

but this sequence did not appear in the OEIS (is is now A263779) and we do not yet know how to count it.

Similarly, we have calculated that |[I.sub.n](100) | begins like this:

1, 2, 6, 23,106, 565, 3399, 22678, 165646,[??] ,

but it also did not appear in the OEIS (it is now A263780).

4 Revisiting 021-avoidance

In this section, we delve deeper into the structure of 021-avoiding inversion sequences and their relationship to structures counted by the Schroder numbers. First, we introduce a bijection that illustrates further natural correspondences between statistics in inversions sequences and Schroder paths. After, we consider the ascent statistic, which we show is symmetric in [I.sub.n] (021) via a bijection with certain black/white binary trees.

4.1 Another correspondence between [I.subn.(021) and Schroder paths

Now we define a different bijection, which serves as a tool to relate different statistics between inversion sequences and Schroder paths. Using Observation 2, we can see that for any e [member of] [I.sub.n] (021), e can be written as e = [b.sub.0][b.sub.1][b.sub.2][??] [b.sub.n-1] where [b.sub.k] is the substring ([e.sub.i], [e.sub.i+1],[??] , [e.sub.j]) such that [e.sub.i] is the first occurrence of k, and, for every t [member of] {i, i + 1,[??] , j}, we have [e.sub.t] = k or [e.sub.t] = 0. We call each [b.sub.k] a block and say that some [b.sub.k] is maximal if [b.sub.k] = ([e.sub.k+1], [e.sub.k+2],[??] , [e.sub.j]) (making [e.sub.k+1] a maximal entry). Notice that any maximal entry [e.sub.j+1] must be the first entry of [b.sub.j].

For example, if e = (0,1,0,1,0, 2,5, 7,7, 7,9,0,10,11,12), then [b.sub.0] = (0), [b.sub.1] = (1,0,1,0), [b.sub.2] = (2), [b.sub.5] = (5), [b.sub.7] = (7, 7,7), [b.sub.9] = (9,0), [b.sub.10] = (10), [b.sub.11] = (11), [b.sub.12] = (12), and [b.sub.3] = [b.sub.4] = [b.sub.6] = [b.sub.8] = [b.sub.13] = [b.sub.14] are all empty strings. Additionally, [b.sub.0], [b.sub.1] and [b.sub.7] are maximal.

This decomposition is essential to describing our bijection. It also produces a recurrence relation on 021-avoiding inversion sequences.

Theorem 14 Let Yn, k be the number of 021-avoiding inversion sequences of length n with k maximal elements, including [e.sub.1] = 0. then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

with initial condition [Y.sub.1,1] = 1.

Proof: Given a 021-avoiding inversion sequence of length n with k maximal elements, let [b.sub.j] be the last maximal block. Consider the effect of removing the last entry of [b.sub.j]. If [b.sub.j] contains only one element, then [b.sub.j] = [b.sub.n] since it is the last maximal block, and removing [b.sub.n] gives an inversion sequence contributing to [Y.sub.n - 1,k - 1]. If [b.sub.j] contains more than one element, it could end in j or 0. Either way, removing the last entry shifts everything following [b.sub.j] one position earlier. This shift may result in a number of additional maximal blocks following [b.sub.j], so the resulting inversion sequence contributes to the term [Y.sub.n-1,i] where k [less than or equal to] i [less than or equal to] n - 1.

Conversely, a 021-avoiding inversion sequence of length n with k maximal elements can be obtained from a 021-avoiding inversion sequence of length n - 1 with k - 1 maximal elements by appending n - 1 to the end. Additionally, given any 021-avoiding inversion sequence of length n - 1 with at least k maximal elements, if [b.sub.j] is the kth maximal block, we can obtain a some e [member of] [I.sub.n] (021) with k maximal blocks by appending either j or 0 to the end of [b.sub.j]. By doing this, all maximal blocks following [b.sub.j] are no longer maximal, since the entries have been shifted, resulting in the desired number of maximal blocks.

A valley in a Schroder Path is a D step immediately followed by an U step. Let the valley word of a Schroder Path be the word obtained when any consecutive DU is replaced with a V .So the Schroder path UUDUFUDUFDDDUUDUDDUUUFDDD from Figure 1 would have valley word

UUVFUVFDDVUVDVUUFDDD.

We define a mapping [phi]: [R.sub.n-1 [right arrow]] {I.sub.n] (021) using the valley word for each element in [R.sub.n-1]. The entries of the valley word are interpreted as instructions for building an inversion sequence.

Let p be the valley word of a path in [R.sub.n-1]. Define M to be a word on the elements {0, 1, 2,[??] , n - 1} that keeps track of the current maximal blocks in the inversion sequence being built, which we denote e. Initially, set M = 0 and e = [b.sub.0] where [b.sub.0] = (0). So, the initial length of e is 1.

The valley word [??] is read left to right and each [p.sub.i] interpreted as an action performed on M and e.

* If [p.sub.i] = U, append [??] to the end of e and M, where [??] is equal to the current length of e. This is equivalent to starting a new block [??] at the end of e.

* If [p.sub.i] = D, delete the last entry of M.

* If [p.sub.i] = V, append a 0 to the end of block [b.sub.j] where j is the last entry of M.

* If [p.sub.i] = F, append a j to the end of block [b.sub.j] where j is the last entry of M.

Notice that this construction yields an inversion sequence with weakly increasing positive entries and therefore avoids 021. Additionally, [phi] is reversible and is a bijection. As an example,

[phi](UUVFUVFDDVUVDVUUFDDD) = (0, 1, 0, 0, 2, 0, 2, 5, 0, 5, 9, 0, 12, 13, 13),

is the image of the Schroder path in Figure 1. Notice that this is not the same as

[rho](UUVFUVFDDVUVDVUUFDDD)

from Section 2.1.

The bijection [phi] succeeds in relating different statistics in 021 -avoiding inversion sequences and Schroder paths. In the following theorem, the number of late zeros in an inversion sequence e [member of] [I.sub.n] (021) is the number of zeros occurring in the blocks [b.sub.1][b.sub.2[??] ] [b.sub.n-1]. Additionally, the number of distinct nonzero values in an inversion sequence e = [b.sub.0][b.sub.1][b.sub.2[??] ] [b.sub.n-1] [member of] [I.sub.n](021) is |{[b.sub.i] | i [not equal to] 0, [not equal to] [epsilon]}|. By using the definition of [phi], we achieve the following results.

Corollary 3 For n [less than or equal to] 1,

1. if p [member of] [R.sub.n-1] with k valleys, then [phi](p) is an inversion sequence in [I.sub.n](021) with k late zeros.

2. if p [member of] [R.sub.n-1] where k is the number of occurrences of U in the valley word of p (alternatively, this is the total number of up steps minus the number of valleys), then [phi](p) is an inversion sequence in [I.sub.n](021) with k distinct nonzero values.

3. if p [member of] [R.sub.n-1] has k flat steps at height 0, then [phi](p) [member of] [I.sub.n](021) begins with k +1 zeros.

The number of Schroder paths of length n with k valleys is counted by A101282 in OEIS.

Based on our computations, the following statistic seems to correspond between inversion sequences and Schroder paths. However, neither [rho] nor [phi] provide the necessary correspondence. An ascent in a Schroder path is a maximal sequence of consecutive up steps.

Conjecture 2 The number of p [member of] [R.sub.n-1] with k - 1 ascents is equal to the number of e [member of] [I.sub.n](021) with k distinct values.

The sequence in Conjecture 2 is counted by A090981 is OEIS. Additionally, notice that Conjecture 2 in tandem with (2) from Corollary 3 would prove that the number of Schroder paths in [R.sub.n-1] with k ascents is equal to the number of paths in [R.sub.n-1] with k occurrences of U that are not a part of a valley, DU.

4.2 A symmetric statistic on 021-avoiding inversion sequences

As ascent in an inversion sequence e is an index i such that [e.sub.i] < [e.sub.i+1]; the number of ascents in e is denoted by asc (e). In this section, we show that the ascent statistic is symmetric on 021-avoiding inversion sequences. That is, if [a.sub.n,k] is the number of e [member of] [I.sub.n](021) with k ascents then [a.sub.n,k] = [a.sub.n,n-k-1].

We make use of a tree structure that appears in the thesis of Brian Drake [6]. Define [[tau].sub.n-1] to be the set of rooted binary trees on n - 1 nodes, where each node is either black or white, and no node is the same color as its right child. For an example, see Figure 3. Let [tau] be the set of all such trees with no restriction on the number of nodes. In [6], Drake uses an inversion theorem for labeled trees to compute the generating function for [tau], keeping track of the number of black nodes. One consequence is that |[[tau].sub.n]| = [r.sub.n], the nth large Schroder number.

The trees in [[tau].sub.n] are also related by a natural bijection to the separable permutations in [S.sub.n]. A separable permutation is a permutation that can be completely decomposed with direct and skew sums; the trees in [[tau].sub.n] provide the recipe for this decomposition. (See [2].) The separable permutations in [S.sub.n] are exactly those that avoid 2413 and 3142 and it is known that |[S.sub.n](2413,3142) | = [r.sub.n] ([22, 26]).

Returning to the ascent statistic on inversions sequences, observe that for a fixed number of nodes, the number of trees in [tau] with k black nodes is the same as the number with k white nodes. Thus the symmetry of the ascent statistic on [I.sub.n](021) is a consequence of the following, which we will prove.

Theorem 15 The number of trees in [[tau].sub.n-1] with k black nodes is the same as the number of inversion sequences in [I.sub.n](021) with k ascents.

Theorem 15 will follow from Proposition 1 below once we define an appropriate bijection. From that we will have the following.

Corollary 4 Let [a.sub.n,k] be the number of e [member of] [I.sub.n](021) with k ascents. Then [a.sub.n,k] = [a.sub.n,n_k_1].

We define a bijection between [I.sub.n](021) and [[tau].sub.n-1] such that the number of ascents in an inversion sequence is equal to the number of black nodes in the corresponding tree. Define two operations on [tau]. Given T, S [member of] [tau], let [omega](T, S) be the tree with a white root that has left subtree T and right subtree S. Similarly, define [beta](T, S) to be the tree with a black root that has left subtree T and right subtree S. Note that in [omega](T, S) and [beta](T, S), the tree S is required to have a black root and white root, respectively.

Throughout this section, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. These sets are nonempty only for n [greater than or equal to] 2.

We define a bijection [tau]: [I.sub.n](021) [right arrow] [[tau].sub.n-1] recursively. Set [tau](0) to be the empty tree. The mapping [tau] will be defined such that any inversion sequence in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] maps to a tree with a white root and any inversion sequence in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] maps to a tree with a black root. Anytime we consider the operations [OMEGA]([tau](e'),[tau](e'')) and [beta]([tau](e'),[tau](e'')), we will ensure that e'' begins with 0,1 and 0,0, respectively, or e'' = (0) in order to satisfy the condition on right children.

Given any inversion sequence e = ([e.sub.1], [e.sub.2], [e.sub.3],[??] ,en) [member of] [I.sub.n] (021), we can consider two cases based on whether [e.sub.2] =0 or [e.sub.2] = 1 (which is equivalent to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively). Let [??] be the largest value such that [??]. Additionally, let k + 1 be the earliest position after [??] such that [??]. If there is no such position, set k = n. Define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [??] denotes the sequence of [??] zeros. For an example, see Figure 3.

First we show that [??] is a 021-avoiding inversion sequence. For [??] each entry [e.sub.k+i] is in the ([??])-th position. So we must show that whenever [e.sub.k+i] = [not equal to] 0, we have 1 [less than or equal to] [??]. By choice of k and Observation 2, it follows that [??] and the result immediately follows. Finally, note that [??] will avoid the pattern 021, since its nonzero entries must weakly increase.

Now consider ([??]). We know the nonzero entries of ([??]) will weakly increase. Additionally, for [??] is in position [??]. Whenever [e.sub.i] [not equal to] 0 we want [??]; this immediately follows by choice of k. Therefore, ([??]) is a 021-avoiding inversion sequence. Notice that the definitions of [??] and k imply that [??] when [e.sub.2] =0 and [??] when [e.sub.2] = 1, which is necessary to satisfy the condition on right children.

The mapping [tau] has an inverse, ensuring that it is a bijection from [I.sub.n](021) to [[tau].sub.n-1].

Our bijection provides a correspondence between a number of statistics on inversion sequences and trees. First, we settle Theorem 15 with the following proposition. Given T [member of] [tau], define B(T) to be the number of black nodes in [tau].

Proposition 1 For any e [member of] [I.sub.n](021), asc (e) = B([tau](e)).

Proof: (Induction.) We immediately see that this is true for n = 1. For n > 1, let e [member of] [I.sub.n](021) with j ascents. We show that [tau](e) has j black nodes. Set [??] and k to be defined as in the definition of [tau].

[FIGURE 3 OMITTED]

If [??], then e = (0, 0,[??] , 0) or e = (0, 1, 1,[??] , 1). In either of these cases, the only nodes of [tau](e) are in the leftmost branch. Additionally, [tau](0,0,[??] , 0) is a tree with all white nodes and [tau](0, 1, 1,[??] , 1) is a tree whose root is black and all other nodes are white. So, B([tau](e)) = asc (e) in either case.

If [??] and k = n, then [??] is an ascent; additionally, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then 1 is guaranteed to be an ascent. The only ascents of e besides these are elements of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII. Notice that [tau](e) = [??] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In each of these, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII respectively. It follows inductively that B([tau](e)) = asc (e).

Now, if [??] and k < n, we have the following argument, which we break into two cases. If [e.sub.2] = 0, then the choice of [??] and k requires that [??] and k are ascent positions. Additionally, there are no ascents in ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII), so asc (e) = 1 asc ([e.sub.k+1], [e.sub.k+2],[??] , [e.sub.n]). It follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If [e.sub.2] = 1, then the definitions of [??] and k require that [??], and k are ascent positions. Additionally, there are no ascents in ([??]), so asc [??] asc ([e.sub.k+1], [e.sub.k+2],[??] , [e.sub.n]). It follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It would be nice to have a direct combinatorial proof of Corollary 4.

There are two other natural statistics on trees and inversion sequences for which [tau] provides a correspondence.

Theorem 16 The number of maximal values in an inversion sequence e [member of] [I.sub.n](021), not counting the initial zero of e, is equal to the number of black nodes in the leftmost branch in [tau](e).

Proof: Let e [member of] [I.sub.n](021) with t maximal values. By choice of [??] and k in the definition of [tau], none of the entries [e.sub.3], [e.sub.4],[??] , [e.sub.k] of e can be maximal. Therefore, the maximal values of e will all occur among the entries [e.sub.1], [e.sub.2], [e.sub.k+1], [e.sub.k+2],[??] , Additionally, if [e.sub.i] is maximal, where i [member of] {k + 1, k + 2,[??] , n}, then that corresponding entry will be maximal in [??].

The number of black nodes in the left branch of [tau](e) is equal to the number of black nodes in the left branch of [??] if [e.sub.2] =0. If [e.sub.2] = 1, then the number of black nodes in the left branch of [tau](e) exceeds the number of black nodes in the left branch of [??] by one. The result follows inductively.

The mapping [tau] visibly encodes the number of initial zeros in an inversion sequence. The following corollary follows quickly from the definition of [tau].

Corollary 5 Let e [member of] [I.sub.n](021) where 0 = [e.sub.1] = [e.sub.2] = [??] = [e.sub.l+1]. Then the top [??] nodes of the leftmost branch of [tau](e) are white.

5 Concluding remarks

This report only scratches the surface of pattern-avoidance in inversion sequences, but we hope that it demonstrates the surprising ability of pattern-avoiding inversion sequences to provide simple and natural models for familiar combinatorial sequences.

A number of open questions have been raised throughout this paper; most notably, finding general expressions for the avoidance sequences for the patterns 120, 110, and 010. In addition to settling Conjecture 1 in Section 3.1 and Conjecture 2 in Section 4.1, it would be nice to see a simple bijection between [I.sub.n](012) and Boolean permutations of [n] (Section 2.1); a combinatorial interpretation of the recurrence at the end of Section 3.4 for the number of inversion sequences in [I.sub.n](101) with k zeros; and a direct combinatorial proof of Corollary 4 in Section 4.2.

There are many obvious ways to extend or generalize this work: consider longer patterns, sets of patterns, other statistics, q-analogs, bijective proofs, or more natural bijections; settle enumeration questions; or even consider pattern avoidance in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for other sequences s of positive integers.

In Part II of this report, we consider a different generalization of pattern-avoidance in inversion sequences and discover some nice surprises, a few conjectures, and several open questions.

Acknowledgements

We would like to express our appreciation to Ira Gessel for a generating function argument that led to the bij ection between 021 -avoiding inversion sequences and the Large Schroder numbers in Section 4.1. Thanks to Michael Albert for making his PermLab software freely available [1]. Thanks to the Simons Foundation for a grant to the third author which supported the travel of the second author for collaboration. We extend our thanks to Toufik Mansour for sending us an advance copy of [16].

We especially owe a debt of gratitude to Neil Sloane and the OEIS Foundation, Inc. Our work was greatly facilitated by the On-Line Encyclopedia of Integer Sequences [10].

References

[1] Michael Albert. Permlab: Software for permutation patterns, 2012. http://www.cs.otago.ac.nz/staffpriv/malbert/permlab.php.

[2] Michael Albert, Cheyne Homberger, and Jay Pantone. Equipopularity classes in the separable permutations. Electron.]. Combin., 22(2):#P2.2, 2015.

[3] Mireille Bousquet-Melou, Anders Claesson, Mark Dukes, and Sergey Kitaev. (2+2)-free posets, ascent sequences and pattern avoiding permutations. J. Combin. Theory, Ser. A, 117(7):884 - 909, 2010.

[4] David Callan. A bijection to count (1-23-4)-avoiding permutations. 2010. Unpublished manuscript, http://arxiv.org/abs/10 08.23 75.

[5] Chak-On Chow and Wai Chee Shiu. Counting simsun permutations by descents. Ann. Comb., 15(4):625-635,2011.

[6] Brian Drake. An inversion theorem for labeled trees and some limits of areas under lattice paths. ProQuest LLC, Ann Arbor, MI, 2008. Thesis (Ph.D.)-Brandeis University.

[7] Paul Duncan and Einar Steingrimsson. Pattern avoidance in ascent sequences. Electron. J. Combin., 18(1):Paper226, 17, 2011.

[8] Sergi Elizalde. Asymptotic enumeration of permutations avoiding generalized patterns. Adv. in Appl. Math., 36(2):138-155, 2006.

[9] Ira Gessel. Schroder numbers, large and small. CanaDAM 2009, Montreal, 2009. Slides, http://www.crm.umontreal.ca/CanaDAM2009/pdf/gessel.pdf.

[10] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2011. http://oeis.org.

[11] Sergey Kitaev. Patterns in permutations and words. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg, 2011. With a foreword by Jeffrey B. Remmel.

[12] Donald E. Knuth. The art of computer programming. Vol. 1: Fundamental algorithms. Second printing. Addison-Wesley Publishing Co., Reading, Mass.-London-DonMills, Ont, 1969.

[13] Donald E. Knuth. The art of computer programming. Volume 3. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching, Addison-Wesley Series in Computer Science and Information Processing.

[14] A. G. Kuznetsov, I. M. Pak, and A. E. Postnikov. Increasing trees and alternating permutations. Uspekhi Mat. Nauk, 49(6(300)):79-110, 1994.

[15] Percy A. MacMahon. Combinatory analysis. Two volumes (bound as one). Chelsea Publishing Co., New York, 1960.

[16] Toufik Mansour and Mark Shattuck. Pattern avoidance in inversion sequences. Preprint (private communication).

[17] Toufik Mansour and Mark Shattuck. Some enumerative results related to ascent sequences. Discrete Math., 315:29-41, 2014.

[18] T. Kyle Petersen and Bridget Eileen Tenner. The depth of a permutation. J. Comb., 6(1-2):145-178, 2015.

[19] D. Rotem. Stack sortable permutations. Discrete Math., 33(2):185-196, 1981.

[20] Carla D. Savage and Michael J. Schuster. Ehrhart series of lecture hall polytopes and Eulerian polynomials for inversion sequences. J. Combin. Theory Ser. A, 119(4):850-870, 2012.

[21] Carla D. Savage and Mirko Visontai. The s-Eulerian polynomials have only real roots. Trans. Amer. Math. Soc., 367(2):1441-1466, 2015.

[22] Louis Shapiro and A. B. Stephens. Bootstrap percolation, the Schroder numbers, and the N-kings problem. SIAMJ. Discrete Math., 4(2):275-280, 1991.

[23] Rodica Simion and Frank W. Schmidt. Restricted permutations. European J. Combin., 6(4):383-406, 1985.

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

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

[26] Julian West. Generating trees and the Catalan and Schroder numbers. Discrete Math., 146(1-3):247-262, 1995.

Sylvie Corteel (1 *)

Megan A. Martinez (2)

Carla D. Savage (3)

Michael Weselcouch (4)

(1) LIAFA, CNRS, Universite Paris Diderot 7, Paris, France

(2) Department of Mathematics, Ithaca College, Ithaca, NY

(3) Department of Computer Science, North Carolina State University, Raleigh, NC

(4) Department of Mathematics, North Carolina State University, Raleigh, NC

received 27th Nov. 2015, accepted 7th Jan. 2016.

(*) Supported in part by grant ANR-08-JCJC-0011

(i) When our paper was first posted to the arXiv we were notified by Mansour that he and Shattuck had independently obtained results on |[I.sub.n][sigma]| for the patterns ?? = 012, 021, 102, 201, 210 in [16]. Their methods are quite complementary to ours, as we will describe in Section 2.

Tab. 1: Enumeration of inversion sequences avoiding permutations and words. (OEIS numbers in parentheses were newly assigned after this paper was posted to the arXiv) Pattern p [a.sub.n] = |[I.sub.n](p)| counted by: in OEIS? 012 [F.sub.2n-1] (Boolean permutations) A001519 021 Large Schroder numbers A006318 102 A(x) = 1 + (x - [x.sup.2])(A(x)) (3) [16] A200753 120 ? no (A263778) 201 Theorem 6 and (5) no (A263777) 210 Theorem 6 and (5) no (A263777) 000 Euler up/down numbers A000111 001 [2.sup.n-1] (|[S.sub.n](132,231)|) A000079 010 ? no (A263779) 100 ? no (A263780) 011 Bell numbers A000110 101 |[S.sub.n](1-23-4)| A113227 110 |[S.sub.n](1-23-4)| A113227 Pattern p sequence identifier [a.sub.7] 012 233 021 1806 102 1694 120 2803 201 4306 210 4306 000 1385 001 64 010 979 100 3399 011 877 101 3207 110 3207

Printer friendly Cite/link Email Feedback | |

Author: | Corteel, Sylvie; Martinez, Megan A.; Savage, Carla D.; Weselcouch, Michael |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Date: | Jun 1, 2016 |

Words: | 11268 |

Previous Article: | Snow leopard permutations and their even and odd threads. |

Next Article: | The complexity of pattern matching for 321-avoiding and skew-merged permutations. |

Topics: |