Enumerations of Permutations Simultaneously Avoiding a Vincular and a Covincular Pattern

of Length 3

Christian Bean and Henning Ulfarsson School of Computer Science Reykjavik University Menntavegi 1 101 Reykjavik Iceland

                  christianbean@ru.is
                    henningu@ru.is

Anders Claesson Science Institute University of Iceland Dunhaga 5 107 Reykjavik Iceland

                       akc@hi.is

Abstract

Vincular and covincular patterns are generalizations of classical patterns allowing restrictions on the indices and values of the occurrences in a permutation. In this paper we study the integer sequences arising as the enumerations of permutations simultaneously avoiding a vincular and a covincular pattern, both of length 3, with at most one restriction. We see familiar sequences, such as the Catalan and Motzkin numbers, but also some previously unknown sequences which have close links to other combinatorial objects such as lattice paths and integer partitions. Where possible we include a generating function for the enumeration. One of the cases considered settles a conjecture by Pudwell (2010) on the Wilf-equivalence of barred patterns. We also give an alternative proof of the classic result that permutations avoiding 123 are counted by the Catalan numbers.

1 Introduction

A permutation π contains a classical pattern p, which is itself a permutation, if π contains a subword which is order isomorphic to p. Babson and Steingrímsson [3] introduced a generalization of classical patterns that allows the requirement that two adjacent letters in a pattern must be adjacent in the permutation. These are called vincular patterns. A further extension, called bivincular patterns, was provided by M. Bousquet-Mélou et al. [4]. We call the special case when only constraints on values are allowed covincular patterns. The set of bivincular patterns is closed under the action of the symmetry group of the square and an alternative way of describing the covincular patterns is that they are inverses of vincular patterns.

Simultaneous avoidance of two vincular patterns was studied by Claesson and Mansour [7] and by Kitaev [13]. Allowing one of the patterns to be covincular is a natural follow up question and leads to some well-known sequences. The overall goal of this paper is to count the number of permutations simultaneously avoiding a length 3 vincular and a length 3 covincular pattern, where both patterns force at most one restriction. A summary of our results can be found in Table 1; these results are detailed in Sections 2 through 10. One of our methods can be adapted to give a new simple proof of the classical result that permutations avoiding the classical pattern 123 are counted by the Catalan numbers; see Section 11. The Appendix contains all the results from the paper collected by their respective enumeration.

We now present the definitions and notation we use. An alphabet, X, is a non-empty set. An element of X is a letter. A finite sequence of letters from X is called a word. The word with no letters is called the empty word and is denoted ϵ. For a word w we say that the length of the word, denoted |w|, is the number of letters in w, that is, if w = x_{1}x_{2} ⋯ x_{n} then |w| = n. A subword of w is a finite sequence x_{i_{1}}x_{i_{2}} ⋯ x_{i_{k}} where 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n.

As we are interested in permutations the alphabet we use is [n] = {1, 2, …, n} for some n ∈ ℕ = {0, 1, 2, …}. A length n permutation is a length n word x = x_{1}x_{2} ⋯ x_{n} of this alphabet with no repeated letters where x_{i} = π(i). Let S_{n} denote the set of all length n permutations. Let w = w_{1}w_{2} ⋯ w_{k} and v = v_{1}v_{2} ⋯ v_{k} be words with distinct letters. We say that w is order isomorphic to v if, for all i and j, we have w_{i} < w_{j} precisely when v_{i} < v_{j}. For example 53296 and 32154 are order isomorphic.

Definition 1 (Bousquet-Mélou et al. [4, page 4]). A bivincular pattern is a triple, p = (σ, X, Y), where σ ∈ S_{k} is the underlying permutation and X and Y are subsets of {0, 1, …, k}. An occurrence of p in π ∈ S_{n} is a subsequence w = π(i_{1}) ⋯ π(i_{k}) order isomorphic to σ such that

∀x ∈ X, i_{x+1} = i_{x} + 1 and ∀y ∈ Y, j_{y+1} = j_{y} + 1,

where {π(i_{1}), …, π(i_{k})} = {j_{1}, …, j_{k}} and j_{1} < j_{2} < ⋯ < j_{k}. By convention, i_{0} = j_{0} = 0 and i_{k+1} = j_{k+1} = n + 1. If such an occurrence exists we say that π contains σ.

We define the length of a bivincular pattern p = (σ, X, Y), denoted |p|, to be |σ|. Further, a permutation avoids p if it does not contain p. If Y = ∅ then p is a vincular pattern. If X = ∅ then p is a covincular pattern. If X = Y = ∅ then p is a classical pattern. For example, the permutation 15423 contains an occurrence of (123, {2}, ∅), namely the subword 123, but avoids (123, {1}, ∅). The permutation 23514 contains an occurrence of (312, ∅, {2}), namely the subword 523, but avoids (312, ∅, {1}). The sets of all length n permutations avoiding the pattern p is denoted

Av_{n}(p) = {π ∈ S_{n} : π avoids p} ,

and, for P a set of patterns, Av_{n}(P) = ∩_{p∈P} Av_{n}(p) and Av(P) = ∪_{n≥0}Av_{n}(P).

Below we use a pictorial representation of vincular and covincular patterns. For a length n bivincular pattern p = (σ, X, Y): First draw the collection of points from the underlying permutation i.e. (k, σ_{k}) where 1 ≤ k ≤ n. Then, for each i ∈ X, shade the ith column and, for each j ∈ Y, shade the jth row; see Figure 1. The shading is used to denote the empty regions in the permutation if we were to overlay the grid onto an occurrence of the pattern.

Figure 1: (231, ∅, ∅), (123, {2}, ∅), (123, {1}, ∅), (312, ∅, {2}), and (312, ∅, {1})

Remark 2. If p = (σ, X, Y) and p′ = (σ, X′, Y′), where X′ ⊆ X and Y′ ⊆ Y, then we immediately have that Av_{n}(p′) ⊆ Av_{n}(p).

