UCLA Olga Radko Endowed Math Circle

4/4/2010 -- Group B: Generating functions (Amit Hazi, Oxford University)

In combinatorics, we are not only concerned with the study of combinatorial objects (such as graphs, permutations, partitions, and the like); we are also interested in how we can apply methods from other areas of mathematics to help us understand these objects. In this lecture, I will present one of the most common ways of applying algebra (and some calculus) to combinatorics: the generating function. A generating function is a way of encoding a sequence into a polynomial. With generating functions, we can use the algebraic operations of polynomials to greatly simplify calculations and (in some cases) prove marvelous identities.