Generating Functionology (eBook)

Front Cover 1
Generatingfunctionology 4
Copyright Page 5
Table of Contents 6
Preface 8
Preface to the Second Edition 10
Chapter 1: Introductory Ideas and Examples 12
1.1 An easy two term recurrence 14
1.2 A slightly harder two term recurrence 16
1.3 A three term recurrence 19
1.4 A three term boundary value problem 21
1.5 Two independent variables 22
1.6 Another 2-variable case 27
Exercises 35
Chapter 2: Series 41
2.1 Formal power series 41
2.2 The calculus of formal ordinary power series generating functions 44
2.3 The calculus of formal exponential generating functions 50
2.4 Power series, analytic theory 57
2.5 Some useful power series 63
2.6 Dirichlet series, formal theory 67
Exercises 76
Chapter 3: Cards, Decks, and Hands: The Exponential Formula 84
3.1 Introduction 84
3.2 Definitions and a question 85
3.3 Examples of exponential families 87
3.4 The main counting theorems 89
3.5 Permutations and their cycles 92
3.6 Set partitions 94
3.7 A subclass of permutations 95
3.8 Involutions, etc 95
3.9 2-regular graphs 96
3.10 Counting connected graphs 97
3.11 Counting labeled bipartite graphs 98
3.12 Counting labeled trees 100
3.13 Exponential families and polynomials of 'binomial type.' 102
3.14 Unlabeled cards and hands 103
3.15 The money changing problem 107
3.16 Partitions of integers 111
3.17 Rooted trees and forests 113
3.18 Historical notes 114
Exercise 115
Chapter 4: Applications of generating functions 119
4.1 Generating functions find averages, etc 119
4.2 A generatingfunctionological view of the sieve method 121
4.3 The 'Snake Oil' method for easier combinatorial identities 129
4.4 WZ pairs prove harder identities 141
4.5 Generating functions and unimodality, convexity, etc 147
4.6 Generating functions prove congruences 151
4.7 The cycle index of the symmetric group 152
4.8 How many permutations have square roots 157
4.9 Counting polyominoes 161
4.10 Exact covering sequences 165
Exercises 168
Chapter 5: Analytic and asymptotic methods 178
5.1 The Lagrange Inversion Formula 178
5.2 Analyticity and asymptotics (I): Poles 182
5.3 Analyticity and asymptotics (II): Algebraic singularities 188
5.4 Analyticity and asymptotics (III): Hayman's method 192
Exercises 199
Appendix: Using Mapl™ and Mathematical™ 203
Solutions 208
References 235
Index 238