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)!)

Doron Zeilberger *

Appeared in: Discrete Math. 102 (1992), 85-93.

A proof on the computer is just a physical experiment.—– (Common sentiment among mathematicians)

Abstract: The Polya-Schutzenberger-Tutte methodology of weight enumeration, combined with about 10 hours of CPU time (of Maple running on Drexel University’s Sun network) established Julian West’s conjecture that 2-stack-sortable permutations are enumerated by sequence #651 in the Sloane listing.

(-1). Prologue

June 3, 1991: About a month ago, (10:30 AM, May 4, 1991, Bordeaux time, to be precise), at the Séries formelles et combinatoire algébriqueconference, Julian West gave an enthralling talk which contained an intriguing conjecture: a certain naturally defined combinatorial family is enumerated by a certain nice formula. First I was sure that I could do it the same night. Then I was certain that it would be proved during the 8-hour plane ride back home. Well, it took longer than expected, and required about 50 mathematician-hours, 10 (Maple) programmer-hours, (the mathematician and programmer being myself), and 10 CPU-hours to construct the proof. Once constructed, the verification of the proof takes a few minutes of Maple CPU time (on the above computer.)

The proof would not have been possible without the generous and kind permission of Drexel’s Mathematics and Computer Science Head, James C.T. Pool, to use the Drexel computing facilities.

People who detest the Appel-Haken proof of the 4 Color Theorem would probably not like the present proof either. I like both proofs very much. The human part of the present proof is very elegant, using the Polya-Schutzenberger-Tutte ([P],[S],[T]) powerful methodology of weightenumeration. The machine part is very tedious, but who cares?. Certainly not the machine, who is always happy to be useful. Another reason why I liked working on this project is that I got to experience what it’s like to be an experimental scientist. Both the construction of the proof, and its final verification, used the methodology of experimental science. The resulting proof is as rigorous and valid as any old fashioned proof, but the flavorand spirit of the proof are experimental, and making it rigorous amounts to just mumbling a few words. I agree with the motto if you delete the word ”just”, which turns it from a curse to a blessing. After all, a human proof is just a sociologicalpsychological act of polemics, and physics is a hard science, while sociology and psychology are soft.

0. Introduction

In his remarkable thesis [W1][W2], Julian West introduced a fascinating new kind of combinatorial objects: k-stack-sortable permutations. They may defined as follows ([W2], lemma 5). Define a mapping Π acting on permutations π of a finite set S of integers, with n := max(S), by the recursive recipe:

* Department of Mathematics, Temple University, Philadelphia, PA19122. Supported in part by NSF grant DMS8901690.

Π(π^{L}nπ^{R}) := Π(π^{L})Π(π^{R})n , Π(empty) := empty.

A permutation π is k − stack − sortable if Π^{k}(π) equals the identity permutation. As observed by West, the number of 1-stack-sortable permutations on n objects is well known to be Catalan’s number (2n)!/((n)!(n + 1)!). West conjectured that the number of 2-stack sortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!).

1. How The Proof Was Found

Step 0: Use West’s[W2] characterization of 2-stack-sortable permutations as permutations avoiding such and such kind of subsequences to get a hold on them. Approach abandoned and two weeks wasted.

Step 1: This is the purely human part, described in section 2. Let W_{n} be the number of 2-stack-sortable permutations of length n, and let P (x) be its ordinary generating function:

P (x) := ∑_{n=0}^{∞} W_{n}x^{n} .

Ideally, it would have been nice to find a recurrence for the W_{n}, or equivalently, some functional equation for P (x) directly. I was unable to do so. Instead, using the definition of Π, a bijection, and weight enumeration, a functional equation for a more general formal power series, Φ(x, t), was obtained, that for t = 1 reduced to the former P (x): Φ(x, 1) = P (x). Unfortunately, it was nota plain algebraic equation, and furthermore plugging in t = 1 resulted in the famous tautology 0 = 0. The functional equation was of the form G(Φ(x, t), Φ(x, 1), x, t) ≡ 0, for some 4-variate polynomial G given in section 2. The functional equation did however give an effective way to compute the West numbers W_{n} much beyond n = 11, that West[W2] computed by directly enumerating permutations. This corroborated West’s conjecture and safely moved it outside the jurisdiction of the law of small numbers.

