The permutation classes equinumerous to the Smooth class

Miklós Bóna LACIM Université du Québec à Montréal Montréal, Québec, Canada bona@math.uqam.ca

Submitted April 8, 1998; Accepted June 14, 1998 AMS Classification numbers: 05A05, 05E10

Abstract

We determine all permutation classes defined by pattern avoidance which are equinumerous to the class of permutations whose Schubert variety is smooth. We also provide a lattice path interpretation for the numbers of such permutations.

1 Introduction

Let q = (q_{1}, q_{2}, …, q_{k}) ∈ S_{k} be a permutation, and let k ≤ n. We say that the permutation p = (p_{1}, p_{2}, ⋯, p_{n}) ∈ S_{n} contains a subsequence (or pattern) of type q if there is a set of indices 1 ≤ i_{q_{1}} < i_{q_{2}} < ⋯ < i_{q_{k}} ≤ n such that p(i_{1}) < p(i_{2}) < ⋯ < p(i_{k}). Otherwise we say that p is q-avoiding.

For example, a permutation is 132-avoiding if it doesn’t contain three (not necessarily consecutive) elements among which the leftmost is the smallest and the middle one is the largest.

The enumeration of permutations of length n (or, in what follows, n-permutations) avoiding one given pattern q is a difficult problem and has recently generated a fairly extensive research. See [2] [3] for an overview of these results.

A similar problem is to determine the number of n-permutations avoiding two given patterns at the same time. This is, of course, a much stronger restriction on the permutations, so we can expect more precise results. The cases of pairs of patterns (q_{1}, q_{2}), where |q_{1}| = |q_{2}| = 3, or |q_{1}| = 3, and |q_{2}| = 4 are completely solved. The first instance of this problem which is not arranged yet is when |q_{1}| = |q_{2}| = 4. In this case numerical evidence shows that the sequences S_{n}(q_{1}, q_{2}) are mostly different for different inequivalent pairs (q_{1}, q_{2}). (Two pairs of patterns are said to be equivalent if one can be transformed into the other by reversing, complementing, inverse-taking, or a sequence of these simple transformations). There are, however, some exceptions. One of them is that there are some inequivalent classes counted by the Schröder numbers [5] [8].

In this paper we prove that five inequivalent classes are equinumerous, namely S_{n}(1324, 2143) = S_{n}(1342, 2431) = S_{n}(1342, 3241) = S_{n}(1342, 2314) = S_{n}(1324, 2413). There are no more inequivalent pairs (q_{1}, q_{2}) for which the values of S_{n}(q_{1}, q_{2}) for n = 1, 2, ⋯, 7 are 1,2,6,22,88,366,1552, so our results determine all classes counted by this sequence.

One of these classes, that of (1324, 2143)-avoiding permutations is equivalent to the class of smooth permutations. A permutation w is called smooth if the Schubert cell indexed by w is smooth, and this is equivalent to w being (3412,4231)-avoiding. A generating function F (x) for smooth permutations has been obtained in [4]. In [6] a recursive formula is given for a pair equivalent to (1342,2431), from which it is easy to obtain a generating function, and see that it coincides with F (x). Our results concerning the three other pairs are, according to our best knowledge, new.

2 The five inequivalent pairs

We are going to examine all five inequivalent permutation classes, and we show that they all have the same generating functions. We are also presenting a simple lattice path interpretation for these numbers.

We are going to use the well-known facts that the number of permutations avoiding any one given pattern of length 3 is c_{n} = \binom{2n}{n}/(n + 1), the nth Catalan number, and that there is a natural bijection between these permutations and lattice paths from (0, 0) to (j, j) using steps (0, 1) and (1, 0) which never go above the main diagonal. Also, let C(x) = ∑_{n≥0} c_{n}x^{n} = \frac{1−\sqrt{1−4x}}{2x}. We start our study with the two pairs on which work has been done earlier.

1. The pair (1324,2143) This is the pair which is equivalent to the smooth permutations defined in the Introduction. Let v(n) be the number of such n-permutations, and let V (x) = ∑_{n≥0} v(n)x^{n}. Then it is known [1] [4] [7] that

V (x) = \frac{1}{1 − x − \frac{x^{2}}{1−x} (\frac{2x}{1+x−(1−x)C(x)} − 1)}  (1)

= \frac{1 − 5x + 3x^{2} + x^{2}\sqrt{1 − 4x}}{1 − 6x + 8x^{2} − 4x^{3}}  (2)

2. The pair (1342, 2431)

