The Amazing 3n Theorem and its even more Amazing Proof [Discovered by Xavier G. Viennot and his École Bordelaise gang]

By
Doron Zeilberger

.pdf   .ps   .tex

Written: Aug. 10, 2012

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)

Pour mon Cher Ami, Guru Xavier G. VIENNOT
We will (probably) never know the exact number of lattice animals with 1001 points, but thanks to Xavier Viennot and Dominique Gouyou-Beauchamps we know, exactly, the number of directed animals with compact source with that many points, namely 31000, since according to their amazing formula the answer for n+1 points is 3n. This is indeed amazing, since at first sight, the second problem does not seem any easier than the first.

The first proof of the 3n 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!).

Added Sept. 30, 2012: Watch the talk! Part 1, Part 2
[produced by Brian Nakamura and Edinah Gnang]

# Sample Input and Output for the Maple package BORDELAISE

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger