EXACT ENUMERATION OF 1342-AVOIDING PERMUTATIONS A CLOSE LINK WITH LABELED TREES AND PLANAR MAPS

MIKLÓS BÓNA

Abstract. Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating function H(x) of all 1342-avoiding permutations of length n as well as an exact formula for their number S_{n}(1342). While achieving this, we bijectively prove that the number of indecomposable 1342avoiding permutations of length n equals that of labeled plane trees of a certain type on n vertices recently enumerated by Cori, Jacquard and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte in 1963. Moreover, H(x) turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Zeilberger and Noonan. We also prove that \sqrt[n]{S_{n}(1342)} converges to 8, so in particular, lim_{n→∞}(S_{n}(1342)/S_{n}(1234)) = 0.

1. Introduction

1.1. Our main results. In this paper we are going to prove an exact formula for the number S_{n}(1342) of 1342-avoiding permutations of length n showing that

S_{n}(1342) = \frac{(7n^{2} − 3n − 2)}{2} · (−1)^{n−1} + 3 ∑_{i=2}^{n} 2^{i+1} · \frac{(2i − 4)!}{i!(i − 2)!} · \binom{n − i + 2}{2} · (−1)^{n−i},

by first proving that the ordinary generating function H(x) for these numbers S_{n}(1342) has the following simple form:

H(x) = \frac{32x}{−8x^{2} + 12x + 1 − (1 − 8x)^{3/2}} .

This is the first result we know of which provides an exact formula for the number S_{n}(q) of permutations of length n avoiding a given pattern q that is longer than three and is not 1234. Results concerning the case of length three can be traced back to two centuries; [4] already makes references to earlier work. The formula for q = 1234 is given in [8]. Until recently it has not even been known that S_{n}(1342) < c^{n} for some constant c. In [1] this upper bound with c = 9 was proved. This paper’s result pushes down this c to 8, and proves that it is optimal. (Definitions and more background information can be found in the next subsection).

In our proof, we are going to present a new link between the enumeration of permutations avoiding the pattern 1342 and the that of β(0, 1)-trees, a class of labeled trees recently introduced in [5]. We will show that the number I_{n}(1342) of indecomposable 1342-avoiding permutations of length n is equal to the number of β(0, 1)-trees on n nodes. The set D_{n}^{β(0,1)} of β(0, 1)-trees on n nodes is known [5] to be equinumerous to the set of rooted bicubic maps on 2(n + 1) vertices, and an exact formula for the number t_{n} of these is provided in [16]. Therefore, I_{n}(1342) = |D_{n}^{β(0,1)}| = t_{n} = 3 · 2^{n−1} · \frac{(2n)!}{(n+2)!n!}. So combinatorially, the number of all n-permutations avoiding 1342 will be shown to be equal to that of plane forests on n vertices in which each component is a β(0, 1)-tree. To our best knowledge, this is the first time when permutations avoiding a given pattern are shown to have such a close connection with some planar maps, though recently 2-stack-sortable permutations have been shown to be equinumerous to nonseparable planar maps [6] [7].

Research at MSRI is supported in part by NSF grant DMS-9022140.

Examining the generating function H(x) we will prove and disprove several conjectures for the pattern 1342. H(x) turns out to be algebraic, proving a conjecture of Zeilberger and Noonan [19] for the first time for a nonmonotonic pattern which is longer than three. We will see that \sqrt[n]{S}_{n}(1342) → 8, which disproves a conjecture of Stanley and implies the surprising fact that lim_{n→∞}(S_{n}(1342)/S_{n}(1234)) = 0.

