AN OLD, BUT CUTE, CATALAN PROOF

VICTOR REINER

A few years ago, my colleague Bill Messing [2] suggested to me a cute proof that I’d never seen, and rather liked, of the Catalan enumeration. After consulting the experts on the domino list-server about the history, several people (David Callan, Ira Gessel, Greg Kuperberg, Gilles Schaeffer) pointed me to the references by Dorrie [1, pp. 23-24] and by Rémy [3], which both give the same proof. Dorrie credits the proof idea to Rodrigues [4] in 1838.

Theorem 0.1. Let c_{n} be the number of nonassociative parenthesizations of a product of n + 1 symbols a_{1}a_{2} ⋯ a_{n+1}. Then

c_{n} = \frac{1}{n + 1}\binom{2n}{n}.

Proof. Consider the set P_{n} of nonassociative parenthesizations of a product of any permutation a_{σ_{1}} ⋯ a_{σ_{n+1}} of the same n + 1 symbols. Clearly the cardinality p_{n} of P_{n} satisfies p_{n} = (n + 1)!c_{n}.

Consider the map from f : P_{n} → P_{n−1} that erases the symbol a_{n+1} along with the smallest parenthesis pair in which it lies. We claim that every fiber f^{−1}(α) of this map has the same cardinality, namely 2 · (2n − 1):

• There are 2n − 1 possible factors of α which can get multiplied first with the extra letter a_{n+1} when it is added in. These factors correspond to the 2n − 1 vertices in the rooted binary tree having leaves labelled a_{1}, …, a_{n} which is associated with the parenthesization α.

• After choosing this factor in 2n − 1 ways, one pins down the element of the fiber f^{−1}(α) by making one more binary choice of whether a_{n+1} is multiplied before or after that factor.

Hence the cardinality p_{n} of |P_{n}| satisfies

(1)  \begin{aligned}p_{n} & = 2(2n − 1)p_{n−1} \\ p_{0} & = 1 \end{aligned}

which shows that

p_{n} = 2n(2n − 1) ⋯ (n + 2)(n + 1) = \frac{2n!}{n!}

and hence

c_{n} = \frac{1}{(n + 1)!}p_{n} = \frac{1}{(n + 1)!} \frac{2n!}{n!} = \frac{1}{n + 1}\binom{2n}{n}

as desired. □

Note that one can reinterpret the crucial recursion (1) as follows. We have shown

(n + 1)!c_{n} = 2(2n − 1) · n!c_{n−1}

Date: November 2005.

or equivalently, after dividing by n!,

(2)  (n + 1)c_{n} = 2(2n − 1) · c_{n−1}.

To argue this somewhat more directly (that is, with less labelling, and more symmetry), Greg Kuperberg suggests the following argument, in which c_{n} is interpreted as the number of triangulations of a convex (n + 2)-gon, and the two sides of (2) are interpreted as counting two different kinds of markings of triangulations.

First choose a base side of both the (n + 1)-gon and the (n + 2)-gon. Mark the (n + 1)-gon by choosing any edge, either a diagonal or any side including the base side, and orienting it. There are 2(2n − 1) ways to do this. Mark the (n + 2)-gon by choosing a side other than the base side. There are n + 1 ways to do this.

There is a bijection between these two sets of marked triangulations: starting with the marked (n + 1)-gon triangulation, open the oriented edge to a triangle that points in the direction that the edge points. The new side that you make is the marked side of the (n + 2)-gon; see the figure below for an example with n = 4. This proves (2).

References

[1] H. Dörrie, 100 great problems of elementary mathematics. Their history and solution. Dover Publications, Inc., New York, 1982.

[2] W. Messing, personal communication, early 2000’s.

[3] J.-L. Rémy, Un procédure itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire. RAIRO Inform. Theor. 19 ,1985, 179–195.

[4] Rodrigues, Journal de Mathématiques 3 (1838).

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

   E-mail address: reiner@math.umn.edu