Posted: March 24, 2015
Dear Doron
I just read with interest your article with Amitai Regev and Nathaniel Shar giving abijective proof of the Touchard Catalan identity. This bijection between bicolored Motzkin words of length n and Catalan's words of length 2n+2 is part of the Bordeaux folklore. It is mentioned for instance in the article by Delest-Viennot at the end of page 179 in five lines (see attachment). Viennot taught it to me during my master studies.
Best regards,
Dominique Gouyou-Beauchamps
I enjoyed reading about your elegant bijective proof of Touchard's identity. It strikes me as very similar to a proof due to Rodica Simion and Daniel Ullman, who prove the identity in terms of noncrossing partitions. (See Corollary 3.1 of the attached paper.) Essentially, they encode a noncrossing partition as a word in the set \{ b, e, l, r \}, for which the letters b and e form a matching (b="beginning" and e="end", I suppose) and the l and the r letters can be inserted freely in any remaining slots.
Relating this to your note, b = 1, e = -1, l = \bar 0, and r = 0.
More recently, in
Saul Blanco and I translate Simion and Ullman's argument for noncrossing partitions into a statement about Dyck paths. In particular, we get our Theorem 1.2 by thinking carefully about how Dyck paths of fixed length come from Motzkin paths as you describe in your Remark 2. While we mention Touchard's identity in the introduction we do not demonstrate how the proof follows from the correspondence with Motzkin paths.
In Remark 3, you mention some pictures you don't want to draw. That's fine! Saul and I already drew them in Section 2.4 of our paper.
With kind regards,
T. Kyle Petersen, DePaul University
Hi Doron,
I saw your beautiful quick proof of the Touchard identity for Catalan numbers.
In Tom Sundquist's thesis (p. 65-67) he had a bijection doing a q-version which had both q-Catalan and the q=1 Catalan:
C_{n+1}(q)= \sum_{k=0}^{n/2} C_k* \sum_{S subset of [n] of size 2k} q^(sum of elements in S} *\product_{t not in S} (1+q^(2t))
For example if n=3,
C_4(q)=[6 choose 3]/[4]_q= 1+q^2+q^3+2q^4+q^5+2q^6+q^7+2q^8+q^9+q^10+q^12=
(1+q^2)(1+q^4)(1+q^6)+(q^3*(1+q^6)+q^4*(1+q^4)+q^5*(1+q^2))