We are interested in |Av_{n}(p, r)| where p = (σ, X, ∅) is a length 3 vincular pattern with X ∈ {∅, {1}, {2}}, and r = (τ, ∅, Y) is a length 3 covincular pattern with Y ∈ {∅, {1}, {2}}, in a sense completing the work by Claesson and Mansour [7]. We do not consider the following cases: 1) The case where X = Y = ∅ since this is classical avoidance of two length 3 patterns, which was done by Simion and Schmidt [17]; 2) The case when either X or Y contains 0 or 3 since this forces the patterns to occur with the first or last, smallest or largest, letters in the permutation and would introduce too many cases to be considered in a single paper; 3) The case when X or Y contain {1, 2} since these would be more naturally treated in the context of consecutive patterns, see e.g., Elizalde and Noy [10].

An important property of the set of bivincular patterns, as noted by Bousquet-Mélou et al. [4], is that it is closed under the symmetries of the square. The set of patterns we are interested in—the union of vincular and covincular patterns—is also closed under these symmetries, and we make the following observation.

Lemma 3. Let π be a permutation and p be a pattern, and let π^{∗} and p^{∗} be the permutation and pattern with the same symmetry applied to both π and p. Then π avoids p if and only if π^{∗} avoids p^{∗}.

From this we immediately see that if we can find the enumeration of Av(p, r), for a single pair of patterns p and r, then we automatically have the enumeration for up to 8 other symmetric cases. This reduces the amount of work to be done considerably. In particular, we need only consider when Y ≠ ∅ as otherwise we could take a symmetry to a case where instead X = ∅. Let

P = { (σ, X, ∅) : σ ∈ S_{3}, X ∈ {∅, {1}, {2}} };
R = { (σ, ∅, Y) : σ ∈ S_{3}, Y ∈ {{1}, {2}} }

In total we have |P × R| = (3! · 3) · (3! · 2) = 216 pairs of patterns to consider. In Table 1 we summarize our results on permutations avoiding a pair of patterns from P × R.

Enumeration  # pairs OEIS
C_{n}  24  \underline{A000108}
\binom{n}{2} + 1  16  \underline{A000124}
2^{n−1}  104 \underline{A000079}
∑_{i=0}^{n}^{\binom{\binom{i+1}{2}}{n − i}}  8  \underline{A121690}
∑_{k=0}^{n}^{\binom{\binom{k+1}{2} + n − k − 1}{n − k}}  8  \underline{A098569}
M_{n}  16  \underline{A001006}
OGF: 1 + ∑_{n≥0} x^{n+1}L_{n}(1 + x)  8  \underline{A249560}
OGF: 1 + \frac{x}{1−x} ∑_{n≥0} ∑_{k=0}^{n+1} x^{i+k}L_{n+1,k} (\frac{1}{1−x})  8  \underline{A249561}
a recurrence relation  8  \underline{A249563}
a recurrence relation  4  \underline{A249562}
finite  12  -

Table 1: The number of permutations avoiding a pair of patterns in P × R.

In Table 1, C_{n} and M_{n} are the Catalan and Motzkin numbers, respectively. The sequences \underline{A249560}–\underline{A249563} were added to the OEIS [18] by the authors. In \underline{A249560} and \underline{A249561}, L_{n}(q) = ∑_{m=0}^{n} \left[{n \atop m}\right]_{q} and L_{n,k}(q) = q^{n+\binom{k}{2}}\left[{n−1 \atop k−1}\right]_{q} enumerate specific types of lattice paths and their areas.

It is sometimes possible to show that avoiding a given pattern p is equivalent to avoiding a simpler pattern p′. The following lemma states three instances of this that are used here. This lemma is part of a more general result called the shading lemma, due to Hilmarsson et al. [12, Lemma 3.11].

We first need to introduce the idea of a mesh pattern. In our previous pictures we shaded entire rows or columns. In a mesh pattern we can shade individual squares in the diagram. As an example, below is a mesh pattern with a single square shaded:

.

A subsequence π(i)π(j)π(k) of π ∈ S_{n}, that is order isomorphic to 132, is an occurrence of this particular pattern if there does not exist an m such that j < m < k and π(m) < π(i). Mesh patterns satisfy a property analogous to Remark 2: given a pattern p = (σ, B), where B is the set of squares shaded, and p′ = (σ, B′), where B′ ⊆ B, then Av_{n}(p′) ⊆ Av_{n}(p). The original definition of mesh patterns was given by Brändén and Claesson [5].

Lemma 4. (i) Av_{n} (  ) = Av_{n} (  )

(ii) Av_{n} (  ) = Av_{n} (  ) .

(iii) Av_{n} (  ) = Av_{n} (  ) .

Proof. For (i) see [3, Lemma 2] and for (ii) and (iii) see [12, Lemma 3.11].

Remark 5. It is important to note that Av_{n}(132, {2}, ∅) ≠ Av_{n}(132, ∅, ∅). For example, 2413 ∉ Av_{4}(132, ∅, ∅) but 2413 ∈ Av_{4}(132, {2}, ∅).

2 Catalan numbers (\underline{A000108} )

There are 24 pairs (p, r) ∈ P × R such that |Av_{n}(p, r)| = C_{n}. These break down to five cases once symmetries are considered; see Table 2 in the Appendix for a full list. They can all be simplified to the avoidance of a single classical pattern. We look at a case for each argument. By Remark 2 we have:

Proposition 6. Av_{n} (  ,  ) = Av_{n}(123).

Similarly, by first using Lemma 4i on the first pattern and then using Remark 2 on the resulting pair we have:

Proposition 7. Av_{n} (  ,  ) = Av_{n}(132).

It is well known that the enumeration for avoiding any classical pattern of length 3 is given by the Catalan numbers; see Knuth [14, Section 2.2.1, Exercises 4 and 5]. Thus the sets in the propositions above all have cardinality C_{n}. In Section 11 we present a new proof that |Av_{n}(123)| = C_{n}.

The rest of the pairs that are counted by the Catalan numbers all follow a very similar argument so we move on to the next case.

3 Central polygonal numbers (\underline{A000124} )

