CATALAN STRIKES AGAIN (AND AGAIN)^{∗}

Doron ZEILBERGER^{1}

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}( ∑_{i=0}^{degree} a_{i}q^{i}) = ∑_{i≥r}^{degree} a_{i}q^{i} .

Define B_{1}(q) := −1, and for n > 1:

B_{n}(q) = (q − 1)B_{n−1}(q) + V_{(n+1)/2} ( q^{n−1}(1 − q)B_{n−1}(1/q) ) .

In his talk, Brenti made the following conjecture.

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.

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu . Sup-

ported 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 ftp.math.temple.edu, in directory 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: ftp.temple.edu, in directory /pub/math/Zeilberger. This paper is not going to be ‘published’ elsewhere.

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.^{2} To prove Brenti’s conjecture, I will exhibit explicit expressions for the B_{n}(q). Proposition:

B_{2n}(q) = (−1)^{n} \frac{1}{2n + 1}\binom{2n + 1}{n}q^{n} + ∑_{i=0}^{n−1}(−1)^{i} \frac{2n − 2i + 1}{2n + 1}\binom{2n + 1}{i}(q^{i} + q^{2n−i}) ,

B_{2n+1}(q) = ∑_{i=0}^{n}(−1)^{i+1} \frac{n − i + 1}{n + 1}\binom{2n + 2}{i}q^{i} .

Proof: . Corollary: B_{2n}(1) = B_{2n+1}(1) = (−1)^{n}C_{n}. Proof: .^{3} 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.

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^{4} for short. Let’s first define them. Definition: A Stanley tree on n vertices labelled {1, 2, …, n} is a tree satisfying the following two conditions (I) If 1 ≤ i < j < k ≤ n then {i, j} and {j, k} can’t both be edges. (II) If 1 ≤ i < j < k < l ≤ 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’.

2 Had I used the computer (with Maple), it would probably have taken me half an hour rather than three hours.

3 When q = 1 the sums are Gosper-summable, so this was routine since 1977, and could be done with Macsyma’s

nusum, or Maple’s sum.

4 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.

Most of us know at least one proof^{5} 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)).

Bijection π:

Input: A Stanley tree T, with n vertices labelled {1, 2, …, n}, given by its set of (n − 1) edges.

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}}, …, {i_{k}, j_{k}}} as follows. Let j_{0} := 0, and let i_{1} := 1. For r from 1 (incremented by 1) do:

j_{r} := max { j | {i_{r}, j} ∈ T } .

If j_{r} = n then exit, else

i_{r+1} := min{ i | i > i_{r} such that there exists j > j_{r} such that {i, j} ∈ T } , end do.

Now let’s describe the mapping π. Start with the n-lettered ‘word’ 123 … n and replace all i_{r} (r = 1, …, k) by BB, and all j_{r}’s (r = 1, …, 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 σ, and to formally prove that πσ and σπ are both the identity mapping, hence verifying my claim that π is indeed a bijection.

5 I know at least ten (distinct) proofs. My favorite goes as follows: Use the Schützenberger methodology to deduce

the equation ϕ(z) = 1 + zϕ(z)^{2} for their generating function, then use the Maple package gfun (written by B.

Salvy and P. Zimmermann and inspired by F. Bergeron and S. Plouffe) with the command algtodiff followed by the command difftorec

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 ≤ n ≤ 10. In other words, not only identities, but even bijections (satisfying certain conditions), are going to be shaloshable.

As a lagniappe, we also get the shaloshable, but charming identity:

C_{n−1} = ∑_{1≤k≤n/2} 2^{n−2k}\binom{n − 2}{2k − 2}C_{k−1} .

Note 1: An even nicer bijection was found independently by Michael Schlosser, a student of Christian Krattenthaler.

Note 2: A Maple implementation of the bijections π and σ can be obtained as described in footnote 1, in file 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;’.

References

[B1] Francesco Brenti, A combinatorial formula for the Kazhdan-Lusztig polynomials, Invent. Math. 118(1994), 371-394.

[B2] Francesco Brenti, Combinatorial expansions of Kazhdan-Lusztig polynomials, IAS preprint, Nov. 1994.

[GGP] I. Gelfand, M.Graev, and A. Postnikov, xxx, preprint.

[S] Richard Stanley, private communication.