2-STACK SORTABLE PERMUTATIONS WITH A GIVEN NUMBER OF RUNS

MIKLÓS BÓNA

Abstract. Using earlier results we prove a formula for the number W_{(n,k)} of 2stack sortable permutations of length n with k runs, or in other words, k − 1 descents. This formula will yield the suprising fact that there are as many 2-stack sortable permutations with k −1 descents as with k −1 ascents. We also prove that W_{(n,k)} is unimodal in k, for any fixed n.

1. Introduction

1.1. Our main results. In this paper we are going to show that the number of 2-stack sortable permutations of length n with k − 1 ascents is equal to the number T_{(n,k)} of β(1, 0)-trees on n + 1 nodes with k leaves. (See Section 2 for the definition of β(1, 0)-trees). This, and results from [2] and [5] will enable us to easily show that

W_{(n,k)} = \frac{(n + k − 1)!(2n − k)!}{k!(n + 1 − k)!(2k − 1)!(2n − 2k + 1)!},  (1)

which formula is symmetric in k and n + 1 − k.

1.2. Background and Definitions. In what follows, permutations of length n will be called n-permutations. We say that i is a descent of the permutation p = (p_{1}, p_{2}, ⋯, p_{n}) if p_{i} > p_{i+1}. Similarly, j is an ascent of p if p_{j} < p_{j+1}. If p has d descents, then p decomposes into d + 1 increasing sequences of consecutive entries, and we then say that p has d + 1 runs. We will use the concept of descents and runs interchangeably, according to the current context.

The stack-sorting operation Π can be defined on the set of all n-permutations as follows. Let p = p_{L}np_{R} be an n-permutation, with p_{L} and p_{R} respectively denoting its subword before and after the maximal entry. Let Π(p) = Π(p_{L})Π(p_{R})n, where p_{L} and p_{R} are defined recursively by this same rule. For a nonrecursive, algorithmic definition, or the origin of the notion see [6], [8].

A permutation p is called t-stack sortable if Π^{t}(p) is the identity permutation. The set of 1-stack sortable n-permutations is easy to characterize by the following

notion of pattern avoidance. 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 contains a q-subsequence (or q-pattern) if there exists 1 ≤ i_{q_{1}} < i_{q_{2}} < ⋯ < i_{q_{k}} ≤ n such that p_{i_{1}} < p_{i_{2}} < ⋯ < p_{i_{k}}. We say that p avoids q if p contains no q-subsequence.

This paper was written while the author was a one-term visitor at Mathematical Sciences Research Institute in Spring 1997. This visit was supported by an MIT Applied Mathematics Fellowship.

For example, p avoids 231 if it cannot be written as ⋯, a, ⋯, b, ⋯ c, ⋯ so that c < a < b. It is easy to show [6] [8] [9] that a permutation is 1-stack sortable if and only if it avoids the pattern 231. In paticular, the number of 1-stack sortable permutations is therefore C_{n}, the n-th Catalan number.

The set of 2-stack sortable permutations is much more complex. For example, it is not true that a subword of a 2-stack sortable permutation is always 2-stack sortable; for 35241 is 2-stack sortable, while 3241 is not. Similarly, it is far more difficult to find a formula for the number W_{n} of these permutations than for that of 1-stack sortable ones. See [10] [4] or [3] for a proof of the formula W_{n} = 2(3n)!/((n + 1)!(2n + 1)!) and see [8] for a characterization of 2-stack sortable permutations.

In this paper we are going to construct a bijection between the set of 2-stack sortable n-permutations with k runs and that of β(1, 0)-trees on n+1 vertices having k leaves. This bijection will be based on a bijection in [4], which mapped these permutations into a class of labeled binary trees. (Our trees are not binary). The set of these trees has recently been shown to be equinumerous [2] to a certain class of planar maps, and the number of those planar maps is known [5]. Therefore, we are going to obtain a formula for the number W_{(n,k)} of 2-stack sortable permutations with k runs, which is a bit surprising, given that even the formula for W_{n} was fairly difficult to prove.

What is even more surprising is that this formula reveals that there are as many 2-stack sortable permutations with k descents as with k ascents. We do not see any obvious reason why this should be true. A direct combinatorial proof of this fact would be highly desirable, but it may not be easy as we do not even have such a proof for the same fact in the much simpler case of 132-avoiding permutations. We also prove that W_{(n,k)} is unimodal in k for any fixed n.

We point out that this is the second case recently [1] when a class of the description trees introduced in [2] to enumerate planar maps has been used to enumerate permutations.

2. The correspondence between trees and permutations

Let p be an n-permutation. A right-to-left maximum of p is an entry which is larger than all entries it precedes. If the right-to-left maxima of p are a_{1} > a_{2} > ⋯ > a_{t}, then clearly a_{1} = n and a_{t} is the last entry of p. In the next three paragraphs we closely follow the characterization of 2-stack sortable permutation given in [4].