Lemma 1 Let f(n) = S_{n}(1342, 2431). Then f(n) = v(n) for all nonnegative integers n.

Proof: Stankova [6] examined the equivalent pair (3214,4123) and obtained the following recursive formula for the numbers f(n), for n ≥ 3.

f(n) = 2f(n − 1) + ∑_{i=1}^{n−2} c_{i}f(n − i).  (3)

Let F (x) = ∑_{n≥0} f(n)x^{n}, with f(0) = 1. Formula (3) gives rise to the generating function identity

F (x) − 2xF (x) = (C(x) − 1)(F (x) − x − 1) + 1 − x

and hence we get

F (x) = 1 + \frac{x}{1 − \frac{2x}{2−C(x)}} = \frac{1 − 5x + 3x^{2} + x^{2}\sqrt{1 − 4x}}{1 − 6x + 8x^{2} − 4x^{3}},  (4)

which agrees with the generating function (2) of smooth permutations. So v(n) = f(n) for all n. ◇

Remarks:

• The proof of (3) in [6] was based on the observation that there is a natural bijection between these permutations, (if their maximal entry is not in the leftmost or rightmost position), and ordered pairs (P, A) so that P is a partition of the set {1, 2, ⋯ n − 1} into disjoint intervals I_{1} = {1, 2, ⋯ l_{1}}, I_{2} = {l_{1} + 1, l_{1} + 2, ⋯ l_{2}}, ⋯ I_{k} = {l_{k−1} + 1, l_{k−1} + 2, ⋯, n − 1} and A is a selection of one 132-avoiding permutation on every I_{2k}, for k ≥ 1, and one 231-avoiding permutation on every I_{2k+1}, for k ≥ 1, or vice versa, and the selection of one (1342,2431)-avoiding permutation on I_{1}. The author then computed the number of such pairs by repeatedly using the recursive formula for the Catalan numbers. There is an alternative way to count these intervals and their permutations, which yields the equivalent formula

f(n) = f(n − 1) + ∑_{i=0}^{n−2} f(n − i − 1)\binom{2i}{i}.  (5)

Indeed, each way to partition the set {1, 2, ⋯ i} into disjoint intervals and choosing alternatingly 231-avoiding and 132-avoinding permutations on each of them corresponds to a lattice path from (0, 0) to (i, i) using steps (0, 1) and (1, 0). The intervals are specified by the points where the path crosses the main diagonal, that is, it goes above from beyond, or vice versa. The segments of the lattice path between two such crossings correspond to the 231-avoiding or 132-avoiding permutations on the intervals.

• In particular, formula (5) shows that f(n) is an even number if n ≥ 1. This is not surprising, as p is (1342,2431)-avoiding if and only if its reverse p′ is (1342,2431)-avoiding, and n ≥ 1 implies p ≠ p′.

3. The pair (1324,2413) The following definition is useful for the treatment of the next two pairs.

Definition 1 A permutation is called indecomposable if it cannot be cut into two parts so that any entry before the cut is larger than any entry after the cut. Otherwise, we say that the permutation is decomposable.

This definition is useful because the next two pairs of patterns are such that if p is decomposable into parts, and each part avoids the forbidden pair, then p itself avoids the forbidden pair. So the number of all permutations of the class can easily be computed from that of indecomposable ones.

Lemma 2 Let h(n) be the number of (1324,2413)-avoiding n-permutations. Then h(n) = v(n) for all nonnegative integers n.

Proof: It is obvious that if n is the leftmost entry, then the number of such permutations is h(n − 1). Now let p be a (1324,2413)-avoiding n-permutation; suppose n is not the leftmost entry of p and let a be the smallest entry of p which precedes n. Then n precedes the entries 1, 2, ⋯, a − 1. Furthermore, these a − 1 entries must occupy the last a − 1 positions. Indeed, suppose there is an entry z > a − 1 on the right of n which is preceded by the entry b < a still on the right of n, then anbz is a 2413-pattern, a contradiction. So the last a − 1 entries of p are the smallest ones, and thus we can have h(a − 1) different strings on them. Let t(n − a + 1) be the number of possible substrings on the first n − a + 1 entries, in other words, t(i) is the number of (1324,2413)-avoiding n-permutations in which the entry 1 precedes the entry n. In what follows, we are going to use this second interpretation of t(n) so as to alleviate notation. Set t(0) = 0. Let T (x) = ∑_{i≥1} t(n)x^{n}. It follows from the above that permutations counted by t(n) are precisely the indecomposable (1324,2413)-avoiding n-permutations. It is then clear that H(x) = 1/(1−T (x)), and this includes even the case when n is the leftmost entry. Now we analyze the structure of permutations enumerated by the t(i) in order to determine T (x). Let us call entries before the entry 1 front entries, entries after the entry n back entries, and entries between 1 and n middle entries. Moreover, we say that an entry x separates two entries y and z which are written in increasing order if y < x < z. The front entries form a 132-avoiding permutation, the middle entries form an increasing subsequence, and the back entries form a 213-avoiding permutation, otherwise a copy of a forbidden pattern is formed. Similary, no front entry can separate two middle entries, or two back entries in increasing order; no middle entry can separate two front entries in increasing order or two back entries in increasing order; and no back entry can separate two middle entries or two front entries in increasing order. If any of these conditions is violated, then a forbidden pattern is formed. Therefore, the only way for two entries of the same category to be in increasing order is when they relate to any entries of the other two category the same way. Such entries are said to form a block. The block subdivision of a permutation counted by T (x) is shown in Figure 1.