Step 2 :Put your faith in notre bon maitre, and conjecture that Φ(x, t) satisfies an algebraic equation, i.e. there exists a polynomial F in (Φ, x, t) such that F (Φ, x, t) ≡ 0. Systematically I tried raising the degrees in x and Φ, until Maple produced an ”awful” polynomial F of degree 6 in Φ, degree 8 in x and degree 9 in t. It was found by computing Φ(x, t) up to a sufficiently large power of x, using the functional equation of step 1, plugging into the generic F, and setting the coefficients of the powers of x to zero, until one gets enough linear equations for the coefficients of F. However, if you do it naively, you will run out of memory pretty fast. So you plug in many specific values of t and then combine them together by ”Lagrange” (or rather ”Pade”) interpolation. F (Φ, x, t) is given in the Maple program of the appendix.

Step 3: Define Ψ(x, t) as the (unique formal power series) solution of the algebraic equation F (Ψ, x, t) ≡ 0. Our goal is to prove that Ψ ≡ Φ. A naive approach is to ”solve” F (Ψ, x, t) ”explicitly”, say by radicals, and verify that it satisfies the functional equation G = 0 of step 1. However, Maple was unable to do it.

The functional equation of step 1, G(Φ(x, t), Φ(x, 1), x, t) is hard to work with, because of the unwieldy Φ(x, 1), which is P (x). By differentiating G w.r.t t, and using the chain rule, one obtains a first order algebraic differential equation G_{1}(Φ(x, t), Φ_{t}(x, t), P, x, t). Finding the resultant of G(Φ, P, x, t) and G_{1}(Φ, Φ_{t}, P, x, t), w.r.t P, eliminates P and yields an algebraic (first order) differential equation for Φ(x, t): H(Φ, Φ_{t}, x, t) = 0. The Maple code that produces H is given in the appendix.

Step 4: Differentiate F (Ψ(x, t), x, t) ≡ 0, w.r.t t, using the chain rule, to get Ψ_{t}(x, t) = −F_{t}(Ψ, x, t)/F_{Ψ}(Ψ, x, t). Substitute it into H(Ψ, Ψ_{t}, x, t), and find out whether it’s zero. In other words, find out whether the numerator of H(Ψ_{t}, Ψ, x, t) is an exact multiple of the polynomial F (Ψ, x, t). Maple said: YES. Hence both Ψ and Φ satisfy the same algebraic differential equation H ≡ 0, and it follows by uniqueness that Φ = Ψ. Even here we had to be clever, since a direct verification resulted in the error message: ”object too large”. We found out the appropriate degrees in x, t, and plugged in enough special cases. We then use the fact that ”if a polynomial of degree ≤ r is 0 in r+1 distinct values, it is identically zero.”

Step 5: Now we are on the home stretch. We need information about P (x) := Φ(x, 1), which we now know is equal to Ψ(x, 1). Plugging in t = 1 in F (Ψ(x, t), x, t), gives you F (Ψ(x, 1), x, 1) and surprise! It equals:

x^{2}(x − 1)^{3}(−1 + P + 11x − 14P x + 2P^{2}x + x^{2} + 3P x^{2} + 3P^{2}x^{2} + P^{3}x^{2})^{2} .

Since the ring of formal power series has no zero divisors, (and hence also no nilpotents), it follows that

−1 + P + 11x − 14P x + 2P^{2}x + x^{2} + 3P x^{2} + 3P^{2}x^{2} + P^{3}x^{2 = 0 ,}  (1.1)

which is not quite yet doable by Lagrange inversion, but we are getting close.

Step 6: Now it’s time to ”peek at the answer at the end of the book”.

P (x) := ∑_{n=0}^{∞} W_{n}x^{n ,}

satisfies (1.1). We want to prove that W_{n} = 2(3n)!/((2n + 1)!(n + 1)!) , n ≥ 1. We do know that the generating function C(x) for ternary trees satisfies C = 1 + xC^{3}, and its coefficients T_{n} have the nice formula, obtainable by Lagrange inversion (and otherwise), T_{n} = (3n)!/(n!(2n + 1)!). We want to prove that C(x) = (1 + (xP (x))′)/2. Differentiating (1.1) w.r.t x, we find an expression for P′(x) in terms of P (x) and x, set D(x) := (1 + (xP (x))′)/2, evaluate D(x) − 1 − xD(x)^{3} and verify that its numerator is a multiple of the left side of (1.1), and hence is identically zero, and hence C(x) = D(x). QED.

