Generatingfunctionology

Title page......Page 1
Date-line......Page 2
Contents......Page 3
Preface......Page 6
1 Introductory Ideas and Examples......Page 8
1.1 An Easy Two Term Recurrence......Page 11
1.2 A Slightly Harder Two Term Recurrence......Page 12
1.3 A Three Term Recurrence......Page 16
1.4 A Three Term Boundary Value Problem......Page 18
1.5 Two Independent Variables......Page 22
1.6 Another 2-Variable Case......Page 25
1.7 Exercises......Page 33
2.1 Formal Power Series......Page 38
2.2 The Calculus of Formal Ordinary Power Series Generating Functions......Page 42
2.3 The Calculus of Formal Exponential Generating Functions......Page 48
2.4 Power Series, Analytic Theory......Page 55
2.5 Some Useful Power Series......Page 62
2.6 Dirichlet Series, Formal theory......Page 66
2.7 Exercises......Page 75
3.1 Introduction......Page 84
3.2 Definitions and a Question......Page 86
3.3 Examples of Exponential Families......Page 87
3.4 The Main Counting Theorems......Page 90
3.5 Permutations and Their Cycles......Page 94
3.6 Set Partitions......Page 95
3.7 A Subclass of Permutations......Page 96
3.8 Involutions, etc......Page 97
3.9 2-Regular Graphs......Page 98
3.10 Counting Connected Graphs......Page 99
3.11 Counting Labeled Bipartite Graphs......Page 100
3.12 Counting Labeled Trees......Page 102
3.13 Exponential Families and Polynomials of \'Binomial Type.\'......Page 104
3.14 Unlabeled Cards and Hands......Page 105
3.15 The Money Changing Problem......Page 109
3.16 Partitions of Integers......Page 114
3.17 Rooted Trees and Forests......Page 116
3.19 Exercises......Page 117
4.1 Generating Functions Find Averages, etc......Page 122
4.2 A Generatingfunctionological View of the Sieve Method......Page 124
4.3 The \'Snake Oil\' Method for Easier Combinatorial Identities......Page 133
4.4 WZ Pairs Prove Harder Identities......Page 145
4.5 Generating Functions and Unimodality, Convexity, etc......Page 152
4.6 Generating Functions Prove Congruences......Page 155
4.7 The Cycle Index of the Symmetric Group......Page 157
4.8 How Many Permutations Have Square Roots?......Page 162
4.9 Counting Polyominoes......Page 166
4.10 Exact Covering Sequences......Page 170
4.11 Waiting for a String......Page 173
4.12 Blocks of 1......Page 174
4.13 Exercises......Page 177
5.1 The Lagrange Inversion Formula......Page 188
5.2 Analyticity and Asymptotics (I): Poles......Page 192
5.3 Analyticity and Asymptotics (II): Algebraic Singularities......Page 199
5.4 Analyticity and Asymptotics (III): Hayman\'s Method......Page 203
5.5 Exercises......Page 210
A Using Maple and Mathematica......Page 214
A.1 Series Manipulation......Page 215
A.2 The RSolve.m Routine......Page 216
A.3 Asymptotics in Maple......Page 218
Solutions......Page 220
References......Page 246
Index......Page 250