After considering symmetries there are three pairs (p, r) ∈ P×R such that |Av_{n}(p, r)| = \binom{n}{2}+ 1; see Table 2 in the Appendix. They all reduce to the already known case |Av_{n}(123, 231)| = \binom{n}{2} + 1 done by Simion and Schmidt [17].

Proposition 8. Av_{n} (  ,  ) = Av_{n}(123, 231).

Proof. Use symmetry and Lemma 4i.

Proposition 9. Av_{n} (  ,  ) = Av_{n}(123, 231).

Proof. After applying Lemma 4 we see that the set we are interested in is

B = Av (  ,  ) .

We want to show that B is equal to A = Av(123, 231). It is clear than A ⊆ B. We will show B ⊆ A by contraposition. Assume that π ∉ A. If π contains 231 then it immediately follows that π ∉ B. If π contains 123 then either π contains

in which case π ∉ B, or else it contains the pattern where there is a point in the shaded square. This would create an occurrence of 1342 which contains an occurrence of 231 and hence we would have π ∉ B. Therefore A = B.

Proposition 10. Av_{n} (  ,  ) = Av_{n}(123, 231).

Proof. Apply Lemma 4i and then Proposition 9.

4 Powers of 2 (\underline{A000079} )

After considering symmetries there are 19 different pairs (p, r) ∈ P ×R such that Av_{n}(p, r) = 2^{n−1} and we list them in Table 2 of the Appendix. Most of the cases reduce to

|Av_{n}(123, 132)| = |Av_{n}(132, 312)| = |Av_{n}(231, 312)| = 2^{n−1},

as shown by Simion and Schmidt [17]. There are two non-trivial cases where we use the structure of the set to find a generating function for the enumeration.

Proposition 11. Let p =  and r =  . The number of permutations in
Av_{n}(p, r) is 2^{n−1}, for n ≥ 1.

Proof. Let A be the set of avoiders in question and let π ∈ A. As π avoids p, the points after the minimum of π form a decreasing sequence. Moreover, in order to ensure that the permutation avoids r, every point to the right of the minimum must be greater than every point on the left of the minimum. Therefore, all non-empty permutations of A have the form

A

where A symbolizes a (possibly empty) permutation which avoids the patterns, and symbolizes a decreasing permutation. As the structure is so rigid we can find the ordinary generating function of the avoiders by multiplying together the ordinary generating functions of the component parts. There is one decreasing permutation of length n and so the ordinary generating function is 1/(1 − x). The ordinary generating function of a single point is x. If A is the ordinary generating function for A, then it follows that

A = A · x · \frac{1}{1 − x} + 1

where we add 1 for the empty permutation which trivially avoids both patterns. Rearranging we get

A = \frac{1 − x}{1 − 2x} = 1 + ∑_{n≥1} 2^{n−1}x^{n}.

Proposition 12. Let p =  and r =  . The number of permutations in

Av_{n}(p, r) is 2^{n−1}, for n ≥ 1.

Proof. Let A be the set of avoiders in question. Consider the leftmost point ℓ of a permutation in A. To avoid p the points greater than ℓ must form a decreasing sequence and similarly to avoid r the points less than ℓ must form decreasing sequence. Therefore the permutations in A have the form below.

A permutation matching this picture cannot contain an occurrence of p = 123, and every occurrence of 312 will have the point ℓ preventing it from being an occurrence of r. Hence these can be encoded with binary strings and so there are 2^{n−1} such permutations.

5 Left-to-right minima boundaries (\underline{A121690} )

After symmetries there is exactly one pair (p, r) ∈ P × R enumerated by the formula in the following proposition.

Proposition 13. Let p =  and r =  . The number of permutations in

Av_{n}(p, r) is ∑_{k=0}^{n} \binom{\binom{k+1}{2}}{n − k}.

(a)  (b)  (c)

Figure 2: The structure of Av_{n}(p, r) from Proposition 13

In the following proof we will consider the set of left-to-right minima, which we call the boundary of the permutation. In later sections we will consider other types of boundaries that use left-to-right minima, right-to-left minima or right-to-left maxima and perhaps unions of these. It should be clear from context which type of boundary it is.

Proof. Consider the minimum point, 1, of a permutation in Av_{n}(p, r). From the pattern p we see that the points to the right of 1 form a decreasing sequence. Moreover, the points vertically between any two adjacent points on the boundary must form a decreasing sequence, giving the structure in Figure 2a, where the permutation we have drawn has five left-to-right minima.

Now, consider the leftmost point, say ℓ, of a permutation in Av_{n}(p, r). From the pattern r we see that the points greater than ℓ must form an increasing sequence. Moreover, considering the points horizontally between any two adjacent points on the boundary we get the structure in Figure 2b, where, again, the permutation has five left-to-right minima. When we overlay the given conditions above we get the structure in Figure 2c, where each of the squares in the diagram must be both increasing and decreasing. Therefore each square must be empty or contain a single point. Also, the structure of the rows and columns will be determined as increasing and decreasing, respectively, no matter which squares have points. Therefore, placing any number of points into the squares (at most one in each) will create a unique permutation (see Figure 3). Create a permutation π ∈ Av_{n}(p, r) with k left-to-right

Figure 3: The permutation 673841952 ∈ Av_{9}(p, r) from Proposition 13

minima. We need to know how to place the remaining n − k points. There will be \binom{k+1}{2} squares available to choose from, and placing the n−k points into any subset of those squares will create a unique permutation. Thus, summing over the number of left-to-right minima, we get

|Av_{n}(p, r)| = ∑_{k=0}^{n} \binom{\binom{k+1}{2}}{n − k}.

We note from the above proof and the formula that a permutation with k left-to-right minima will be of length at most k + \binom{k+1}{2}. Also, a length n avoider will have at least

⌈\frac{−3+\sqrt{9+8n}}{2}⌉ left-to-right minima.

6 Barred patterns (\underline{A098569} )

After considering symmetries there are two pairs (p, r) ∈ P × R enumerated by the formula in the following proposition.

Proposition 14. Let p =  and r =  . The number of permutations in

