MIT Combinatorics Seminar Bijective Counting of Kreweras Walks and Loopless Triangulations Olivier Bernardi (LaBRI University of Bordeaux) Email: bernardi@labri.fr Wednesday, March 1, 2006   4:30 pm    Room 2-105 ABSTRACT 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 quadrant is 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.