A Very Short (Bijective!) Proof of Touchard’s Catalan Identity

By Amitai REGEV, Nathaniel SHAR, and Doron ZEILBERGER

Added March 24, 2015: It turns out that our bijection was too nice not to have been known before. See the insightful comments by Dominique Gouyo-Beauchamp, Kyle Petersen, and Dennis Stanton in

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/touchardComm.html

Recall that one of the almost infinitely many definitions of the ubiquitous Catalan Numbers, C_{n}, is as the number of elements of the set of 2n-letter words, w_{1} … w_{2n} in the alphabet {−1, 1} that add up to zero, and all whose partial sums are non-negative. Let’s call this set C_{n}.

In the 1924 Toronto ICM, Jacques Touchard [T] announced (and proved) the elegant identity

C_{n+1} = ∑_{k≥0} \binom{n}{2k}2^{n−2k}C_{k} .  (T ouchard)

Here is a very short, purely bijective, proof, even nicer than Lou Shapiro’s [S].

Let f(1, 1) := 1, f(1, −1) := 0, f(−1, 1) := ¯0, f(−1, −1) := −1, where ¯0 is a twin-sister of 0, whose value in summation is also 0. Define on w = w_{1} … w_{2n+2} ∈ C_{n+1},

T (w_{1} … w_{2n+2}) := f(w_{1}, w_{2})f(w_{3}, w_{4}) … f(w_{2n+1}, w_{2n+2}) .

This is a bijection onto the set, let’s call it G′_{n}, of n + 1-letter words in the alphabet {−1, 0, ¯0, 1}, that sum-up to zero, have all non-negative partial sums, and in addition, the partial sum before any occurence of the letter ¯0 is strictly positive.

But this latter set is in bijection with the set, let’s call it G_{n}, of such n-letter words without the last restriction, as follows. For w = w_{1} … w_{n+1} ∈ G′_{n}, if w_{n+1} = 0 just chop that last letter, mapping it to w_{1} … w_{n}. Otherwise, of course w_{n+1} = −1 (it can’t be 1, and it can’t be ¯0), so write w as (¯1 := −1) w′ 1 w′′ ¯1 (where w′ ∈ G′_{k} and w′′ ∈ G_{n−1−k} for some 0 ≤ k ≤ n − 1), and map it to w′¯0w′′.

Note that the number of elements of G_{n} is given by the right side of Eq. (T ouchard). Indeed, let the number of ones be k (0 ≤ k ≤ n/2), then there are also k minus-ones. There are \binom{n}{2k} ways to choose the locations of the 1’ and −1’s, C_{k} ways of forming them into a member of C_{k}, and 2^{n−2k} ways of deciding which kind of zero ( 0 or ¯0) will occupy the remaining n − 2k slots.

Remarks

1. While it is nice to give pretty bijective proofs, let us note that today, thanks to WZ proof theory, the epistemological stature of identities like Touchard’s is the same as that of the identity 2 + 2 = 1 + 3. Indeed just copy-and-paste the line below onto a Maple session:

SumTools[Hypergeometric][Zeilberger](binomial(n,2*k)*2**(n-2*k)*binomial(2*k,k)/(k+1),n,k,N);

2. Another way of counting G_{n} is to partition it according to the number of occurrences of ¯0, say n − k, then choose the \binom{n}{n−k} locations of the ¯0 and ‘fill-in’ the remaining k slots by a so-called Motzkin word of length k, i.e. a word in the alphabet {−1, 0, 1}, whose sum is 0, and whose partial sums are non-negative, yielding the equally elegant identity (where M_{k} is the number of Motzkin words of length k)

C_{n+1} = ∑_{k=0}^{n} \binom{n}{k}M_{k} .  (Motzkin)

While this identity is ‘trivially equivalent’ to quite a few known identities, and is ‘well-known to the experts’, we were unable to find it in the literature.

3. We intentionally avoided drawing diagrams, but most human readers will probably get a better appreciation of the beauty of our proof by drawing a random Dyck path in C_{n+1}, and then, scanning it in consecutive pairs, replace 11 (alias up-up) by an Up Step, replacing ¯1¯1 (alias down-down) by a Down Step, replace 1¯1 by a green horizontal step, and replace ¯11 by a red horizontal step. Then G′_{n} are generalized Motzkin paths of length n + 1, with two types of horizontal steps, green and red, where a red horizontal step may not lie on the x-axis, and G_{n} is the set of such n-step paths without this restriction. The bijection between G′_{n} and G_{n} consists of removing the last step, if it is a green horizontal step (of course it can’t be a red horizontal step), and otherwise looking at the ‘Up-mate’ of the last step (that is [of course] a Down step), and replacing that Up-Mate by a red horizontal step, and at the same time deleting the above-mentioned last Down step.

4. We thank Lou Shapiro for telling us that we rediscovered Touchard’s identity (in its almostequivalent form given in Eq. (Motzkin)), and telling us about [S]. While we admire Shapiro’s combinatorial proof, it it is not purely bijective, and makes use of generating functions.

5 Our bijection is a renormalization-group transformation, where we ‘renormalized’ a word of length 2n + 2 into a word half as long, but with more letters in the underlying alphabet. It may be interesting to see if one can get less trivial identities by considering generalized Dyck words where the fundamental steps are drawn from a larger set of steps than just {(1, −1), (1, 1)}.

References

[S] L. W. Shapiro, A short proof of an identity of Touchard’s concerning Catalan Numbers, J. Combinatorial Theory (A) 20 (1976), 375-376.

[T] J. Touchard, Sur certain équations fonctionelles, in: Proc. Int. Math. Congress, Toronoto (1924), Vol. 1 (1928), 465-472.

http://www.mathunion.org/ICM/ICM1924.1/Main/icm1924.1.0465.0472.ocr.pdf .

Amitai Regev, Department of Mathematics, Weizmann Institute of Science, amitai.regev at weiz-

mann dot ac dot il ; http://www.wisdom.weizmann.ac.il/~regev/ .

Nathaniel Shar and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), [nshar, zeilberg] at math dot rutgers dot edu ,

http://www.math.rutgers.edu/~zeilberg/ , http://www.math.rutgers.edu/~nshar/ .

π day, 2015; This version: March 24, 2015.