Av_{n}(p, r) is ∑_{k=0}^{n} \binom{\binom{k+1}{2} + n − k − 1}{n − k}.

Proof. Consider the left-to-right minima of a permutation π ∈ Av_{n}(p, r) as we did in Proposition 13. The points vertically between any two adjacent left-to-right minima must form a decreasing sequence and the points horizontally between any two adjacent left-to-right minima must also form a decreasing sequence. If we overlay these two conditions we get a structure like that in Figure 2c, where, in this case, each of the squares in the diagram must be decreasing. Also, the structure of the rows and columns will be determined as decreasing no matter which squares have points. Therefore, placing any number of points into the squares will create a unique permutation, and so the ordinary generating function for |Av_{n}(p, r)| is

∑_{k≥0} x^{k} (\frac{1}{1 − x})^{\binom{k+1}{2}} .

The coefficient of x^{j} in 1/(1 − x)^{m} is \binom{m+j−1}{j} which concludes the proof.

It is possible to show that avoiding the two patterns p and r, above, is equivalent to avoiding a single barred pattern first introduced by West [20]. For a more detailed account of barred patterns see Pudwell [15]. The following is the definition which can be found in that reference.

Definition 15. (Pudwell [15, p. 1]) Let p be a barred pattern. Let r be the pattern with the bars removed and let p′ be the permutation order isomorphic to the pattern in which the barred numbers are removed. We say that a permutation contains p if every occurrence of p′ can be extended to an occurrence of r.

For example, a permutation contains ¯425¯13 if every occurrence of 132 is contained as 253 in a 42513 pattern. Barred patterns can often be thought of as mesh patterns (see Ulfarsson [19, p. 5]). For instance,

Av_{n}(¯423¯15) = Av_{n} (  ,  ) = Av_{n} (  ,  )

and

Av_{n}(¯425¯13) = Av_{n} (  ,  ) = Av_{n} (  ,  ) ,

where the second equalities in both equations follow from Lemma 4

Corollary 16. The number of permutations in Av_{n} (¯423¯15) is

∑_{k=0}^{n} \binom{\binom{k+1}{2} + n − k − 1}{n − k}.

This confirms the conjecture from Pudwell [15, page 8] that ¯425¯13 and ¯423¯15 are Wilfequivalent, i.e., that the number of permutations avoiding either one is the same. If we were to apply the same method as in the proof of Proposition 14 to

Av_{n} (  ,  ) = Av_{n}(¯425¯13)

then we would have a similar structure with the left-to-right minima, where, however, we get increasing sequences in the squares and along the rows and columns.

7 Motzkin numbers (\underline{A001006} )

The Motzkin numbers, M_{n}, form a well known sequence which can be defined by a functional equation their ordinary generating function satisfies:

M = 1 + xM + x^{2}M^{2} where M = ∑_{n≥0} M_{n}x^{n}.

For more information on Motzkin numbers see e.g., OEIS [8]. After considering symmetries and Lemma 4 we have two cases such that |Av_{n}(p, r)| = M_{n} and (p, r) ∈ P × R. For a full list see Table 2 of the Appendix.

Proposition 17 (Elizalde and Mansour [9]). Let p =  and r =  . The number of

permations in

Av_{n}(p, r) is M_{n}.

The proof given by Elizalde and Mansour [9] provides a bijection between Av_{n}(p, r) and Motzkin paths. We show that the structure of the permutations implies they are enumerated by the Motzkin numbers.

Proof. Consider a permutation π in A = Av(p, r). Further, consider the rightmost point of π. For π to avoid p the structure of π must be like Figure 4a. With regard to σ, let us

\begin{matrix}A \\ σ \end{matrix} ; (a)  \begin{aligned}A \\ & (b) \end{aligned}  \begin{matrix}A \\ A \end{matrix} ; (c)

Figure 4: The structure of Av(p, r) from Proposition 17

consider two cases. Either σ is empty or it has at least one point. If σ is empty the structure looks like Figure 4b. If σ is non-empty then consider the maximum point, m, of σ. If there was a point to the left of m in σ then this point together with m and the rightmost point of π would create an occurrence of r. Therefore there must be no points to the left of m in σ. Thus we can place any possibly empty smaller permutation in A to the right of the maximum of σ without creating an occurrence of p or r, and so we have the structure in Figure 4c.

In conclusion, any non-empty permutation in A either has a structure described by Figure 4b or a structure described by Figure 4c. Letting A denote the ordinary generating function for A we thus have A = 1 + xA + x^{2}A^{2}, from which the claim follows.

We now go on to the second case. We will consider the structure of the avoiders in terms of the left-to-right minima, as in Proposition 13.

Proposition 18. Let p =  and r =  . The number of permutations in
Av_{n}(p, r) is M_{n}.

Proof. Let π ∈ Av_{n}(p, r) and consider the boundary of (the diagram of) π given by the left-to-right minima. As in Proposition 13, any cell in the diagram must be both increasing and decreasing and so the cell is empty or contains exactly one point. Because the rows are increasing and π avoids 123 there can be at most one point in each row. Moreover, if there is a point in a cell then we cannot place a point in a cell further to the right and above.

Pick the leftmost point in the leading diagonal of this grid. The points above this cell will then form a subword of π which is of shorter length and also avoids both patterns. The points below this cell will similarly form a subword which avoids both patterns; see Figure 5. Notice that this process is reversible: we can take a pair of avoiders of lengths k and n−k−2,

A ; B ; C ; D ; E ; F ; · ; G ; H ; I  ↦ A B C D E F  + G H I

Figure 5: Decomposing a permutation in Av_{n}(p, r) from Proposition 18

respectively, and glue them together by adding the leftmost point on the leading diagonal and the corresponding left-to-right minimum in this way.

There is also the case when there are no points on the leading diagonal directly to the right of a left-to-right minima. In this case we remove the minimum point and tuck the

A B C D E F G H I J ↦ A B C D E F G H I J

Figure 6: “Shortening” a permutation in Av_{n}(p, r) from Proposition 18

