Séminaire du 8 juin 2009,
14h00: The complete generating function for Gessel walks is algebraic, Alin Bostan, Équipe-projet Algorithms.
The aim of the talk is to show how a difficult combinatorial problem has been recently solved using an experimental-mathematics approach combined with (rather involved) computer algebra techniques. More precisely, let g(n,i,j) denote the number of lattice walks in the quarter plane which start at the origin, end at the point (i,j), and consist of n unit steps going either west, south-west, east, or north-east. In the early nineties, Ira Gessel conjectured that the sequence of excursions g(n,0,0) is holonomic. We will present the computer-driven discovery and proof of the following generalization, obtained in August 2008 together with Manuel Kauers: the trivariate generating series of the sequence (g(n,i,j))n,i,j is an algebraic function.