1.2. Definitions and Background. In what follows permutations of length n will be called n-permutations. A permutation is called indecomposable if it cannot be cut in two parts so that everything before the cut is larger than everything after the cut. Let q = (q_{1}, q_{2}, …, q_{k}) be a k-permutation and let p = (p_{1}, p_{2}, …, p_{n}) be an n-permutation. We say that p avoids q if 1 ≤ i_{q_{1}} < i_{q_{2}} < … < i_{q_{k}} ≤ n such that p(i_{1}) < p(i_{2}) < … < p(i_{k}). For example, p avoids 132 if it cannot be written as ⋯, a, ⋯, b, ⋯ c, ⋯ so that a < c < b. For another example, a permutation is 1234-avoiding if it doesn’t contain an increasing subsequence of length 4.

It is a natural and easy-looking question to ask how many n-permutations avoid a given pattern q. Throughout this paper, this number will be denoted by S_{n}(q).

However, this problem turns out to be very hard. Exact answers have only been known for the easy case of patterns of length 3 [11]. In that case S_{n}(q) = C_{n}, the n-th Catalan number, for any such pattern q. If q is longer than three, then the most exact result is due to Regev [10] and says that for all n, S_{n}(1234 ⋯ k) asymptotically equals c\frac{(k−1)^{2n}}{n^{(k^{2}−2k)/2}} , where c is a constant given by a multiple integral. The major problem of this area is to prove the conjecture of Wilf and Stanley [18] from 1990, stating that for each pattern q there is an absolute constant λ so that S_{n}(q) < λ^{n} holds. This has been proven for the case of length 4 and some longer patterns in [1]. The general case is, however, still open.

Stanley [15] conjectured that \sqrt[n]{S_{n}(q)} converges to (k − 1)^{2} where k is the length of q. The results of this paper will indicate the disproof of this conjecture for the pattern 1342, in fact, our formula for S_{n}(1342) clearly implies that \sqrt[n]{S_{n}(1342)} → 8. This

shows in particular that (S_{n}(1342)/S_{n}(1234)) → 0 when n → ∞ as \sqrt[n]{S_{n}(1234)} → 9 by the above results of Regev [10] and Gessel [8] for monotonic patterns. We would like to point out the surprising nature of this discovery: while S_{n}(q) = \binom{2n}{n}/(n + 1) for any patterns q of length three, for the case of length four there are sequences S_{n}(q) that are not only different from each other, but their quotient also converges to 0.

We note that while there are 24 permutation patterns of length 4, for many of them the sequences S_{n}(q) are identical. In fact, there are only three different classes of patterns from this point of view, [17], [12], 1342, 1234 and 1324 are representants of them.

Recently, attention has been paid to the problem of counting the number of permutations of length n containing a given number r (as opposed to 0) of subsequences of a certain type q.

The major problem of this field is to describe this function for any given r, not just for r = 0. In [19] Noonan and Zeilberger conjectured that for any given subsequence q and for any given r, the number of n-permutations containing exactly r subsequences of type q is a P -recursive function of n. Present author has proved this conjecture for any r when q = 132. Beyond the case of length 3, however, there have been no nonmonotic instances solved prior to this paper, not even for the case of r = 0. Even in the case of length 3, exact formulae have only been given for r = 1 ([9] for q = 123 and [3] for 132). The case of monotonic patterns and r = 0 has been handled in [20]. Figure 1 shows the present state of research on permutations avoiding given patterns of length 4, including the contributions of this paper.

known [10] known [1] known [1] S_{n}(q) < c^{n} formula P -recursive known [8] known this paper open  known [20] known this paper open 1324 1342 1234  Figure 1

In the following two paragraphs we give a very brief summary of P -recursive and algebraic generating functions. The reader familiar with them can skip these paragraphs.

A function f : ℕ → ℂ is called P -recursive if there exist polynomials P_{0}, P_{1}, ⋯, P_{k} ∈ Q[n], with P_{k} ≠ 0 so that

P_{k}(n)f(n) + P_{k−1}(n)f(n + k − 1) + ⋯ + P_{0}(n)f(n) = 0  (1)

