A Very Short (Bijective!) Proof of Touchard's Catalan Identity
Amitai Regev, Nathaniel Shar, and Doron Zeilberger
Posted: π Day, 2015
This version: March 24, 2015.
It is still fun to find bijective proofs of identities, even if they are shaloshable!
Added March 24, 2015: It turns out that our nice bijection was too nice not to have been
known before. See the insightful comments
by Dominique Gouyo-Beauchamp, Kyle Petersen, and Dennis Stanton.
Added Nov. 24, 2021: Nachum Dershowitz pointed out the follwing beautiful
that is relevant to our note.
A short Maple package, implementing the bijection (and its inverse), and checking, empirically,
that it is indeed a bijection!
An Input and Output file for the Maple package TOUCHARD
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page