MIT Combinatorics Seminar
Bijective Counting of Kreweras Walks and
Olivier Bernardi (LaBRI University of Bordeaux)
Wednesday, March 1, 2006 4:30 pm Room 2-105
In 1965, Germain Kreweras published an enumerative result for planar lattice
walks made of South, West and North-East steps. He proved that the number of
walks of length 3n starting and ending at the origin and staying in the first
kn = 4^n /((n+1)(2n+1)) Binomial(3n,n).
Kreweras' formula has a striking similarity with another result published the
same year by Ronald Mullin: the number of loopless planar triangulations with
3n edges is
tn = 2^n /((n+1)(2n+1)) Binomial(3n,n).
The original proof of Kreweras received major simplifications by Niederhausen,
Gessel and Bousquet-Melou. Yet, the enumerative formula remained without
combinatorial explanation. As for Mullin's result, a bijective proof was
obtained only recently by Poulalhon and Schaeffer.
In my talk, I will present a bijective proof of both results. The bijection
concerning triangulations is different from the one by Poulalhon and Schaeffer.
These bijections gives convincing combinatorial explanations of the enumerative
formulas and allow the random sampling of triangulations in linear time.