for all natural numbers n. Here P -recursive stands for “polynomially recursive”. The continuous analogue of this notion is d-finiteness, which stands for “differentiably finite”. Let u(x) ∈ ℂ[[x]] be a power series. If there exist polynomials p_{0}(x), p_{1}(x), ⋯ p_{d}(x) so that p_{d} ≠ 0 and

p_{d}(x)u^{(d)}(x) + p_{d−1}(x)u^{(d−1)}(x) + ⋯ + p_{1}(x)u′(x) + p_{0}(x)u(x) = 0,  (2)

then we say that u is d-finite. (Here u^{(j)} = \frac{d^{j}u}{dx^{j}}). It is well-known [13] that a function f(n) is P -recursive if and only if its ordinary generating function u(x) = F (x) = ∑_{n≥0} f(n)x^{n} is d-finite.

Another, smaller class of formal power series is that of algebraic series. We say that the series v(x) ∈ ℂ[[x]] is algebraic if there exist polynomials p_{0}(n), p_{1}(n), ⋯ p_{d−1}(n) so that p_{d−1} ≠ 0 and

v^{d}(x) + p_{d−1}(x)v^{d−1}(x) + ⋯ + p_{1}(x)v(x) + p_{0}(x) = 0.  (3)

Any algebraic power series is necessarily d-finite.

As we have mentioned, we are going to prove our results by showing connections between these permutations and rooted bicubic maps. These are planar maps with 2-colorable vertices which in addition all have degree three and a distinguished “root” edge and face. We will make good use of a class of labeled rooted trees called β(0, 1)- trees introduced in [5]. Their definition is at the beginning of the next section.

2. The correspondence between trees and permutations

Definition 1. [5] A rooted plane tree with nonnegative integer labels l(v) on each of its vertices v is called a β(0, 1)-tree if it satisfies the following conditions:

• if v is a leaf, then l(v) = 0,

• if v is the root and v_{1}, v_{2}, ⋯, v_{k} are its children, then l(v) = ∑_{i=1}^{k} l(v_{k}),

• if v is an internal node and v_{1}, v_{2}, ⋯, v_{k} are its children, then l(v) ≤ 1 + ∑_{i=1}^{k} l(v_{k}).

A branch of a rooted tree is a tree whose top is one of the root’s children. Some rooted trees may have only one branch, which doesn’t necessarily mean they consist of a single path.

We start by treating two special types of β(0, 1)-trees on n vertices. These cases are fairly simple- they will correspond to 231-avoiding (resp. 132-avoiding) permutations, but they will be our tools in dealing with the general case.

First we set up a bijection f from the set of all 1342-avoiding n-permutations starting with the entry 1 and the set of β(0, 1)-trees on n vertices consisting of one single path. In other words, the former is the set of 231-avoiding permutations of the set {2, 3, 4 ⋯, n}.

So let p = (p_{1}p_{2} ⋯ p_{n}) be an 1342-avoiding n-permutation so that p_{1} = 1. Take an unlabeled tree on n nodes consisting of a single path and give the label l(i) to its ith node (1 ≤ i ≤ n − 1) by the following rule:

l(i) = #{j ≤ i so that p_{j} > p_{s} for at least one s > i }.

Finally, let l(n) = l(n − 1). In words, l(i) is the number of entries on the left of p_{i} (inclusive) which are larger than at least one entry on the right of p_{i}. We note that this way we could define f on the set of all n-permutations starting with the entry 1, but in that case, as we will see, f would not be a bijection. (For example, the images of 1342 and 1432 would be identical).

Example 1. If p = 14325, then the labels of the nodes of f(p) are, from the leaf to the root, 0,1,2,0,0.

Lemma 1. f is a bijection from the set of D_{n}^{β(0,1)} of all β(0, 1)-trees on n vertices consisting of one single path to the set of 1342-avoiding n-permutations starting with the entry 1.

Proof: It is easy to see that f indeed maps into the set of β(0, 1)-trees : l(i + 1) ≤ l(i) + 1 for all i because there can be at most one entry counted by l(i + 1) and not counted by l(i), namely the entry p_{i+1}. All labels are certainly nonnegative and l(1) = 0.

