3^n

Xavier Viennot

Affiliation:

LaBRI
University of Bordeaux 1
33405 Talence Cedex
France

Time:

Tuesday, 26 February 2013, 16:00 to 17:00

Venue:

• AG-69

The following is reproduced from Doron Zeilberger's page:
http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/bordelaise.html.

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!).