2.The Human Part: Getting The Functional Equation Of Step 1

For any permutation π of 1, 2, ..., n, let i(π) be the largest integer i such that the subsequence of the ”big i”: n − i + 1, ..., n − 1, n are in decreasing order. Let W^{(i)}, be the set of all permutations (of any length) π such that i(π) = i, and let W^{≥i} be the set of permutations π such that i(π) ≥ i.

Let’s analyze a typical member of W^{≥i}. If its length is n, then it has the form

π = σ_{0}nσ_{1}(n − 1)...(n − i + 1)σ_{i ,}  (2.1)

where σ_{0}, ..., σ_{i} are (possibly empty) permutations of disjoint smaller sets, the union of whose underlying sets is 1, 2, ..., n − i. Now, by iterating the definition of Π,

Π(π) = Π(σ_{0})Π(σ_{1})...Π(σ_{i})(n − i + 1)(n − i + 2)...n ,

so that,

Π^{2}(π) = Π(Π(σ_{0})Π(σ_{1})...Π(σ_{i}))(n − i + 1)...n .

It follows that there is a 1-1 correspondence between the elements of W^{≥i} and i+1-tuples of permutations σ_{0}, ..., σ_{i}, such that Π(Π(σ_{0})...Π(σ_{i})) equals the ”identity” (i.e. the increasing permutation), and the underlying sets of the σ’s are disjoint and their union is 1, 2, ..., n − i.

Consider now a typical element of W^{(i)},except the following permutation of length i: i, i − 1, ..., 1. It still has the form (2.1) but n − i should not be in σ_{i}. In other words, although the ”big i” are in decreasing order, the ”big i + 1” are not, so the subsequence consisting of the ”big i + 1” looks as follows, for some 0 ≤ j ≤ i − 1:

n(n − 1)...(n − j + 1)(n − i)(n − j)...(n − i + 1) .  (2.2)

Padding in the rest, we get that a typical π of length n, belonging to W^{(i)} has the form

π = σ_{0}nσ_{1}(n − 1)σ_{2}...σ_{j−1}(n − j + 1)σ̄(n − i)σ_{j}(n − j)σ_{j+1}...σ_{i−1}(n − i + 1)σ_{i} .

It follows from the definition of Π that

Π(π) = Π(σ_{0})...Π(σ_{j−1})Π(σ̄(n − i)σ_{j}(n − j)σ_{j+1}...σ_{i−1}(n − i + 1)σ_{i}) (n − j + 1)...n =

Π(σ_{0})...Π(σ_{j−1})Π(σ̄(n − i)σ_{j})Π(σ_{j+1}(n − j − 1)...σ_{i−1}(n − i + 1)σ_{i})(n − j)(n − j + 1)...n =

Π(σ_{0})...Π(σ_{j−1})Π(σ̄)Π(σ_{j}) (n − i) Π(σ_{j+1})...Π(σ_{i})(n − i + 1)...n .

Now apply Π again, to get

Π^{2}(π) = Π(Π(σ_{0})...Π(σ̄)Π(σ_{j}))Π(Π(σ_{j+1})...Π(σ_{i}))(n − i)(n − i + 1)...n .

It follows that every element of W^{(i)}, except the excluded permutation (i, i − 1, ..., 1), corresponds to a pair of tuples of permutation, for some 0 ≤ j ≤ i − 1,

[(σ_{0}, ..., σ̄, σ_{j}), (σ_{j+1}, ..., σ_{i})] ,

such that both Π(Π(σ_{0})...Π(σ_{j})) and Π(Π(σ_{j+1})...Π(σ_{i})) are the identity permutation, and the underlying sets satisfy the obvious requirements. But we saw that these correspond to members of W^{≥j+1} and W^{≥i−j−1} respectively. So we have a bijection

W^{(i)} → {(i, i − 1, ..., 1)} ∪ ∪_{j=0}^{i−1}W^{≥j+1} × W^{≥i−j−1} , π → (π_{1}, π_{2}) ,  (2.3)

such that length(π) = length(π_{1}) + length(π_{2}) + 1.

For each permutation π, introduce the weight:

weight(π) := x^{length(π)} ,