To prove that f is a bijection, it suffices to show that it has an inverse, that is, for any β(0, 1)-tree T consisting of a single path, we can find the only permutation p such that f(p) = T. We claim that given T, we can recover the entry n of the preimage p. First note that p was 1342-avoiding and started by 1, so any entry on the left of n must have been smaller than any entry on the right of n. In particular, the node preceding n must have label 0. Moreover, n is the leftmost entry p_{i} of p so that p_{j} > 0 for all j ≥ i if there is such an entry at all, and n = p_{n} if there is none. That is, n corresponds to the node which starts the uninterrupted sequence of strictly positive labels which ends in the last node, if there is such a sequence, and corresponds to the last node otherwise. To see this, note that n is the largest of all entries, so in particular it is always larger than at least one entry in any nonempty set of entries.

Once we located where n was in p, we can simply delete the node corresponding to it from T and decrement all labels after it by 1. (If this means deleting the last node, we just change l(n − 1) l(n − 2) to satisfy the root-condition). We can indeed do this because the node preceding n had label 0, and the node after n had a positive label, by our algorithm to locate n. Then we can proceed recursively, by finding the position of the entries n − 1, n − 2, ⋯, 1 in p. This clearly defines the inverse of f, so we have proved that f is a bijection. Lemma 2. The number β(0, 1)-trees with all labels equal to zero is C_{n−1}. Proof: These β(0, 1)-trees are in fact unlabeled plane trees. We prove that they are in one-to-one correspondence with the 132-avoiding permutations whose last entry is n. Suppose we already know this for all positive integers k < n. Let T be a β(0, 1)-tree on n vertices with all labels equal to 0 and root r. Let r have t children, which are, from left-to-right, at the top of such unlabeled trees T_{1}, T_{2}, ⋯, T_{t} on n_{1}, n_{2}, ⋯, n_{t} nodes. Then by induction, each of the T_{i} corresponds to a 132-avoiding n_{i}-permutation ending with n_{i}. Now add ∑_{j=i+1}^{t} n_{j} to all entries of the permutation p_{i} associated with T_{i}, then concatenate all these strings and add n to the end to get the permutation p associated with T. This is clearly a bijection as the blocks of the first n − 1 elements determine the branches of T. Example 2. The permutation 341256 corresponds to the β(0, 1)-tree with all labels equal to 0 shown in Figure 2.

[figure: 3; 4; 2; 1; 5; 6; Figure 2]

An easy way to read off the corresponding permutation once we have its entries written to the corresponding nodes is the well-known preorder reading: for every node, first write down the entries associated with its children from left to right, then the entry associated with the node itself, and do this recursively for all the children of the node.

Note that such a β(0, 1)-tree has only one branch if and only if the next-to-last element of the indecomposable 132-avoiding n-permutation corresponding to it is n − 1.

Let’s introduce some more notions before we attack the general case. An entry of a permutation which is smaller than all the entries by which it is preceded called a left-to-right minimum.

Definition 2. Two n−permutations x and y are said to be in the same class if the left-to-right minima of x are the same as those of y and they are in the same positions.

Example 3. 34125 and 35124 are in the same class since their left-to-right minima are 3 and 1, and they are located at the same positions. 3142 and 3412 are not in the same class.

Proposition 1. Each nonempty class C of n-permutations contains exactly one 132avoiding permutation.

Proof: Take all entries which are not left-to-right minima and fill all slots between the left-to-right minima with them as follows: in each step place the smallest element which has not been placed yet which is larger then the previous left-to-right minimum. The permutation obtained this way will be clearly 132-avoiding, and it will be the only one in this class because any time we deviate from this procedure, we create a 132-pattern.

Definition 3. The normalization N(p) of an n-permutation p is the only 132-avoiding permutation in the class C containing p.

