Many questions in discrete mathematics, probability and computer science start with the words "How many...?" How many binary trees are there? How many "bad" inputs are there for a certain algorithm? What's the probability that in a sequence of 100 coin flips there are more than five heads in a row? Generating functions are one powerful tool in combinatorial enumeration to answer such questions. For a (counting) sequence $a_n$ (e.g. the number of planar graphs on $n$ vertices) the generating function is the (formal) power series $A(z)=\sum a_n z^n.$ Combinatorial decompositions of the objects in question often translate into functional equations for $A(z).$
In some cases generating function techniques provide neat exact formulas for $A(z)$ and/or $a_n.$ On the other hand, analytic methods can provide very precise estimates of the asymptotic behaviour of the sequence $a_n.$
As a first (and very delightful) reading I recommend the book "Generatingfunctionology" by Herbert Wilf which can be downloaded for free at
Sections 4.2, 4.3, 4.4, 4.5 and 4.7 might be good material for a student presentation.
http://www.math.upenn.edu/~wilf/DownldGF.html
Check also the other books available for free download on this web site!
The other book this course is based on is "Analytic Combinatorics" by Philippe Flajolet and Robert Sedgewick which can be downloaded for free at
http://algo.inria.fr/flajolet/Publications/books.html