1  n

Figure 1: The block subdivision of p

Here the boxes represent the blocks. As we said above, each block between 1 and n consists of an increasing subsequence, while blocks in the front are 132avoiding permutations, and blocks in the back are 231-avoiding permutations. Permutations satisfying all these conditions avoid both 1324 and 2413, so we have given a full characterization for them. Now for i ≥ 2 let r_{i−1} be the number of those permutations counted by t(i) containing no middle blocks, except for 1 and i. So r_{1} = 1, r_{2} = 2, r_{3} = 6, · · ·. Let R(x) = ∑_{i≥1} r_{i}x^{i} be the generating function for the r_{i}. Then clearly T (x) = \frac{x}{1−R(x)}. Note that r_{i−1} is just the number of ways to partition the interval {2, 3, ⋯, i − 1} into disjoint intervals, and then taking a 213-avoiding or a 132-avoiding permutation on each of them alternatingly. As explained in proof of formula (5), this means that r_{i} = \binom{2i−2}{i−1}, so R(x) = \frac{x}{\sqrt{1−4x}}. Therefore,

T (x) = \frac{x}{1 − R(x)} = \frac{x\sqrt{1 − 4x}}{\sqrt{1 − 4x} − x},

which implies

H(x) = \frac{1}{1 − T (x)} = \frac{(\sqrt{1 − 4x} − x)(\sqrt{1 − 4x}(1 − x) + x)}{(1 − 4x)(1 − x)^{2} − x^{2}} = \frac{1 − 5x + 3x^{2} + x^{2}\sqrt{1 − 4x}}{1 − 6x + 8x^{2} − 4x^{3}}.

So H(x) = V (x), and the Lemma is proved. ◇ Proposition 1 Let n ≥ 2 and let L_{n} be the set of lattice paths from (0, 0) to (n−2, n−2) with steps (0, 1) and (1, 0); and when on the main diagonal, (1, 1). Then L_{n} has t(n) elements.

Proof: Bijection by the above decomposition. Front blocks correspond to segments of paths below the diagonal, back blocks correspond to segments of paths above the diagonal, and middle elements correspond to steps (1,1) on the diagonal. ◇

4. The pair (1342,2314)

Lemma 3 For all nonnegative integers n, we have S_{n}(1342, 2314) = S_{n}(1324, 2413).

Proof: We prove the corresponding statement for indecomposable elements of the two classes, and that certainly implies the lemma. Let p be an indecomposable (1342,2314)-avoiding n-permutation, and let a_{1} > a_{2} > ⋯ > a_{m} = 1 be its left-to-right minima. Then the following three statements must hold for p.

• Any remaining entry on the left of a_{i} is larger than any remaining entry on the right of a_{i}, for i = 2, 3 ⋯, m.

• Entries between a_{i} and a_{i+1} are in decreasing order, for i = 1, 2 ⋯ m − 1.

• Entries after a_{m} = 1 form a 231-avoiding permutation.

