  
%catalan.tex: Plain TeX file of the paper `Catalan Strikes Again (and Again)*'
%by Doron Zeilberger
%
%begin macros
\def\mod{\mathop{\rm mod} \nolimits}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
%end macros
\bf
\centerline
{\bf CATALAN STRIKES AGAIN (AND AGAIN)$^*$}
\rm
\bigskip
\centerline{ {\it Doron ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. 
%\break
{\eighttt zeilberg@math.temple.edu .}
Supported in part by the NSF. First version: Jan. 26, 1995.
This version: Mar. 6, 1995.
This paper, and many other papers, are available via anonymous
ftp to {\eighttt ftp.math.temple.edu}, in directory 
{\eighttt pub/zeilberg/papers}, and also via Mosaic to 
http://www.math.temple.edu/\~{}zeilberg. If the above is down
(a frequent event), then try the mirror ftp site: {\eighttt ftp.temple.edu},
in directory {\eighttt /pub/math/Zeilberger}.
This paper is not
going to be `published' elsewhere.
} 
}
\medskip
{\bf 1. Francesco Brenti's Conjecture}
 
In the very first day of the Oberwolfach meeting
on Enumerative Combinatorics and the Symmetric Group (Jan. 16-20, 1995),
during the morning session, Francesco Brenti gave a wonderful talk
about his combinatorial approach to the Kazhdan-Lusztig polynomials ([B1][B2]).
Among much harder and deeper conjectures, he has made a
conjecture involving the Catalan numbers.
 
Brenti recursively defines a sequence of polynomials $B_n(q)$ with the aid of
operators $V_r$ (where $r$ is any (real) number), acting
on polynomials by:
 
$$
V_r ( \sum_{i=0}^{degree} a_i q^i )=
\sum_{i \geq r}^{degree} a_i q^i  \quad .
$$
 
Define $B_1(q) := -1$, and for $n>1$:
$$
B_n (q) = (q-1) B_{n-1} (q) + V_{(n+1)/2} \left ( \,\,
q^{n-1} (1-q) B_{n-1} (1/q)  \,\,
\right )
\quad.
$$
 
In his talk, Brenti made the following conjecture.
 
{\bf Conjecture:} $B_{2n}(1)=B_{2n+1}(1)=(-1)^{n+1} C_n $.
 
Here, as usual, $C_n$ denote the omnipresent Catalan numbers
$(2n)!/(n!(n+1)!)$.
 
Shortly after the talk, during lunch, I had the good fortune to share
a table with Francesco (an event whose probability is roughly
$6/42=1/7$). Half-jokingly, I suggested that he should offer prizes for
his conjectures, including the one above. He replied, very wisely, that
since these conjectures were only made recently, he 
does not know yet how hard they really
are, and hence it would be premature to offer prizes. Then I tried the
next best thing: a bet of $10$ German marks, that I would be able to solve
his conjecture by the end of the meeting. To this Francesco graciously
agreed.
 
I was a little worried, though, that my preoccupation with this problem
would prevent me from paying due attention to the many other interesting
talks that were going to be delivered, and that I would get into the bad habit,
practiced by some of my best friends, of doing one's own work
during other people's talks.
 
Luckily, I won the bet that very same afternoon. I was especially
proud that I did it completely the old-fashioned way, not breaking
the promise to myself not to go near the computer during that 
week.\footnote{$^2$}{ \eightrm Had I used the computer (with Maple), it
would probably have taken me half an hour rather than three hours.}
 
To prove Brenti's conjecture, I will exhibit explicit expressions
for the $B_n(q)$.
 
{\bf Proposition:}
 
$$
B_{2n} (q)= 
(-1)^n {{1} \over {2n+1}} {{2n+1} \choose {n}} q^n \, + \,
\sum_{i=0}^{n-1}
(-1)^i {{2n-2i+1} \over {2n+1}} {{2n+1} \choose {i}} ( q^i + q^{2n-i} )
\quad ,
$$
 
$$
B_{2n+1} (q) =
\sum_{i=0}^{n}
(-1)^{i+1} {{n-i+1} \over {n+1}} {{2n+2} \choose {i}}  q^i
\quad .
$$
 
{\bf Proof:} \halmos.
 
{\bf Corollary:}  $B_{2n}(1)=B_{2n+1}(1)=(-1)^n C_n $.
 
{\bf Proof:} \halmos.\footnote{$^3$}{\eightrm When $q=1$ the sums are
Gosper-summable, so this was routine since 1977, and could be done
with Macsyma's {\eighttt nusum}, or Maple's {\eighttt sum}. }
 
{\bf Note}: After this note was written, Brenti informed me that
he has found a combinatorial interpretation of his (generalized)
polynomials that implies his Catalan conjectures.
 
{\bf 2. Richard Stanley's Question}
 
During one of the breaks of the last day of the same meeting,
Richard Stanley asked me whether I would be able to 
find a bijective proof for a new
enumerative result, due to his student Alexander Postnikov[S], that
a certain new kind of trees, on $n$ vertices, are
enumerated by the Catalan number $C_{n-1}$.
Let's call these trees one-Sided Trees, Arcs Non-nesting,
Leaving Edges Yearning (to be together), or 
STANLEY\footnote{$^4$}
{\eightrm Richard Stanley has since informed me that his only contribution
was to tell me about them, and that these trees were introduced by
Gelfand, Graev and Postnikov[GGP], and hence should be called GGP trees.}
for short.
Let's first define them.
 
{\bf Definition}: A  {\it Stanley tree} on $n$ vertices labelled
$\{ 1, 2, \dots , n \}$ is a tree satisfying the following two conditions
 
(I) If $1 \leq i < j < k \leq n$ then $\{ i , j \}$ and $\{ j,k \}$
can't both be edges.
 
(II) If $1 \leq i< j < k < l \leq n$, then $\{i,l\}$ and
$\{ j,k \}$ can't both be edges.
 
The quintessential Catalan family is the set of `legal parenthesing'
(alias `Dyck words', `Ballot paths',`Pascal Programs', etc. etc.), 
which are words in the alphabet $\{ ( , ) \}$ with as many
left parentheses as right parentheses, with the
property that each `left factor' (i.e. prefix) has never more right 
parentheses
than left ones. For typographical reasons, we will use
$B$ for `left parenthesis' and $E$ for `right  parenthesis', or 
alternatively think of Pascal programs with $B$ meaning `begin'
and $E$ meaning `end'.
 
Most of us know at least one proof\footnote{$^5$}
{\eightrm I know at least ten (distinct) proofs. My favorite
goes as follows: Use the Sch\"utzenberger methodology to
deduce the equation $\phi(z)=1+ z \phi(z)^2$ for their
generating function, then use the Maple
package {\eighttt gfun} (written by
B. Salvy and P. Zimmermann and inspired by F. Bergeron and
S. Plouffe) with the command {\eighttt algtodiff} followed
by the command {\eighttt difftorec}}
that these are
enumerated by $C_n$. The set  of `irreducible' legal parenthesings are
those of the form $BwE$, where $w$ is a legal parenthesing.
Obviously the number of irreducible
legal parenthesings with $n$ pairs is $C_{n-1}$. 
 
I will now describe the bijection that I (essentially) found that
very same night (Jan. 20, 1995, 23:06 local time, to be precise).
Luckily Stanley was still up, preparing himself a late-night snack, so
that I was able to show him the bijection right away.
(Of course I did not have the guts to wager a bet with Richard
Stanley, but impressing him is its own reward (far exceeding
$10$ marks (or even $10$ dollars)).
 
{\bf Bijection $\pi$:} 
 
{\bf Input:} A Stanley tree $T$, with $n$ vertices
labelled $\{ 1, 2, \dots , n \}$, given by its set of
$(n-1)$ edges.
 
{\bf Output:} An irreducible legal parenthesing with $n$ $B$'s and $n$ $E$'s.
 
The first step is to determine the `exterior arc structure', a certain 
non-empty
set of edges  $L=\{ \{i_1 , j_1 \} , \dots , \{i_k , j_k \}\}$ as follows.
Let $j_0:=0$, and let $i_1:=1$.
For $r$ from $1$ (incremented by $1$) {\it do}:
$$
j_r:= \max \,\{ \,j \,\vert \, \{ i_r , j \} \in T \} \quad .
$$
If $j_r=n$ then exit, else
$$
i_{r+1}:= \min \{ \,i \,\vert \,i > i_r \quad such \quad that \quad there
\quad exists \quad j > j_r \quad such \quad that \quad \{i,j\} \in T \} \quad ,
\quad end\,\,do.
$$
 
Now let's describe the mapping $\pi$. Start with
the $n$-lettered `word' $1 2 3 \dots n$ and replace all $i_r$
($r=1, \dots , k$) by $BB$, and 
all $j_r$'s ($r=1, \dots , k$) by  $EE$.
For each of the remaining vertices $v$, it is easy to see that it
can be incident to exactly one edge and that its sole
neighbor must be one of two vertices (the smallest
$i_r$ such that $i_r < v < j_r$, or the largest $j_r$ such that
$i_r<v<j_r$.) In the former case, replace $v$ by $BE$, and 
in the latter, replace $v$ by $EB$.
 
I leave it to the reader, as an amusing exercise, to prove
that this indeed outputs an irreducible legal parenthesing,
and to construct the
inverse bijection $\sigma$, and to formally prove that
$\pi \sigma$ and $\sigma \pi$ are both the identity mapping,
hence verifying my claim that $\pi$ is indeed a bijection. \halmos
 
An alternative proof, that I am sure would be rigorizable in a few
years, would be to program this mapping, and check empirically
that it works for, say, $1 \leq  n \leq 10$. In other words, not
only identities, but even bijections (satisfying certain conditions),
are going to be shaloshable.
 
As a {\it lagniappe}, we also get the shaloshable, but 
charming identity:
 
$$
C_{n-1}= \sum_{1 \leq k \leq n/2} 
 2^{n-2k} {{n-2} \choose {2k-2}} C_{k-1} \quad .
$$
 
{\bf Note 1:} An even nicer bijection was found independently by
Michael Schlosser, a student of Christian Krattenthaler.
 
 
{\bf Note 2}: A Maple implementation of the bijections $\pi$ and
$\sigma$ can be obtained as described in footnote 1, in file
{\tt pub/zeilberg/programs/catalan} (or via Mosaic.)
In order to use it (once you downloaded it into
the current directory), just get into Maple, and then type
`read catalan;'.
 
{\bf References}
 
[B1] Francesco Brenti, {\it A combinatorial formula for the Kazhdan-Lusztig
polynomials}, Invent. Math. {\bf 118}(1994), 371-394.
 
[B2] Francesco Brenti, {\it Combinatorial expansions of Kazhdan-Lusztig
polynomials}, IAS preprint, Nov. 1994.
 
[GGP] I. Gelfand, M.Graev, and A. Postnikov, xxx, preprint.
 
[S] Richard Stanley, {\it private communication}.
 
 
\end
 
 
 