and, by abuse of notation, from now on, for any set of permutations S, let S(x) be the formal power series that equals the sum of all the weights of the elements of S. By taking weights on both sides of (2.3) (the Polya-Schutzenberger-Tutte transform), we get

W^{(i)}(x) = x^{i} + x ∑_{j=0}^{i−1} W^{≥j+1}(x)W^{≥i−j−1}(x) .  (2.4)

Now let

Φ(x, t) := ∑_{i=0}^{∞} W^{(i)}(x)t^{i} .

It is easily seen that if we define

Φ̄(x, t) := ∑_{i=0}^{∞} W^{≥i}(x)t^{i ,}

then

Φ̄(x, t) = ∑_{j≥i≥0} W^{(j)}(x)t^{i} = ∑_{j=0}^{∞} W^{(j)}(1 + t + ... + t^{j}) =  (2.5)

∑_{j=0}^{∞} W^{(j)}(1 − t^{j+1})/(1 − t) = (Φ(x, 1) − tΦ(x, t))/(1 − t) .

Now (2.4) can be written as

W^{(i)}(x) = x^{i} + x ∑_{j=0}^{i} W^{≥j}(x)W^{≥i−j}(x) − xW^{≥0}(x)W^{≥i}(x) .

Multiplying both sides by t^{i} and summing from i = 0 to ∞, realizing that the middle term on the right is a convolution, and that W^{≥0} = Φ(x, 1), we get

Φ(x, t) = \frac{1}{(1 − xt)} + xΦ̄(x, t)^{2} − xΦ(x, 1)Φ̄(x, t) ,

which upon substituting for Φ̄(x, t) its expression (2.5) in terms of Φ(x, t), we get (recall that Φ(x, 1) = P)

Φ − \frac{1}{1 − xt} − \frac{xt(P − tΦ)(P − Φ)}{(1 − t)^{2}} = 0 ,

which by clearing denominators, and taking the numerator, finally yields the functional equation G(Φ, P, x, t) ≡ 0, promised in step 1 of section 1.

ω. Epilogue: How The Proof Could Have Been Found

July 2, 1991: The first proof of any conjecture is seldom the shortest. It turns out that the present proof is no exception. Ira Gessel made the brilliant observation that steps 2-5 can be replaced by the following.

Step 2’: Conjecture I(P (x), x)) = 0 ((1.1)) empirically. To prove it rigorously, we must show that the unique Ψ(x, t) that satisfies G(Ψ(x, t), Ψ(x, 1), x, t) ≡ 0, is such that I(Ψ(x, 1), x) ≡ 0. Let’s write,

(i)G(Ψ(x, t), Q(x), x, t) ≡ 0 , (ii)Ψ(x, 1) = Q(x) , (iii)I(Q(x), x) ≡ 0 .

We have to prove that (i)+(ii) implies (iii). But note that (i)+(ii) have a unique solution, and (i)+(iii) have a unique solution, and we must show that these are the same. So it’s enough to show that (i)+(iii) implies (ii). Taking the resultant of G and I w.r.t. Q(x) gives the algebraic equation F (Ψ, x, t) ≡ 0 found empirically, and very painfully, in step 3. Proceeding as in step 5, we see that indeed Q(x) = P (x). This observation is the leitmotif of a paper [GZ] that Ira Gessel and I hope to write.

References

[GZ] I. Gessel and D. Zeilberger, An empirical method for solving (rigorously) algebraic-functional equations of the form F (P (x, t), P (x, 1), x, t) ≡ 0(temporary title), in planning.

[P] G. Polya, On picture writing, Amer. Math. Monthly 63 (1956), 689-697. Reprinted in: ”CLASSICAL PAPERS IN COMBINATORICS”, edited by I. Gessel and G. -C. Rota, Birkhauser, Boston, 1987, pp. 249-258.

[S] M. P. Schutzenberger, Context free languages and pushdown automata, Information and Control 6(1963), 246-264.

[T] W.T. Tutte, On the theory of chromatic polynomials, Canadian J. Math. 68(1954), 101-121.

[W1] Julian West, ”Permutations with restricted subsequences and stack-sortable permutations”, doctoral thesis, M.I.T., 1990.

[W2] ,Sorting twice through a stack, Proceedings of Séries Formelles et Combinatoire Algébrique (M. Delest, G. Jacob, and P. Leroux, eds.) 397-406. Also to appear in J. Theoretical Computer Science.