points in the same way we did for the top half of the previous case, producing an avoider which is shorter in length; see Figure 6. Again this is reversible, so we can take any length n − 1 avoider and append a new minimum to create a length n avoider. Thus, letting A be the ordinary generating function for A we get that A = 1 + xA + x^{2}A^{2}.

We will use a similar method to give a new proof of the enumeration of Av_{n}(123) in Section 11.

8 Lattice paths and their area (\underline{A249560} )

Up to symmetries there is a single pair (p, r) in P × R with the enumeration given in Proposition 20, namely

A_{n} = Av_{n} (  ,  ) .

To find the enumeration of this set we consider a different boundary than those seen in previous sections. Our boundary here will be left-to-right minima and right-to-left minima. We will first find a bijection between lattice paths and the boundaries of permutations in A_{n}. Then we extend this bijection by considering the area under these paths.

For our purposes a lattice path of length n is a path that starts at (0, 0) and has n steps, each of which is

N : (x, y) ↦ (x, y + 1) or

E : (x, y) ↦ (x + 1, y).

Clearly there are 2^{n} paths of length n. The following result is due to Simion and Schmidt [17], but we give a proof that is different from theirs.

Proposition 19 (Simion and Schmidt [17]). There is a bijection between the length n − 1 lattice paths and the permutations in Av_{n}(231, 132).

Proof. For π ∈ Av_{n}(231, 132) define the path w = x_{n}x_{n−1} ⋯ x_{2} by

x_{k} = \begin{cases}N & if π^{−1}(k) < π^{−1}(1) i.e., k appears to the left of 1, \\ E & otherwise. \end{cases}

To see that π ↦ w is invertible note that the points to the left of the minimum of π form a decreasing sequence, and, similarly, the points to the right of the minimum form an increasing sequence. Thus, any permutation π ∈ Av_{n}(231, 132) is uniquely specified by the set {i : π^{−1}(i) < π^{−1}(1)} which coincides with the set {i : x_{i} = N}.

For example,

π = 975431268 = ↦ NENENNNE = \begin{matrix}y \\ x \end{matrix}

Every lattice path defines an area enclosed by the path and the x-axis. We use q-binomials to record this, see e.g., Azose [2] for more details. In terms of q-binomial coefficients the number of length n paths, with m E-steps, is given by \left[{n \atop m}\right]_{q} where the coefficient of q^{k} is the number of paths with area k. Let

L_{n}(q) = ∑_{m=0}^{n} \left[{n \atop m}\right]_{q},

which is the distribution of area over all length n paths. We will now link this to pattern avoidance.

Proposition 20. Let p =  and r =  . The ordinary generating function for

Av_{n}(p, r) is 1 + ∑_{n≥0} x^{n+1}L_{n}(1 + x).

Proof. Taking the left-to-right minima and right-to-left minima boundary of any permutation produces a permutation in the set Av_{n}(231, 132). Consider a particular boundary of rightto-left minima and left-to-right minima of a permutation avoiding p and r. To avoid p the points to the left of the minimum form a decreasing sequence and hence there are no other points in this region; also, the columns in between the right-to-left minima are forced to be increasing. To avoid r, the rows in between the right-to-left minima must be decreasing, and the rows directly above a left-to-right minimum must be empty. As an example, for the boundary given by π = 975431268 we get the following restrictions.

In each of the unshaded squares we can place either a single point or leave it empty, and each such choice will create a unique permutation. The number of unshaded squares is given by the area under the lattice path corresponding to the boundary as in Proposition 19. For example, in π = 975431268 the three unshaded boxes in the top row correspond to the three squares in the bottom row of the area under its corresponding lattice path. This is because there are three left-to-right minima (excluding 1), which ensures three E steps in the lattice path, and 9 appears at the beginning of π ensuring a N step at the start of the path.

Hence, to count permutations in Av(p, r) we first fix the size of boundary, say n + 1, giving the factor x^{n+1}. Then we substitute q = 1 + x into L_{n}(q), since this is the generating function for all length n+1 boundaries with q marking the squares that we can place a point in or leave empty.

9 Partitions into distinct parts (\underline{A249561} )

Up to symmetries there is a single pair (p, r) in P × R with the enumeration given in Proposition 25, namely

A = Av(p, r) = Av (  ,  ) .

To find the enumeration of this set we consider the boundary of a permutation π ∈ A given by its right-to-left maxima and right-to-left minima. Taking this boundary of any permutation will result in a permutation that avoids 231 and 213. Since avoiding 231 implies avoiding r by Remark 2 it is clear that any such boundary for a permutation in A is in the set

A′ = Av (  ,  ,  ) .

If we take π′ ∈ A′ and consider the restrictions implied by p and r, we see that the number of right-to-left maxima between the two rightmost right-to-left minima does not change the number of unshaded squares (see Figure 7).

Figure 7: The boundaries given by 15423 and 1762543

We therefore start by considering π′ ∈ A′, where π′(n − 1) = π′(n) − 1, i.e. with a single right-to-left maximum after the rightmost left-to-right minimum. In terms of pattern avoidance these boundaries are given by the set

B_{n} = Av_{n} (  ,  ,  ,  ) ⊆ A′_{n}.

Here the last pattern ensures that the condition π′(n − 1) = π′(n) − 1 is enforced.

We will now show that the permutations in B_{n} are in bijection with a subset of lattice paths.

Definition 21. Let w = x_{1}x_{2} ⋯ x_{n} be a lattice path. We say w is a restricted lattice path if

(i) x_{1} = N,

(ii) x_{n} = E and

(iii) for all i ∈ {1, …, n − 1} we have x_{i}x_{i+1} ≠ EE.

We define R_{n} to be the set of all restricted lattice paths of length n.

Remark 22. A restricted lattice path, w, represents a unique integer partition since w starts with an N step and ends with an E step. As there are no two consecutive E steps in w we can never have two columns of the same height, so it corresponds to an integer partition with distinct parts.

Proposition 23. There is a bijection between the restricted lattice paths in R_{n} and the permutations in B_{n}.

Proof. Let π ∈ B_{n}. Define the path w = Nx_{1}x_{2} ⋯ x_{n−1} by

