The Amazing 3<sup>n</sup> Theorem and its even more Amazing Proof [Discovered by Xavier G. Viennot and his Ecole Bordelaise gang]

The Amazing 3ⁿ 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 3¹⁰⁰⁰, since according to their amazing formula the answer for n+1 points is 3ⁿ. This is indeed amazing, since at first sight, the second problem does not seem any easier than the first.
The first proof of the 3ⁿ 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]

Maple Package

BORDELAISE

Sample Input and Output for the Maple package BORDELAISE

Pictures:

Here are the pictures of all the half-pyramids with two pieces, three pieces, four pieces, five pieces, six pieces, seven pieces, and eight pieces

Here are the pictures of all the pyramids with two pieces, three pieces, four pieces, five pieces, and six pieces

Here are the pictures of all the xaviers with two pieces, three pieces, four pieces, five pieces, and six pieces

Here are pictures of randomly-picked half-pyramids with 35 pieces (one hundred of them!), 100 pieces (one hundred of them!), and 1000 pieces (ten of them!),

Here are pictures of randomly-picked pyramids with 35 pieces, (one hundred of them!), 100 pieces, (one hundred of them!), and 1000 pieces (ten of them!),

Here are pictures of randomly-picked xaviers with 35 pieces, (one hundred of them!), 100 pieces, (one hundred of them!), and 1000 pieces (ten of them!),

If you want to see the examples of the three Betrema-Penaud mappings
the input file would yield the output file

Here is an example of the FIRST Betrema-Penaud mapping, with all the intermedia steps

Here is an example of the SECOND Betrema-Penaud mapping, with all the intermedia steps

Here is an example of the THIRD Betrema-Penaud mapping, with all the intermedia steps

If you want to see the image of the Xavier mapping applied to the word in {-1,0,1} corresponding to the integer part of 3¹⁰⁰⁰/101 with n=1000, getting a xavier with 999 pieces,
the input file would yield the output file

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page