.EQ
delim $$
.EN
.nr Pi 10
.nr Pt 1
\fBA PROOF OF JULIAN WEST'S CONJECTURE THAT THE NUMBER OF
TWO-STACK-SORTABLE
PERMUTATIONS OF LENGTH n IS 2(3n)!/((n+1)!(2n+1)!)
.SP1
.LP
\fIDoron Zeilberger*\fR
.FS*
Department of Mathematics, Temple University,
Philadelphia, PA19122. Supported in part by NSF grant DMS8901690.
.FE
.SP1
.S -2
.DS
A proof on the computer is just a physical experiment.
(Common sentiment among mathematicians)
.DE
.S P
.SP1
\fBAbstract\fR:
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.
.SP1
\fB(-1). Prologue\fR
.P
June 3, 1991: About a month ago, (10:30 AM, May 4, 1991, Bordeaux time, to
be precise), at the \fIS\*'eries formelles et combinatoire
alg\*'ebrique\fR
conference, 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 \fIconstruct\fR the proof. Once constructed, the
verification of the proof takes a few minutes of Maple CPU time
(on the above computer.)
.P
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.
.P
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 \fIweight-enumeration\fR.
The machine part is very tedious, but \fIwho cares?\fR.
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 \fIexperience\fR 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 \fIflavor\fR and \fIspirit\fR 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 sociological-psychological act of polemics,
and physics is a hard science, while sociology and psychology are
soft.
.SP1
\fB0. Introduction\fR
.P
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 $PI$ acting on permutations $pi$ of
a finite set $S$ of integers, with $n:=max(S)$, by the recursive
recipe:
.SP1
.EQ
PI ( pi sup L n pi sup R )~:=~ PI ( pi sup L ) PI ( pi sup R ) n~,~~
PI ( empty ) := empty .
.EN
.SP1
A permutation $pi$ is $k-stack-sortable$ if $PI sup k ( pi )$ 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)!)$.
.SP1
\fB1. How The Proof Was Found\fR
.SP1
\fBStep 0:\fR 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.
.SP1
\fBStep 1:\fR This is the purely human part, described in section 2.
Let $W sub n$ be the number of 2-stack-sortable permutations of
length $n$, and let $P(x)$ be its ordinary generating function:
.SP1
.EQ
P(x) := sum from n=0 to inf W sub n x sup n~~.
.EN
.SP1
Ideally, it would have been nice to find a recurrence for the
$W sub n$, or equivalently, some functional equation for $P(x)$
directly. I was unable to do so. Instead,
using the definition of $PI$, a bijection, and \fIweight enumeration\fR,
a functional equation for a more general
formal power series, $PHI (x,t)$, was obtained, that for
$t=1$ reduced to the former $P(x)$: $PHI (x,1)=P(x)$.
Unfortunately, it was \fInot\fR a plain \fIalgebraic\fR equation,
and furthermore plugging in $t=1$ resulted in the famous tautology
$0=0$. The functional equation was of the form
$G( PHI ( x,t) , PHI ( 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 sub 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.
.SP1
\fBStep 2 :\fR Put your faith in \fInotre bon mai\*^tre\fR,
and conjecture that $PHI (x,t) $ satisfies an algebraic
equation, i.e. there exists a polynomial $F$ in $( PHI ,x,t)$ such that
$F( PHI ,x,t) == 0 $. Systematically I tried raising the
degrees in $x$ and $PHI$, until Maple produced an "awful"
polynomial $F$ of degree $6$ in $PHI$, degree $8$ in $x$ and
degree $9$ in $t$. It was found by computing
$PHI (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( PHI , x, t)$ is given in the Maple program of the appendix.
.SP1
\fBStep 3:\fR Define $PSI (x,t)$ as the (unique formal
power series) solution of
the algebraic equation $F( PSI , x, t ) == 0$. Our goal
is to prove that $PSI == PHI$. A naive approach
is to "solve" $F( PSI , 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.
.P
The functional equation of step 1,
$G( PHI (x,t), PHI (x,1),x,t)$ is hard to work with, because
of the unwieldy $PHI (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 sub 1 ( PHI (x,t), PHI sub t (x,t), P, x,t)$. Finding the
resultant of $G( PHI ,P,x,t)$ and $G sub 1 ( PHI , PHI sub t , P , x, t)$,
w.r.t P, eliminates $P$ and yields an algebraic (first order)
differential equation for $PHI (x,t)$: $H( PHI , PHI sub t ,x,t ) =0$.
The Maple code that produces $H$ is given in the appendix.
.SP1
\fBStep 4\fR: Differentiate $F( PSI (x,t) , x,t ) == 0$, w.r.t
$t$, using the chain rule, to get
$PSI sub t (x,t) = -F sub t ( PSI ,x,t)/ F sub PSI ( PSI ,x,t )$.
Substitute it into $H( PSI , PSI sub t ,x,t)$, and find out
whether it's zero.
In other words, find out whether the numerator of
$H( PSI sub t , PSI , x, t)$ is an exact multiple
of the polynomial $F( PSI ,x,t)$. Maple said:
YES. Hence both $PSI$ and $PHI$ satisfy the same
algebraic differential equation $H == 0$, and it follows
by uniqueness that $PHI = PSI$. 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."
.SP1
\fBStep 5:\fR
Now we are on the home stretch. We need information
about $P(x):= PHI (x,1)$, which
we now know is equal to $PSI (x,1)$. Plugging in $t=1$
in $F( PSI (x,t) ,x,t)$, gives you $F( PSI (x,1),x,1)$ and
surprise! It equals:
.SP1
.EQ
x sup 2 (x-1) sup 3
(- 1 + P + 11 x - 14 P x + 2 P sup 2 x + x sup 2 + 3 P x sup 2 +
3 P sup 2 x sup 2 + P sup 3 x sup 2 ) sup 2~~~.
.EN
.SP1
Since the ring of formal power series has no zero divisors,
(and hence also no nilpotents), it follows that
.SP1
.EQ(1.1)
- 1 + P + 11 x - 14 P x + 2 P sup 2 x + x sup 2 + 3 P x sup 2 +
3 P sup 2 x sup 2 + P sup 3 x sup 2~=~0~~~,
.EN
.SP1
which is not quite yet doable by Lagrange inversion, but
we are getting close.
.SP1
\fBStep 6:\fR Now it's time to "peek at the answer at the end of the
book".
.SP1
.EQ
P(x):= sum from n=0 to inf W sub n x sup n~~~,
.EN
.SP1
satisfies (1.1). We want to prove that
$W sub n = 2 (3n)!/((2n+1)!(n+1)!)~,~n >= 1$. We do know that the
generating function $C(x)$ for ternary trees satisfies
$C=1+ x C sup 3$, and its coefficients $T sub n$ have the nice
formula, obtainable by Lagrange inversion (and otherwise),
$T sub 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- x D (x) sup 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.
.SP1
\fB2.The Human Part: Getting The Functional Equation Of Step 1\fR
.SP1
.P
For any permutation $pi$ of {$1,2, ... , n$}, let $i( pi )$ 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 sup (i)$, be the set of all permutations (of any length)
$pi$ such that $i( pi ) =i$, and let $W sup {>= i} $ be the set
of permutations $pi$ such that $i( pi ) >= i$.
.P
Let's analyze a typical member of $W sup {>= i}$. If its
length is $n$, then it has the form
.SP1
.EQ(2.1)
pi~=~sigma sub 0 n sigma sub 1 (n-1) ... (n-i+1) sigma sub i~~,
.EN
.SP1
where $sigma sub 0 , ... , sigma sub 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 $PI$,
.SP1
.EQ
PI ( pi ) = PI ( sigma sub 0 ) PI ( sigma sub 1 ) ...
PI ( sigma sub i ) (n-i+1) (n-i+2) ... n~~~,
.EN
.SP1
so that,
.SP1
.EQ
PI sup 2 ( pi ) = PI ( PI ( sigma sub 0 ) PI ( sigma sub 1 ) ...
PI ( sigma sub i ) ) (n-i+1) ... n~~~.
.EN
.SP1
It follows that there is a 1-1 correspondence between
the elements of $W sup { >= i}$ and $i+1$-tuples of
permutations $sigma sub 0 , ... , sigma sub i$, such that
$PI ( PI ( sigma sub 0 ) ... PI ( sigma sub i ) )$ equals the "identity"
(i.e. the increasing permutation),
and the underlying sets of the $sigma$'s are disjoint and their union is
{$1, 2, ... , n-i$}.
.P
Consider now a typical element of $W sup (i)$,\fIexcept\fR
the following permutation of length $i$: $i,i-1,..., 1$. It still
has the form (2.1) \fIbut\fR $n-i$ should not be in $sigma sub 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$:
.SP1
.EQ(2.2)
n (n-1) ... (n-j+1) (n-i) (n-j) ... (n-i+1)~~~.
.EN
.SP1
Padding in the rest, we get that a typical $pi$ of length n,
belonging to $W sup (i)$ has the form
.SP1
.EQ
pi~=~sigma sub 0 n sigma sub 1
(n-1) sigma sub 2 ... sigma sub j-1 (n-j+1) sigma bar (n-i)
sigma sub j (n-j) sigma sub j+1 ... sigma sub i-1 (n-i+1) sigma sub i~.
.EN
.SP1
It follows from the definition of $PI$ that
.SP1
.EQ
PI ( pi ) =
PI ( sigma sub 0 ) ... PI ( sigma sub j-1 )
PI ( sigma bar (n-i) sigma sub j (n-j) sigma sub j+1 ...
sigma sub i-1 (n-i+1) sigma sub i )~ (n-j+1) ... n~~=~~
.EN
.SP1
.EQ
PI ( sigma sub 0 ) ... PI ( sigma sub j-1 )
PI ( sigma bar (n-i) sigma sub j )
PI ( sigma sub j+1 (n-j-1) ... sigma sub i-1 (n-i+1) sigma sub i )
(n-j) (n-j+1) ... n ~=
.EN
.SP1
.EQ
PI ( sigma sub 0 ) ... PI ( sigma sub j-1 )
PI ( sigma bar ) PI ( sigma sub j ) ~ (n-i) ~
PI ( sigma sub j+1 ) ... PI ( sigma sub i ) (n-i+1) ... n~~~.
.EN
.SP1
Now apply $PI$ again, to get
.SP1
.EQ
PI sup 2 ( pi ) ~=~
PI ( PI ( sigma sub 0 ) ... PI ( sigma bar ) PI ( sigma sub j ) )
PI ( PI ( sigma sub j+1 ) ... PI ( sigma sub i ) )
(n-i) (n-i+1) ... n~~~.
.EN
.SP1
It follows that every element of $W sup (i)$, except the
excluded permutation $(i,i-1,...,1)$, corresponds to a pair
of tuples of permutation, for some $ 0 <= j <= i-1$,
.SP1
.EQ
[( sigma sub 0 , ... , sigma bar , sigma sub j ),
( sigma sub j+1 , ... , sigma sub i ) ]~~~,
.EN
.SP1
such that both
$PI ( PI ( sigma sub 0 ) ... PI ( sigma sub j ) )$ and
$PI ( PI ( sigma sub j+1 ) ... PI ( sigma sub i ) )$
are the identity permutation, and the underlying sets
satisfy the obvious requirements. But we saw that
these correspond to members of $W sup {>= j+1}$ and
$W sup {>= i-j-1}$ respectively. So we have a bijection
.SP1
.EQ(2.3)
W sup (i) size +3 ->
"{" (i, i-1 , ... , 1 ) "}" union
{size +4 union} from j=0 to i-1 W sup { >= j+1 }
~size -3 times ~ W sup { >= i-j-1}~~, ~~
pi -> ( pi sub 1 , pi sub 2 )~~~,
.EN
.SP1
such that
$length ( pi ) = length ( pi sub 1 ) + length ( pi sub 2 ) +1$.
.P
For each permutation $pi$, introduce the weight:
.SP1
.EQ
weight ( pi ) := x sup {length ( pi )}~~~,
.EN
.SP1
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 \fIPolya-Schutzenberger-Tutte transform\fR), we get
.SP1
.EQ(2.4)
W sup (i) (x) = x sup i + x sum from j=0 to i-1
W sup {>= j+1 } (x) W sup { >= i-j-1 } (x)~~~.
.EN
.SP1
.P
Now let
.SP1
.EQ
PHI (x,t) := sum from i=0 to inf W sup (i) (x) t sup i~~~.
.EN
.SP1
It is easily seen that if we define
.SP1
.EQ
PHI bar (x,t) := sum from i=0 to inf W sup {>= i} (x) t sup i~~~,
.EN
.SP1
then
.SP1
.EQ(2.5)
PHI bar (x,t) = sum from { j >= i >= 0 } W sup (j) (x) t sup i ~=~
sum from j=0 to inf W sup (j) (1+t+ ... + t sup j )~=~
.EN
.SP1
.EQ
sum from j=0 to inf W sup (j) (1- t sup j+1 )/(1-t)~=~
( PHI (x,1) - t PHI (x,t))/(1-t)~~~.
.EN
.SP1
Now (2.4) can be written as
.SP1
.EQ
W sup (i) (x) = x sup i + x sum from j=0 to i
W sup {>= j } (x) W sup { >= i-j } (x)~-~ x
W sup { >= 0 } (x) W sup { >= i } (x)~~.
.EN
.SP1
Multiplying both sides by $t sup i$ and summing from $i=0$ to
$inf$, realizing that the middle term on the right is a convolution,
and that $W sup { >= 0} = PHI (x,1)$,
we get
.SP1
.EQ
PHI (x,t) = 1 over (1-xt) + x PHI bar ( x, t) sup 2 - x PHI ( x, 1)
PHI bar (x,t)~~~,
.EN
.SP1
which upon substituting for $PHI bar (x,t)$ its expression (2.5)
in terms of $PHI (x,t)$, we get (recall that $PHI (x,1) = P$)
.SP1
.EQ
PHI ~-~ 1 over 1-xt ~-~
{ x t (P- t PHI ) (P - PHI ) }
over
{(1-t) sup 2 }~=0~~~,
.EN
.SP1
which by clearing denominators, and taking the numerator,
finally yields the functional equation $G( PHI , P, x,t ) == 0$,
promised in step 1 of section 1.
.SP1
\fB $bold omega$. Epilogue: How The Proof Could Have Been Found\fR
.SP1
.P
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.
.SP1
\fBStep 2'\fR: Conjecture $I(P(x),x))=0$
((1.1)) empirically. To prove it rigorously,
we must show that the unique $ PSI (x,t)$ that satisfies
$G( PSI (x,t), PSI (x,1),x,t) == 0$, is such that $I( PSI (x,1),x) == 0$.
Let's write,
.SP1
.EQ
(i) G( PSI (x,t) , Q(x) , x, t ) == 0 ~~, ~~(ii) PSI (x,1) = Q(x) ~~,~~
(iii) I( Q(x) , x ) == 0 ~.
.EN
.SP1
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( PSI , 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 \fIleitmotif\fR of a paper [GZ] that Ira Gessel
and I hope to write.
.SP1
\fBReferences\fR
.SP1
[GZ] I. Gessel and D. Zeilberger, \fIAn empirical method for
solving (rigorously) algebraic-functional equations of the form
$F( P(x,t),P(x,1),x,t) == 0$\fR (temporary title), in planning.
.SP1
[P] G. Polya, \fIOn picture writing\fR, Amer. Math. Monthly \fB63\fR
(1956), 689-697. Reprinted in: "\fICLASSICAL PAPERS IN COMBINATORICS\fR",
edited by I. Gessel and G. -C. Rota, Birkhauser, Boston, 1987, pp.
249-258.
.SP1
[S] M. P. Schutzenberger, \fIContext free languages and pushdown
automata\fR, Information and Control \fB6\fR(1963), 246-264.
.SP1
[T] W.T. Tutte, \fIOn the theory of chromatic polynomials\fR,
Canadian J. Math. \fB68\fR(1954), 101-121.
.SP1
[W1] Julian West, \fI"Permutations with restricted subsequences and
stack-sortable permutations"\fR, doctoral thesis, M.I.T., 1990.
.SP1
[W2] _____,\fISorting twice through a stack\fR, Proceedings of
\fIS\*'eries Formelles et Combinatoire Alg\*'ebrique\fR (M. Delest,
G. Jacob, and P. Leroux, eds.) 397-406. Also to appear in
J. Theoretical Computer Science.
.SP1