x_{k} = \begin{cases}N & if π^{−1}(k) > π^{−1}(n), \\ E & if π^{−1}(k) < π^{−1}(n). \end{cases}

By definition the path w starts with an N step. Also, π ends with an ascent, and so x_{n−1} = E. That w does not contain EE can be seen by contraposition: Assume that x_{i}x_{i+1} = EE, then π^{−1}(i) < π^{−1}(n) and π^{−1}(i+1) < π^{−1}(n) which means that π either contains the subsequence (i, i+1, n) or it contains the subsequence (i+1, i, n). In the latter case we have an occurrence of 213 and we are done, so assume the former. If i and i + 1 are adjacent in π then we have an occurrence of p. If not, then there must be a point in one of the lower three squares of the shading of p. But each of these three options leads to an occurrence of p or 213. This shows that the range of the mapping π ↦ w is contained in R_{n}. To see that π ↦ w is invertible we can reason in a way that is similar to the proof of Proposition 19.

Remark 24. Let λ be the integer partition obtained from applying the above bijection to the permutation π. By Remark 22 it is clear that λ has distinct parts. The number of points greater than π(n) is one less than the maximum part of λ and the number of points less than π(n) is the number of parts of λ. See Figure 8 for an example.

↔ \begin{matrix}y \\ x \end{matrix} ↔ 2 + 3 + 6

Figure 8: The boundary given by the permutation 918276534 with the corresponding lattice path and integer partition with distinct parts

Partitions are well studied objects (see e.g., Andrews [1]) and it can be shown that if q keeps track of the sum of the parts then the number of partitions with maximum part n into k distinct parts is given by

L_{n,k}(q) = q^{n+\binom{k}{2}}\left[{n − 1 \atop k − 1}\right]_{q}.

Proposition 25. Let p =  and r =  . The ordinary generating function for

A = Av(p, r) is 1 + \frac{x}{1 − x} ∑_{n≥0} ∑_{k=0}^{n+1} x^{i+k}L_{n+1,k} (\frac{1}{1 − x}) .

Proof. Let π ∈ A. Consider the boundary given by right-to-left maxima and right-to-left minima. As before we assume that π(n − 1) = π(n) − 1 and thus the boundary is in B_{n}. To avoid r the points above π(n) must form a decreasing sequence. There must also be no points between a right-to-left minimum and right-to-left minimum in order to avoid p. In the remaining unshaded regions, columns are decreasing (to avoid p) and rows are decreasing (to avoid r). Thus, an unshaded square can contain a decreasing sequence of any length. The bijection in Proposition 23 gives a bijection that defines the available squares, and, considering Remark 24, it follows that the ordinary generating function for A is as claimed.

10 Recurrence relations (\underline{A249562} & \underline{A249563} )

We enumerate the two remaining pairs (p, r) ∈ P × R with recurrence relations.

10.1 A recurrence for \underline{A249563}

The set we are enumerating is

Av_{n}(p, r) = Av_{n} (  ,  ) .

Let π ∈ Av_{n}(p, r). Write π = m_{1}T_{1}m_{2}T_{2} ⋯ m_{k}T_{k} where m_{1}, m_{2}, …, m_{k} are the left-to-right minima of π, and T_{1}, T_{2}, …, T_{k} are the remaining points in between the minima. To avoid p each T_{i} must be increasing. We call m_{i}T_{i} the ith block of π.

Assume that π has an occurrence of the pattern . Because π avoids r there cannot be any points above and to the right of this occurrence. This motivates the following definition.

Definition 26. For a permutation π ∈ Av_{n}(r), if there exists i and j such that j > i and π(i) = π(j) − 1 then we call π(j) a ceiling point.

Going back to analyzing the structure of π ∈ Av_{n}(p, r), notice that if we remove the maximum, n, from π then the resulting permutation will be in Av_{n−1}(p, r). This gives us ground for a recursion. Consider inserting n into a permutation in Av_{n−1}(p, r). Where we can place n depends on several factors. Let a_{n,k,i,ℓ} be the number of avoiders where n is the length of the permutation; k is the number of blocks; i is the block that the maximum is in and ℓ is the block containing the leftmost ceiling point; if there is no ceiling point then we let ℓ = 0.

It is clear that we can have at most n blocks and that n cannot occur after the leftmost ceiling point. Therefore if n < k or i > ℓ (while ℓ > 0) then a_{n,k,i,ℓ} = 0. There is a unique length n permutation with n blocks, namely the decreasing one. The maximum is in the first block (except when n = 0, in which case there is no maximum so we let i = 0), hence we have

a_{n,n,1,0} = 1 = a_{0,0,0,0}.

We have three cases to consider. The new maximum, n, is inserted to become a ceiling point (this is when i = ℓ); n is inserted to create a new block (when i = 1) or n is inserted into an existing block but is not a ceiling point.

We first consider inserting n into a length n − 1 permutation so as to ensure n is a ceiling point. It must be placed after the current maximum but before the leftmost ceiling point. If the smaller permutation has no ceiling point then we can freely insert n. Hence

a_{n,k,ℓ,ℓ} = a_{n−1,k,1,0} + ∑_{j=1}^{i} ∑_{m=i+1}^{k} a_{n−1,k,j,m}.

Now we consider inserting n so it is not a ceiling point. We may either create a new block (when i = 1) or place it into an already existing block. Consider inserting it into an existing block, then it cannot be placed after the current maximum or else it will become a ceiling point. The leftmost ceiling point will carry over to the larger permutation. Therefore, if i < ℓ,

a_{n,k,i,ℓ} = ∑_{j=i+1}^{k} a_{n−1,k,i,ℓ}.

To create a new block we can add n to any length n − 1 avoider but there will of course be a shift of indices. If i = 1 we get

a_{n,k,i,ℓ} = ∑_{j=i+1}^{k} a_{n−1,k,j,ℓ} + ∑_{j=0}^{k−1} a_{n−1,k−1,j,ℓ−1}.

This, with the initial conditions, gives a recursion for a_{n,k,i,ℓ}.