Example 4. If p = 32514, then N(p) = 32415.

Definition 4. The normalization N(T) of a β(0, 1)-tree T is the β(0, 1)-tree which is isomorphic to T as a plane tree, with all labels equal to zero.

Proposition 2. A permutation p is indecomposable if and only N(p) is indecomposable.

Proof: Let C be the class containing p, given by the set and position of its left-to-right minima. It is clear that if p ∈ C is decomposable, then the only way to cut it in two parts (so that everything before the cut is larger than everything after the cut) is to cut it immediately before a left-to-right minimum a. Now if there is a left-to-right minimum a so that it is in the n+1−ath position, then all entries which are larger than a must be placed on the left of a and so all such permutations in C are decomposable. If there is no such a, then for all left-to-right minima m, there will be an entry b so that m < b and b is on the right of m and so permutations in C will not be decomposable.

Corollary 1. If p is an indecomposable n-permutation, then N(p) always ends with the entry n.

Proof: Note that the only way for a 132-avoiding n-permutation to be indecomposable is for it to end with n. Then the statement follows from Proposition 2.

Now we are in a position to prove our theorem about the number of indecomposable 1342-avoiding permutations.

Theorem 1. The number of indecomposable n-permutations which avoid the pattern 1342 is

I_{n}(1342) = t_{n} = 3 · 2^{n−1} · \frac{(2n)!}{(n + 2)!n!}

Proof: We are going to set up a bijection F between these permutations and D_{n}^{β(0,1)}. This will be an extension of the bijection f of lemma 1. As the size of D_{n}^{β(0,1)} is known to be equal to t_{n} [5], this will prove our claim.

Let p be and indecomposable 1342-avoiding n-permutation. Take N(p). By corollary 1 its last element is n. Define F (N(p)) to be the β(0, 1)-tree S associated to N(p) by the bijection of lemma 2. Now write the entries of p to the nodes of S so that for all i, the p_{i} is written to the node where N(p)_{i} was written in S. In particular, the left-to-right minima remain unchanged. Figure 3 shows how we associate the entries of the permutation 361542 to the nodes of N(T), which is the image of N(p) = 341256.

[figure: 3; 6; 5; 1; 4; 2; Figure 3]

Now we are going to define the label of each node for this new β(0, 1)-tree T and obtain F (p) this way. (As an unlabeled tree, T will be isomorphic to S, but its labels will be different). Denote i the ith node of T in the preorder reading, thus p_{i} is the ith entry of p, (which is therefore associated to node i), while l(i) is the label of this node. We say that p_{i} beats p_{j} if there is an element p_{h} so that p_{h}, p_{i}, p_{j} are written in this order and they form a 132-pattern. Moreover, we say that p_{i} reaches p_{k} if there is a subsequence p_{i}, p_{i+a_{1}}, ⋯ p_{i+a_{t}}, p_{k} of entries so that i < i + a_{1} < i + a_{2} < ⋯ < i + a_{t} < k and that any entry in this subsequence beats the next one. For example, in the permutation 361542, the entry 6 beats 5 and 4, 5 beats 4 and 2, and 4 beats 2, while 6 reaches 2 (of course, each entry reaches all those elements it beats, too). Then let

l(i) = #{j descendants of i (including i itself) so that there is at least one k > i for which p_{j} reaches p_{k}},

and let F (p) be the β(0, 1)-tree defined by these labels. (Recall that a descendant of i is an element of the tree whose top element is i). First, it is easy to see that F indeed maps into the set of β(0, 1)-trees: if v is an internal node and v_{1}, v_{2}, ⋯, v_{k} are its children, then l(v) ≤ 1 + ∑_{i=1}^{k} l(v_{k}) because there can be at most one entry counted by l(v) and not counted by any of its children’s label, namely v itself. All labels are certainly nonnegative and all leaves, that is, the left-to-right minima, have label 0.

If p = 361542, then F (p) is the β(0, 1)-tree shown in Figure 4b.