Write p in the form s_{1}a_{1}s_{2}a_{2} ⋯ s_{t}a_{t}. Here the s_{i} are strings of entries located between two right-to-left maxima. We say that p is of type 1 if the entry a_{t} − 1 is part of the string s_{t}. Otherwise we say that p is of type 2. The 1-permutation 1, denoted ϵ, is of type 2. Then the following holds. Lemma 1. [4] There is a bijection F from the set of 2-stack sortable n-permutations of type 1 to that of 2-stack sortable (n−1)-permutations with a right-to-left maximum marked. Moreover, F preserves the number of descents and does not decrease the number of right-to-left maxima. Proof:[4] Let p be of type 1, with the above s_{1}a_{1}s_{2}a_{2} ⋯ s_{t}a_{t} decomposition. Define F as follows. Delete a_{t} from the end of p and decrement all entries larger than a_{t} by 1. Then a_{t} − 1 ∈ s_{t} becomes a right-to-left maximum in the new permutation, in fact, it becomes the tth right-to-left maximum. Mark this entry to get F (p). This map is reversible by simply adding an entry one larger than the marked vertex to the end of F (p) and increment all the larger entries by one.

So F is a bijection. Moreover, F does not create or destroy any existing descents as it deletes the last entry of p, and that entry was larger than its predecessor. The number of right-to-left maxima is not decreased by F, because a_{t} − 1 becomes a right-to-left maximum instead of a_{t}.

Finally, one sees easily [4] that F (p) is 2-stack sortable if and only if p is, and the proof is complete.

We need one more lemma from [4]. We omit its proof as we will not need any of its rather complicated machinery. Let rl(p) be the number of right-to-left maxima of p and let desc(p) be the number of descents in p.

Lemma 2. Let n ≥ 2. Then there is a bijection G from the set of 2-stack sortable n-permutations of type 2 onto the set of ordered pairs (p_{1}, p_{2}) where

1. p_{1} is any 2-stack sortable n_{1}-permutation, p_{2} is either a 2-stack sortable n_{2}- permutation of type 1, or ϵ,

2. n_{1} + n_{2} = n,

