Chapter 3: Generating Functions introduces a central concept in the average-case analysis of algorithms: generating functions - a necessary and natural link between the algorithms that are our objects of study and analytic methods that are necessary to discover their properties.