[figure: 3; 6; 5; 1; 4; 2; Figure 4a; 0; 1; 1; 0; 3; 3; Figure 4b]

To prove that F is a bijection, it suffices to show that it has an inverse, that is, for any β(0, 1)-tree T ∈ D_{n}^{β(0,1)}, we can find the only permutation p so that F (p) = T. We again claim that given T, we can recover the node j which has the entry n of the preimage p associated to it, and so we can recover the position of n in the preimage.

Proposition 3. Suppose p_{n} ≠ n, that is, n is not associated to the root vertex. Then each ancestor of n, including n itself, has a positive label. If p_{n} = n, then l(n) = 0 and thus there is no vertex with the above property.

Proof: If p_{n} = n, then nothing beats it, thus p_{n} = 0. Suppose p_{n} is not the root vertex.

To prove our claim it is enough to show that for any node i which is an an ancestor of j, there is an entry p_{k} so that p_{k} is an ancestor of p_{i} and n = p_{j} reaches k. Indeed, this would imply that the entry p_{j} = n is counted by the label l(i) of i. Now let a_{m} = p_{1} > a_{2} > ⋯ a_{1} = 1 be the left-to-right minima of p so that n is located between a_{r} and a_{r+1}. Then n certainly beats all elements located between a_{r} and a_{r+1} as a_{r} can play the role of 1 in the 132-pattern. Clearly, n must beat at least one entry y_{1} on the right of a_{r+1} as well, otherwise p would be decomposable by cutting it right before a_{r+1}. If y_{1} is on the right of i, then we are done. If not, then y_{1} must beat at least one entry y_{2} which is on the other side of a_{r_{1}+1}, where y is located between a_{r_{1}} and a_{r_{1}+1} for the same reason, and so on. This way we get a subsequence y_{1}, y_{2}, ⋯ so that n reaches each of the y_{t}, and this subsequence eventually gets to the right of i, since in each step we bypass at least one left-to-right minimum. Thus the proposition is proved.

Proposition 4. Suppose p_{n} ≠ n. Then n is the leftmost entry of p which has the property that each of its ancestors has a positive label.

Proof: Suppose p_{k} and n both have this property and that p_{k} is on the left of n. (If there are several candidates for the role of p_{k}, choose the rightmost one). If p_{k} beats an element y on the right of n by participating in the 132-pattern x p_{k} y, then x p_{k} n y is a 1342-pattern, which is a contradiction. So p_{k} does not beat such an element y. In other words, all elements after n are smaller than all elements before p_{k}. Still, p_{k} must reach elements on the right of n, thus it beats some element v between p_{k} and n. This element v in turn beats some element w on the right of n by participating in some 132-pattern t v w. However, this would imply that t v n w is a 1342-pattern, a contradiction, which proves our claim.

Therefore, we can recover the entry n of p from T. Then we can proceed as in the proof of Lemma 1, that is, just delete n, subtract 1 from the labels of its ancestors and iterate this procedure to get p. If any time during this procedure we find that the current root is associated to the maximal entry that hasn’t been associated to other vertices yet, and the tree has more than one branch at this moment, then deleting the root vertex will split the tree into smaller trees. Then we continue the same procedure on each of them. The set of the entries associated to each of these smaller trees is uniquely determined because T as an unlabeled tree determines the left-to-right minima of p. Therefore, we can always recover p in this way from T. This proves that F is a bijection.

Thus we have set up a bijection between the set of indecomposable 1342-avoiding n-permutations and D_{n}^{β(0,1)}. We know from [5] that |D_{n}^{β(0,1)}| = t_{n} = 3 · 2^{n−1} · \frac{(2n)!}{(n+2)!n!} and therefore the Theorem is proved.

Note that in particular, F maps 132-avoiding permutations into β(0, 1)-trees with all labels equal to 0 and permutations starting with the entry 1 into β(0, 1)-trees consisting of a single path.