Indeed, the first property is needed, for any pair (x, y) of entries not having this property would yield the 2314-pattern a_{i−1}xa_{i}y. The second property is needed, because p is indecomposable, so there is an element z > a_{i} on the right of a_{i+1}. By the first property, z is smaller than any entry between a_{i} and a_{i+1}, so if there were a pair (v, w) in increasing order between a_{i} and a_{i+1}, then a_{i}vwz would be a 1342-pattern. The third statement is obviously necessary. Therefore, an indecomposable (1342,2314)-avoiding n-permutation has the following structure: on the left of a_{m} = 1, there is a 123-avoiding permutation, on the right of a_{m} = 1, there is a 231-avoiding permutation. Moreover, entries on the right of 1, or, in what follows, the tail of p must be smaller than any remaining entry on the left of 1, and p must be indecomposable. However, the three conditions above are not sufficient for a permutation to be (1342,2314)-avoiding. One further condition is needed for the elements of the tail. Let x be any remaining entry of p, so that a_{i} < x < a_{i+1}. Then we say that x is of rank i. Then clearly, we cannot have a copy yxz of the pattern 213 in the tail so that the rank of x is smaller than the rank of y and z, for we would get the 2314-pattern m_{i}yxz. This means that entries z_{1}, z_{2}, ⋯ of rank j_{1}, j_{2}, ⋯ > i on the left of x in the tail must be larger than any entry on the right of x. Moreover, they must be in decreasing order, otherwise the tail would not be 231-avoiding. In other words, if there is an entry y of rank j > i on the left of x, then all entries of rank j which are larger than y, and all entries of ranks higher than j are on the left of x, and they are in decreasing order. Yet in other words, there can be higher-ranked elements inserted into the string of elements of rank i, but they must be in decreasing order (and of course, they cannot be inserted between two elements of an inversion). The diagram of a typical indecomposable (1342,2314)-avoiding n-permutation is shown on Figure 2.

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; 1; m; 1]

Figure 2

This completes the characterization of indecomposable (1342,2314)-avoiding npermutations as it is easy to see that indecomposable permutations satisfying the above four conditions cannot contain 1342 or 2314. There are several ways to see that these n-permutations are counted by the numbers t(n). Maybe the fastest is by showing bijectively that these permutations correspond to the lattice paths of Proposition 1. Indeed, the string of entries of rank 1 form a 231-avoiding permutation to which we can assign a lattice path L of steps (0,1) and (1,0) which never crosses the diagonal (say it stays below). Suppose it touches the diagonal first at the point (i, i). If there is an entry of rank more than 1 inserted between the ith and i + 1st entries of the substring of rank-1 entries, then let us reflect the remainder of L to the main diagonal. Then we continue this procedure till we run out of rank-1 entries. Then, if there are no rank-2 entries, that is, when a_{m−1} = a_{m} + 1 = 2, then make a step (1,1) on the main diagonal, if there are rank-2 entries, then delete all entries of rank 1, then the ranks of all other elements go down by 1, and continue this same procedure. It is easy to see that this is indeed a bijection between indecomposable (1342,2314)-avoiding n-permutations and lattice paths of Proposition 1, completing the proof. So there are t(n) indecomposable (1342,2314)-avoiding n-permutations, and therefore there are h(n) (1342,2314)-avoiding n-permutations. ◇

5. The pair (1342,3241) In this case we cannot rely on indecomposable elements as it is possible for p to contain the pattern 3241 and still be decomposable into parts none of which contains it. Our proof will be therefore somewhat longer.

Lemma 4 Let g(n) = S_{n}(1342, 3241). Then f(n) = g(n) for all nonnegative integers n.

Proof: Let p be an (1342, 3241)-avoiding n-permutation. If the entry n is in the leftmost position, then we clearly have g(n−1) good permutations, and the same is true when n is in the rigthmost position. No suppose n is in neither of these positions. We still consider two cases, according to the position of the entry 1, relative to n. In what follows entries of the left of the entry n are called front entries, those on the right of n are called back entries.

• Suppose 1 is a back entry. Then all front entries must be written in increasing order, for otherwise there would be a 3241-pattern containing the entries 1 and n. Moreover, the front entries must form interval. Indeed, if there were front entries a and b so that a < b and there existed a back entry c so that a < c < b, then abnc would be a 1342-pattern. This means that we can determine all front entries if we only know the leftmost one. Therefore, any (1342, 3241)-avoiding n-permutation in which 1 is a back entry can be obtained uniquely by taking a (1342, 3241)-avoiding m-permu-tation in which the entry n is in the second position, and the leftmost entry is x ≠ 1, and then inserting the entries x+1, x+2, ⋯ x+n−m in increasing order after the leftmost entry. It is easy to see that all permutations obtained this way are indeed (1342, 3241)-avoiding. To find the number of such permutations, note that the maximal entry can be inserted into the second position of any (1342, 3241)-avoiding permutation without creating a bad pattern. It then follows that we have