3. rl((p_{1}) + rl(p_{2}) = rl(p),

4. desc(p_{1}) + desc(p_{2}) + 1 = desc(p).

We are going to iterate the decomposition of the above Lemma. In other words, we take a 2-stack sortable n-permutation p of type 2, decompose it into (p_{1}, p_{2}) by the bijection G of [4], then, if p_{1} was of type 2 (and not ϵ), then we apply G to p_{1} to get (p_{11}, p_{12}). Again, if p_{11} is of type 2 (and not ϵ), the we apply G to p_{11}, and so on. We stop when both elements of the current decomposition are either of type 1, or ϵ. As each step of this algorithm uses a bijection, p can be recovered from its final decomposition. This proves the following Corollary.

Corollary 1. There is a bijection H from the set of 2-stack sortable n-permutations onto the set of string (q_{1}, q_{2}, ⋯, q_{r}), where r ≥ 1 and

• for all i, q_{i} is either a 2-stack sortable permutation of type 1, or ϵ and

• ∑_{i=1}^{r} |q_{i}| = n,

• ∑_{i=1}^{r} rl(q_{i}) = rl(p),

• the total number of runs in the q_{i} equals the number of runs in p.

The last part follows from the last part of Lemma 2 and the fact that the number of runs in any permutation is one more than that of descents.

Cori, Jacquard and Schaeffer [2] give the following definition in their study of planar maps.

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

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

• 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 a nonroot internal node and v_{1}, v_{2}, ⋯, v_{k} are its children, then l(v) ≤

∑_{i=1}^{k} l(v_{k}).

Example 1. Two β(1, 0)-trees are shown in Figures 1a and 1b.

[figure: 1; 2; 1; 1; 1; 3; 3; Figure 1a; 1; 1; 1; 1; 2; 2; 1; Figure 1b]

Now we are in position to state and prove the main result of this paper.

Theorem 1. For any positive integer n and for any positive integer k ≤ n, there is a bijection B from the set of 2-stack sortable n-permutations with k runs onto that of β(1, 0)-trees on n + 1 nodes having k leaves. Therefore, W_{(n,k)} = T_{(n,k)}. Moreover, for any 2-stack sortable n-permutation p, the label of the root of B(p) equals rl(p).

Proof: We are going to prove the statements of the Theorem by induction on n and k. For k = 1 and any n, the statements are clearly true: there is one n-permutation with one run, namely 12 ⋯ n, and there is one β(1, 0)-tree having only one leaf, namely the one consisting of a single path. The root label of this tree is 1, and the number of right-to-left maxima of this permutation is 1, so the initial case is proved.

Now let k > 1 and suppose we already know the statements for all permutations shorter than n. Let p be any 2-stack sortable n-permutation with k runs.

• First suppose p is of type 1. Consider F (p), where F is the bijection defined in the proof of Lemma 1. Forget for now which vertex of F (p) is marked, then F (p) is a 2-stack sortable (n−1)-permutation with k runs. So, by our induction hypothesis, B associates a β(1, 0)-tree T′ on n nodes to it, which has k leaves and whose root label is equal to rl(F (p)) ≥ rl(p). Now add one node above the root x of T′ and “recall” which right-to-left maximum of F (p) was marked. If it was the tth right-to-left maximum, that is, if p had exactly t right-to-left maxima, then let the label of this new root x (and necessarily, that of the old root, which is the only child of x) be t. Then we certainly get a β(1, 0)-tree T as t ≤ rl(F (p)). We set B(p) = T. By the argument of Lemma 1 we see that p can be recovered from T (as T′, and thus F (p) can), and that T has k leaves, and its root label is rl(p) as it should be.

• If p = ϵ, then B(p) is the only β(1, 0)-tree on two nodes. We point out that here, as well as in the previous case, the root of B(p) has only one child.

• Now suppose p is of type 2. Take H(p) = (q_{1}, q_{2}, ⋯, q_{r}) as defined in Corollary 1 and consider B(q_{i}) for all i as defined by the previous two cases. B(q_{i}) has q_{i} + 1 nodes, so by contracting the roots of all B(q_{i}) to one node (keeping the B(q_{i}) ordered from left to right), we get a tree T with 1 + ∑_{i=1}^{r} |q_{i}| = n + 1 nodes. We set B(p) = T. The components q_{i} can be recovered from T by simply cutting off its root and adding a new root to the top of each component obtained. (Recall that in all the B(q_{i}), the root has only one child). The number of leaves of T equals the sum of the leaves of the B(q_{i}), so by the previous two cases and by Corollary 1, it equals the number of runs of p. The root label of T is by definition the sum of the labels of its children, which is, again by the previous two cases and by Corollary 1, equal to rl(p).

This completes the proof of the Theorem.

We remark that our algorithm certainly sets up a bijection between the set of all 2-stack sortable n-permutations and that of all β(1, 0)-trees on n + 1 vertices.

3. New enumerative results

Exercise 2.9.8.b in [5] shows that the number of nonseparable rooted planar maps with f + 1 faces and p + 1 vertices is equal to

\frac{(2f + p − 2)!(2p + f − 2)!}{f!p!(2f − 1)!(2p − 1)!}.  (2)

It is shown in [2] that the number of these maps equals the number of β(1, 0)-trees on n + 1 nodes with k = f + 1 leaves and n + 1 − k = p + 1 internal nodes. (Here the root is counted as an internal node). By Theorem 1 this implies the result we announced in the introduction.

Theorem 2. Let W_{(n,k)} be the number of 2-stack sortable n-permutations with k runs. Then for all 1 ≤ k ≤ n we have

W_{(n,k)} = \frac{(n + k − 1)!(2n − k)!}{k!(n + 1 − k)!(2k − 1)!(2n − 2k + 1)!}.

In particular, equation (2) shows that the roles of f + 1 = k and p + 1 = n + 1 − k are symmetric. In other words, W_{(n,k)} = W_{(n,n+1−k)}. A permutation with k runs has k − 1 descents, so have proved the following surprising Corollary.

Corollary 2. The number of 2-stack sortable n-permutations with k descents equals that of those with k ascents.

A routine computation yields that W_{(n,k)}/W_{(n,k−1)} > 1 if and only if k ≤ (n + 1)/2, and we already know from the previous Corollary that if n = 2k, then W_{(n,k)} = W_{(n,k+1)}. So we have proved the following Corollary.

Corollary 3. For fixed n, the sequence W_{(n,k)} is unimodal in k, and its peak is at k = [(n + 1)/2].

Acknowledgement

I am grateful to Gilles Schaeffer who sent me the preprint [2].

References

[1] M. Bóna, Exact enumeration of 1342-avoiding permutations; A close link with labeled trees and planar maps, Journal of Combinatorial Theory, Series A, to appear.

[2] R. Cori, B. Jacquard, G. Schaeffer, Description trees for some families of planar maps, Proceedings of the 9th Conference of Formal Power Series and Algebraic Combinatorics, to appear.

[3] 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), 85-103.

[4] 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), 220-242.

[5] I. P. Goulden, D. M. Jackson “Combinatorial Enumeration”, Wiley-Interscience, 1983.

[6] D. E. Knuth, “The art of computer programming,” volume 3, Sorting and searching, Addison-Wesley, Reading, Massachusetts, 1973.

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

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

[9] Sorting twice through a stack. Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991). Theoret. Comput. Sci. 117 (1993) 303-313.

[10] D. Zeilberger, A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!). Discrete Math. 102 (1992), 85-93.

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