Corollary 2. S_{n}(1342) equals the number of plane forests on n vertices in which each component is a β(0, 1)-tree.

3. Enumerative results

Tutte [16] has obtained the numbers t_{n} by first computing a translate of their generating function

F (x) = ∑_{n=1}^{∞} 3 · 2^{n−1} · \frac{(2n)!}{(n + 2)!n!}x^{n} = \frac{8x^{2} + 12x − 1 + (1 − 8x)^{3/2}}{32x} .  (4)

By theorem 1, the coefficients of this generating function are the numbers I_{n}(1342). Therefore, the generating function of all 1342-avoiding permutations is given by the following theorem.

Theorem 2. Let s_{n} = S_{n}(1342) and let H(x) = ∑_{n=0}^{∞} s_{n}x^{n}. Then

H(x) = ∑_{i≥0} F^{i}(x) = \frac{1}{1 − F (x)} = \frac{32x}{−8x^{2} + 12x + 1 − (1 − 8x)^{3/2}} .  (5)

Proof: Any 1342-avoiding permutation has a unique decomposition into indecomposable permutations. This can consist of 1, 2, ⋯ blocks, implying that s_{n} = ∑_{i=1}^{n} t_{i}s_{n−i}, and the statement follows.

Theorem 3. For all n ≥ 0 we have

\begin{aligned}S_{n}(1342) & = S_{n}(1342) \\ & = \frac{(7n^{2}−3n−2)}{2} ·(−1)^{n−1}+3 ∑_{i=2}^{n} 2^{i+1}· \frac{(2i−4)!}{i!(i−2)!}\binom{n−i+2}{2}(−1)^{n−i}. \end{aligned} (6)

Proof: Multiply both the numerator and the denominator of H(x) by (−8x^{2} +20x+ 1) + (1 − 8x)^{3/2}. After simplifying we get

H(x) = \frac{(1 − 8x)^{3/2} − 8x^{2} + 20x + 1}{2(x + 1)^{3}}.  (7)

As (1 − 8x)^{3/2} = 1 − 12x + ∑_{n≥2} 3 · 2^{n+2}x^{n} \frac{(2n−4)!}{n!(n−2)!}, formula (7) implies our claim.

So the first few values of S_{n}(1342) are 1,2,6,23,103,512,2740,15485,91245,555662. In particular, one sees easily that the expression on the right hand side of (6) is dominated by the last summand; in fact, the alternation in sign assures that this last summand is larger than the whole right hand side if n ≥ 8. As \frac{(2n−4)!}{n!(n−2)!} < \frac{8^{n−2}}{n^{2.5}} by Stirling’s formula, we have proved the following exponential upper bound for S_{n}(1342).

Corollary 3. For all n, we have S_{n}(1342) < 8^{n}.

It is straightforward to check that the numbers I_{n} = t_{n} satisfy the following recurrence

t_{n} = (8n − 4)t_{n−1}/(n + 2).  (8)

In particular, \sqrt[n]{t_{n}} → 8. Using this formula we can disprove a conjecture of Stanley claiming that for all permutation patterns q of length k, the sequence \sqrt[n]{S_{n}(q)} converges to (k − 1)^{2}.

Theorem 4. \sqrt[n]{s_{n}} = \sqrt[n]{S_{n}(1342)} → 8 when n → ∞.

Proof: This is true as clearly t_{n} ≤ s_{n} < 8^{n} by Corollary 3 and we know from (8) that \sqrt[n]{t_{n}} → 8 if n → ∞.

Corollary 4. lim_{n→∞}(S_{n}(1342)/S_{n}(1234)) = 0.

Proof: Follows from lim_{n→∞} \sqrt[n]{S_{n}(1234)} = 9 [8] [10].

This Corollary certainly implies that S_{n}(1342) < S_{n}(1234) if n is large enough. However, using the formulae of Theorem 3 and [8], we can easily show that this is true for all n ≥ 6. (This has recently been shown by a long argument in [1]).

