Generatingfunctionology (mostly combinatorics)

This edition contains several new areas of application, in chapter 4, many new problems and solutions, a number of improvements in the presentation, and corrections. It also contains an Appendix that describes some of the features of computer algebra programs that are of particular importance in the study of generating functions. I am indebted to many people for helping to make this a better book. Bruce Sagan, in particular, made many helpful suggestions as a result of a test run in his classroom. Many readers took up my oRer (which is now repeated) to supply a current errata sheet and my thanks in return for any errors discovered. Contents 4 Chapter 1: Introduction 6 An easy two term recurrence 8 A .. harder two term recurrence 10 A three term recurrence 13 A three term boundary value problem 15 Two independent variables 19 Another 2-variable case 21 Exercises 29 Chapter 2: Series 35 Formal power series 35 Calculus of formal opsgf's 38 Calculus of formal egf's 44 Power series: analytic theory 51 Some useful power series 57 Dirichlet series: formal 61 Exercises 70 Chapter 3: Cards, decks and hands 78 Introduction 78 Definitions and a question 79 Examples of exponential families 81 Main counting theorems 83 Permutationss and their cycles 86 Set partitions 88 A subclass of permutations 89 2-regular graphs 90 Counting connected graphs 91 Counting labeled bipartite graphs 92 Counting labeled trees 94 Polynomials of binomial type 96 Unlabeled cards and hands 97 The money changing problem 101 Partitions of integers 105 Rooted trees and forests 107 Historical notes 108 Exercises 109 Chapter 4: Applications of gf's 113 Finding averages, etc. 113 A gf view of the sieve method 115 The Snake Oil method 123 WZ pairs 135 Unimodality, convexity, etc. 141 gf's prove congruences 145 The cycle index 146 How many perms have square roots? 151 Counting polyominoes 155 Exact covering sequences 159 Exercises 162 Chapter 5: Analytic and asymptotic methods 172 Lagrange inversion 172 Analyticity and Asymptotics 176 (I) Poles 176 (II) Algebraic singularities 182 (III) Hayman's method 186 Exercises 193 Appendix: Maple and Mathematica 197 Solutions 202 References 229