∑_{i=2}^{n−1} g(i) − ∑_{i=2}^{n−1} c_{i−1}

(1342, 3241)-avoiding n-permutations in which 1 is a back entry. The negative term corresponds to those permutations in which the entry 1 would have been the leftmost entry– so not a back entry.

• Now suppose the entry 1 is a front entry. Denote B the nonempty set of front entries which are smaller than all back entries, and denote D the set of other front entries. Then any entry of D must be on the left of any entry of B, otherwise a 1342-pattern would be formed with the pair x, y not having this property, n, and the back entry smaller than the front entry x. Moreover, all entries of D must be written in increasing order and they must form an interval for the same reasons as in the previous case. The substring on the back entries must be 231-avoiding, otherwise there would be a 1342-pattern together with the entry 1. Now let |B| = i and let m − i be the number of back entries. Then we have g(i) different choices for the substring on B = {1, 2, ⋯, i} and c_{m−i} choices for the substring on the back entries. Entries of D are in increasing order, so we do not have a choice for their substring. However, we still need to determine what the elements of D are. We know they form an interval (so it suffices to determine the smallest one of them) and that they are larger than at least one of the m − i back entries. This means we have m − i choices for their set D, as long as D is not empty. If D is empty, that is, when m = n − 1, then we have no more choices. So altogether we have

∑_{m=2}^{n−2} ∑_{i=1}^{m−1}(m − i) · g(i) · c_{m−i} + ∑_{i=1}^{n−2} g(i) · c_{n−1−i}

(1342, 3241)-avoiding n-permutations in which 1 is a front entry.

Summarizing for all the four cases we get that

g(n) = 2g(n−1)+ ∑_{i=2}^{n−1} g(i)− ∑_{i=2}^{n−1} c_{i−1}+ ∑_{m=2}^{n−2} ∑_{i=1}^{m−1}(m−i)·g(i)·c_{m−i}+ ∑_{i=1}^{n−2} g(i)·c_{n−1−i}

Note that (m − i) · g(i) · c_{m−i} = g(i) · \binom{2(m−i)}{(m−i)} − g(i) · c_{m−i}. Using this identity we get the following equation of generating functions from (6).

G(x)(1 − 2x) + x − 1 = x\frac{G(x) − x − 1}{1 − x} − x^{2} \frac{C(x) − 1}{1 − x}+

x^{2} \frac{(M(x) − 1)(G(x) − 1)}{1 − x} − x^{2} \frac{(C(x) − 1)(G(x) − 1)}{1 − x} + x(C(x) − 1)(G(x) − 1),

where G(x) = ∑_{n≥0} g(n)x^{n} and M(x) = ∑_{n≥0} \binom{2n}{n}x^{n} = \frac{1}{\sqrt{1−4x}}. A teadious but routine computation then shows that G(x)=F(x). ◇

Lemmas 1-4 yield the following theorem, summarizing the results of this paper.

Theorem 1 For all n ≥ 0 we have

S_{n}(1324, 2143) = S_{n}(1342, 2431) = S_{n}(1324, 2413) = S_{n}(1342, 2314) = S_{n}(1342, 3241).

Numerical evidence shows that there is no more pair of patterns of length 4 which is not equivalent to any of the above five pairs and which is avoided by the same number of n-permutations, even if n ≤ 7. So we have found all classes equinumerous to the smooth class.

Acknowledgement

I am thankful to Darla Kremer, who has brought the question into my attention. I am also grateful to my former advisor Richard Stanley and to Sara Billey for sending me helpful data and references.

References

[1] S. Billey, V. Lakshmibai, On the singular locus of a Schubert variety, preprint.

[2] M. Bóna, Exact and Asymptotic Enumeration of Permutations with subsequence conditions, PHD-thesis, Massachusetts Institute of Technology, 1997.

[3] M. Bóna, Exact enumeration of 1342-avoiding permutations; A close link with labeled trees and planar maps, Journal of Combinatorial Theory, Series A, 80 (1997), 257-272.

[4] M. Haiman, Smooth Schubert Varieties, preprint. the electronic journal of combinatorics 5 (1998), #R31 12

[5] D. Kremer, Permutations which avoid pairs of length four, preprint.

[6] Z. Stankova, Forbidden Subsequences, Discrete Mathematics, 132 (1994), 291-316.

[7] R. P. Stanley, “Enumerative Combinatorics”, Volume 2, Cambridge University Press, 1998.

[8] J. West, Generating trees and the Catalan and Schroder numbers, Discrete Mathematics 146 (1995), 247-262.