Corollary 5. For all n ≥ 6, we have S_{n}(1342) < S_{n}(1234).

Proof: It is known [8] that

S_{n}(1234) = 2 · ∑_{i=0}^{n} \binom{2i}{i} · \binom{n}{i}^{2} · \frac{3k^{2} + 2k + 1 − n − 2kn}{(k + 1)^{2}(k + 2)(n − k + 1)}  (9)

One sees easily that the dominant summand is the one with i = 2n/3, and that this summand is much larger than the last (and dominant) summand in (6) if n ≥ 9. The proof then follows by checking the values of S_{n}(1342) and S_{n}(1234) for n ≤ 8.

Formula (5) enables us to prove that the sequence S_{n}(1342) is P -recursive in n, solving an instance of the conjecture of Zeilberger and Noonan mentioned in the Introduction. Indeed, H(x) is certainly algebraic, thus in particular, it is d-finite and therefore S_{n}(1342) is P -recursive as claimed. So we have proved the following theorem.

Theorem 5. The sequence S_{n}(1342) is P -recursive in n. Furthermore, its generating function H(x) is algebraic and its only irrationality is \sqrt{1 − 8x}.

Acknowledgement

I am grateful to my research advisor Richard Stanley and to Robert Cori who indicated me very useful references, as well as to Gilles Schaeffer who sent me the preprint [5]. I am also indebted to Sergey Fomin for his helpful remarks and suggestions.

References

[1] M. Bóna, Permutations avoiding certain patterns; The case of length 4 and generalizations, Discrete Mathematics, to appear.

[2] M. Bóna, The number of permutations with exactly r 132-subsequences is P-recursive in the size! Advances in Applied Mathematics, to appear.

[3] M. Bóna, Permutations with one or two 132-subsequences, Discrete Mathematics, to appear.

[4] E. Catalan, Note sur une équation aux differences finies, J. des Mathematiques pures et appliqués, 3 (1838), 508-516.

[5] R. Cori, B. Jacquard, G. Schaeffer, Description trees for some families of planar maps, preprint.

[6] S. Dulucq. S. Gire, J. West, Permutations with forbidden subsequences and nonseparable planar maps. Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993), Discrete Math, 153 (1996), no. 1-3, 85-103.

[7] I. P. Goulden, J. West, Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations, J. Combin. Theory Ser. A 75 (1996), no. 2, 220-242.

[8] I. M. Gessel, Symmetric functions and P -recursiveness, J. Combin. Theory Ser. A 53 (1990), 257–285.

[9] J. Noonan, The Number of Permutations Containing Exactly One Increasing Subsequence of Length 3, Discrete Mathematics, 152 (1996), 307-313.

[10] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Advances in Mathematics 41 (1981), 115-136.

[11] R. Simion and F. W. Schmidt, Restricted Permutations, European Journal of Combinatorics, 6 (1985), 383-406.

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

[13] R. P. Stanley, Differentiably Finite Power Series, European Journal of Combinatorics, 1 (1980), 175-188.

[14] R. P. Stanley, “Enumerative Combinatorics”, Volume 2, to appear.

[15] R. P Stanley, oral communication.

[16] J. W. Tutte, A census of planar maps, Canadian Journal of Mathematics 33 (1963), 249-271.

[17] J. West, Permutations with forbidden subsequences ; and, Stack sortable permutations, PHDthesis, Massachusetts Institute of Technology, 1990.

[18] H. S. Wilf, R. P. Stanley, oral communication.

[19] D. Zeilberger, J. Noonan, The enumeration of permutations with a prescribed number of “forbidden” subsequences, Advances in Applied Mathematics, 17 (1996), 381-407.

[20] D. Zeilberger, Holonomic systems for special functions, J. Computational and Applied Mathematics, 32 (1990), 321-368.

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139

  E-mail address: bona@math.mit.edu