Written: Aug. 10, 2012
(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)
The first proof of the 3^{n} theorem, by Gouyou-Beauchamps and Viennot, that was published in 1988, was a true tour-de-force, alas it was via a rather complicated (and seemingly ad hoc) bijection, and Viennot believed that there must be a simpler proof.
So he invented his famous empilements and his two Bordelaise disciples, Jean Bétréma and Jean-Guy Penaud, used them to find the proof from the book, (that another brilliant Bordelaise disciple, Mireille Bousquet-Mélou, taught me).
Alas this most elegant proof is buried in a long technical paper by Bétréma and Penaud, and it is also buried in one of the almost one thousand pages of the Flajolet-Sedgewick bible. It deserves to be better known! And implemented!
And guess what? By "combinatorial reverse-engineering" of this algebraic-combinatorial proof, one can easily derive a natural bijection between these creatures (that I call xaviers) with n+1 pieces and words of length n in the alphabet {-1,0,1}, that, who knows?, is similar (or even the same!) as the old one, but is much easier to formulate (and program!).
the input file would yield the output file
the
input file
would yield the
output file