Proposition 27. Let p =  and r =  . The number of permutations in Av_{n}(p, r)

is given by

{∑_{k=0}^{n} ∑_{i=0}^{k} ∑_{ℓ=0}^{k} a_{n,k,i,ℓ}}_{n≥0} = {1, 1, 2, 4, 9, 22, 57, 156, 447, 1335, 4140, …}.

This sequence was added to the OEIS by the authors [18, \underline{A249563}].

10.2 A recurrence for \underline{A249562}

Here we enumerate the set

Av_{n}(p, r) = Av_{n} (  ,  ) .

Let π ∈ Av_{n}(p, r). Write π = m_{1}T_{1}m_{2}T_{2} ⋯ m_{k}T_{k} where m_{1}, m_{2}, …, m_{k} are the left-to-right minima of π, and T_{1}, T_{2}, …, T_{k} are the remaining points in between the minima. To avoid p each T_{i} must be decreasing. We call m_{i}T_{i} the ith block of π. Notice that removing n from π will result in a permutation in Av_{n−1}(p, r). Therefore we will build these permutations recursively by adding in a new maximum.

We set up as follows: let n be the length of the permutation; let k be the number of blocks; let i be the position of the maximum; and let ℓ be the position of the leftmost ceiling point (if there are no ceiling points we set ℓ = 0). Let â_{n,k,i,ℓ} be the number of avoiders where the maximum is a ceiling point; let ā_{n,k,i,ℓ} be the number of avoiders where the maximum is a left-to-right minimum; and let ǎ_{n,k,i,ℓ} be the number of avoiders where the maximum is neither a ceiling point nor a left-to-right minimum. Then we are interested in

a_{n,k,i,ℓ} = â_{n,k,i,ℓ} + ā_{n,k,i,ℓ} + ǎ_{n,k,i,ℓ}.

First consider adding the maximum as a ceiling point. If we want to add n to the first block then we must have m_{1} = n − 1 and the leftmost ceiling point can be anywhere. Therefore,

â_{n,k,1,ℓ} = ∑_{m=0}^{k} ā_{n−1,k,1,m}.

Otherwise we want to add n to any of the other blocks. We can do this to a permutation starting with a maximum as long as it is before the leftmost ceiling point. If the previous maximum is not a ceiling point then we must add it after the maximum but before the leftmost ceiling point. We cannot create a new maximum ceiling point if the previous one is already a ceiling point. Hence, if i > 1,

â_{n,k,i,ℓ} = ∑_{m=ℓ}^{k} ā_{n−1,k,1,m} + ∑_{j=1}^{i−1} ∑_{m=i}^{k} ǎ_{n−1,k,j,m}.

We can add a maximum to the far left of any length n − 1 avoider to create a length n avoider, so we get

ā_{n,k,i,ℓ} = ∑_{j=1}^{k−1} a_{n−1,k−1,j,ℓ−1}.

We can add a new maximum to an existing block so that it is not a ceiling point as long as it comes before the current maximum, so

ǎ_{n,k,i,ℓ} = ∑_{j=i}^{k} â_{n−1,k,j,ℓ} + ǎ_{n−1,k,j,ℓ}.

This together with ā_{n,n,1,0} = 1, â_{n,n−1,i,ℓ} = 1, and the conditions that n > k > i and i < ℓ is enough to enumerate these permutations recursively.

Proposition 28. Let p =  and r =  The number of permutations in Av_{n}(p, r)

is given by

{∑_{k=0}^{n} ∑_{j=0}^{k} ∑_{ℓ=0}^{k} a_{n,k,i,ℓ}}_{n≥0} = {1, 1, 2, 5, 14, 43, 143, 509, 1921, 7631, 31725, …}.

This sequence was added to the OEIS by the authors [18, \underline{A249562}].

11 Avoiding 123

It is well known that |Av_{n}(123)| = C_{n} = \binom{2n}{n}/(n + 1), the nth Catalan number. Inspired by Sections 6 and 7 we shall derive this fact in a alternative way.

Proposition 29 (Hammersley [11], Rogers [16]). |Av_{n}(123)| = C_{n}.

Proof. Given a permutation avoiding 123 we can use its left-to-right minima to partition the remaining points into cells. Each cell must be decreasing and the same is true for each row and each column, as noted by Claesson and Kitaev [6]. Therefore the permutation is uniquely determined by the number of points in each cell. If a cell is non-empty then all the cells strictly above and strictly to the right of it will be empty. See e.g., Figure 9 where we have five left-to-right minima and are assuming that A ≠ ϵ. This property allows us to

A

Figure 9: An avoider of 123 with five left-to-right minima where A ≠ ϵ

construct a larger avoider from two smaller ones. See Figure 10 where F′ has one more point

\begin{matrix}A \\ B \\ C \\ D \\ E \\ F \end{matrix}  + \begin{matrix}G \\ H \\ I \\ J \\ K \\ L \end{matrix}  ↦ _{A B C D E F′ G H IJ K L}

Figure 10: The sum of two 123-avoiding permutations

than F. If we are adding the empty permutation, on the left, we instead add a left-to-right minimum. See Figure 11. This construction is reversible. Therefore, if we let A be the generating function then it is clear that it will satisfy A = 1 + x(A − 1)A + xA = 1 + xA^{2}, which is the defining functional equation for the ordinary generating function of the Catalan numbers.

We would like to thank the referee for his detailed comments and suggestions.

ϵ + \begin{matrix}G \\ H \\ I \\ J \\ K \\ L \end{matrix} ↦ \begin{matrix}G \\ H \\ I \\ J \\ K \\ L \end{matrix}

Figure 11: The sum of the empty permutation and a 123-avoiding permutation

Appendix

In the tables below the column titled “Method” indicates the argument to confirm the enumeration. In some cases these links are to a proposition or lemma with the patterns, and in others to a similar case where the same or a similar argument is used.

Method  p  r  |Av_{n}(p, r)|
Prop. 6  (123, ∅, ∅) (123, ∅, {1})  C_{n}
(132, ∅, ∅) (132, ∅, {1})
(132, ∅, ∅) (132, ∅, {2})
Prop. 7  (132, {1}, ∅) (132, ∅, {1})  C_{n}
(132, {1}, ∅) (132, ∅, {2})
Prop. 6  (123, ∅, ∅) (231, ∅, \{1\}) \binom{n}{2} + 1
Prop. 9  (132, ∅, ∅) (321, ∅, \{1\}) \binom{n}{2} + 1
Lemma 4 and Prop. 9 (123, \{2\}, ∅) (231, ∅, \{1\}) \binom{n}{2} + 1
Prop. 6  (123, ∅, ∅) (132, ∅, {1})  2^{n−1}
(132, ∅, ∅) (213, ∅, {2})
(132, ∅, ∅) (231, ∅, {1})
(132, ∅, ∅) (312, ∅, {2})
Prop. 7  (132, {1}, ∅) (213, ∅, {2})  2^{n−1}
(132, {1}, ∅) (231, ∅, {1})
Prop. 9  (132, ∅, ∅) (123, ∅, {1})  2^{n−1}
(132, ∅, ∅) (213, ∅, {1})
(132, ∅, ∅) (231, ∅, {2})

(132, ∅, ∅) (312, ∅, {1})
Lemma 4 and Prop. 9 (123, {1}, ∅) (132, ∅, {1})  2^{n−1}
(132, {1}, ∅) (213, ∅, {1})
(132, {1}, ∅) (231, ∅, {2})
(132, {1}, ∅) (312, ∅, {1})
Prop. 11 (123, {2}, ∅) (312, ∅, {2}) 2^{n−1}
(132, ∅, ∅) (321, ∅, {2})
(132, {2}, ∅) (213, ∅, {1})
Prop. 12 (123, ∅, ∅) (231, ∅, {2}) 2^{n−1}
(123, {1}, ∅) (312, ∅, {1})
Prop. 13  (123, \{2\}, ∅) (132, ∅, \{2\}) \underline{A121690}
§ 6  (123, \{1\}, ∅) (123, ∅, \{1\}) \underline{A098569}
(132, {2}, ∅) (132, ∅, {2})
Prop. 17 (132, ∅, ∅) (123, ∅, {2}) M_{n}
Lemma 4 and Prop. 17 (123, {1}, ∅) (213, ∅, {2})  M_{n}
Prop. 18 (123, ∅, ∅) (132, ∅, {2}) M_{n}
Prop. 20  (132, \{2\}, ∅) (231, ∅, \{2\}) \underline{A249563}
Prop. 25  (123, \{1\}, ∅) (231, ∅, \{2\}) \underline{A249561}
§ 27  (123, \{1\}, ∅) (132, ∅, \{2\}) \underline{A249560}
§ 28  (123, \{1\}, ∅) (123, ∅, \{2\}) \underline{A249562}
(123, ∅, ∅) (321, ∅, {1})  finite
(123, {1}, ∅) (321, ∅, {1})
(123, {1}, ∅) (321, ∅, {2})

Table 2: Enumeration of Av_{n}(p, r)

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and its Applications, Vol. 2. Addison-Wesley, 1976.

[2] J. Azose, A tiling interpretation of q-binomial coefficients. Thesis, Harvey Mudd College, 2007.

[3] Eric Babson and Einar Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art. B44b, 18 pp. (electronic).

[4] M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev, (2 + 2)-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117 (2010), 884–909.

[5] P. Brändén and A. Claesson, Mesh patterns and the expansion of permutation statistics as sums of permutation patterns, Electron. J. Combin. 18 (2011), #P5.

[6] A. Claesson and S. Kitaev, Classification of bijections between 321- and 132-avoiding permutations. In 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), Discrete Math. Theor. Comput. Sci. Proc., 2008, pp. 495–506.

[7] A. Claesson and T. Mansour, Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns, Ars Combin. 77 (2005), 17–31.

[8] Robert Donaghey and Louis W. Shapiro, Motzkin numbers, J. Combinatorial Theory Ser. A 23(3) (1977), 291–301.

[9] Sergi Elizalde and Toufik Mansour, Restricted Motzkin permutations, Motzkin paths, continued fractions and Chebyshev polynomials, Discrete Math. 305 (2005), 170–189.

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

[11] J. M. Hammersley, A few seedlings of research, In Proc. 6th Berkeley Symposium on Mathematical Statistics and Probability, Vol. I: Theory of Statistics, Univ. California Press, 1972, pp. 345–394.

[12] I. Hilmarsson, I. Jónsdóttir, S. Sigurðardóttir, L. Viðarsdóttir, and H. Ulfarsson, Wilf-classification of mesh patterns of short length. Preprint, 2014, available at

https://arxiv.org/abs/1409.3165.

[13] Sergey Kitaev, Multi-avoidance of generalised patterns, Discrete Math. 260 (2003), 89– 100.

[14] D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998.

[15] L. Pudwell, Enumeration schemes for permutations avoiding barred patterns, Electron. J. Combin. 17(1) (2010), #P29.

[16] D. G. Rogers, Ascending sequences in permutations, Discrete Math. 22 (1978), 35–40.

[17] R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383–406.

[18] N. J. A. Sloane, The on-line encyclopedia of integer sequences, https://oeis.org.

[19] H. Ulfarsson, Describing West-3-stack-sortable permutations with permutation patterns, Sém. Lothar. Combin. 67 (2011/12), Art. B67d, 20.

[20] Julian West, Sorting twice through a stack, Theoret. Comput. Sci. 117 (1993), 303–313.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: permutation, pattern, covincular, enumeration, Wilf-equivalence.

(Concerned with sequences \underline{A000079}, \underline{A000108}, \underline{A000124}, \underline{A001006}, \underline{A098569}, \underline{A121690}, \underline{A249560}, \underline{A249561}, \underline{A249562}, and \underline{A249563}.)

Received February 14 2017; revised versions received June 9 2017; July 3 2017. Published in Journal of Integer Sequences, July 5 2017.

Return to Journal of Integer Sequences home page.