Lectures on generating functions

Title page......Page 1
Preface to the English Edition......Page 9
Preface......Page 11
§1.1. The lucky tickets problem......Page 15
§1.2. First conclusions......Page 20
§1.3. Generating functions and operations with them......Page 21
§1.4. Elementary generating functions......Page 24
§1.5. Differentiating and integrating generating functions......Page 26
§1.6. The algebra and the topology of formal power series......Page 27
§1.7. Problems......Page 28
§2.1. Geometric series......Page 31
§2.2. The Fibonacci sequence......Page 32
§2.3. Recurrence relations and rational generating functions......Page 35
§2.4. The Hadamard product of generating functions......Page 37
§2.5. Catalan numbers......Page 39
§2.6. Problems......Page 44
§3.1. The Dyck Language......Page 49
§3.2. Productions in the Dyck language......Page 50
§3.3. Unambiguous formal grammars......Page 52
§3.4. The Lagrange equation and the Lagrange theorem......Page 56
§4.1. Exponential estimates for asymptotics......Page 61
§4.2. Asymptotics of hypergeometric sequences......Page 64
§4.3. Asymptotics of coefficients of functions related by the Lagrange equation......Page 68
§4.4. Asymptotics of coefficients of generating series and singularities on the boundary of the disc of convergence......Page 70
§4.5. Problems......Page 72
§5.1. The Pascal triangle......Page 73
§5.2. Exponential generating functions......Page 75
§5.3. The Dyck triangle......Page 77
§5.4. The Bernoulli-Euler triangle and enumeration of snakes......Page 78
§5.5. Representing generating functions as continùed fractions......Page 86
§5.6. The Euler numbers in the triangle with multiplicities......Page 92
§5.7. Congruences in integer sequences......Page 93
§5.8. How to solve ordinary differential equations in generating functions......Page 96
§5.9. Problems......Page 97
§6.1. Partitions and decompositions......Page 101
§6.2. The Euler identity......Page 106
§6.3. Set partitions and continued fractions......Page 109
§6.4. Problems......Page 112
§7.1. The inclusion-exclusion principle......Page 115
§7.2. Dirichlet generating functions and operations with them......Page 118
§7.3. Möbius inversion......Page 121
§7.4. Multiplicative sequences......Page 123
§7.5. Problems......Page 124
§8.1. Enumeration of marked trees......Page 127
§8.2. Generating functions for non-marked, marked, ordered, and cyclically ordered objects......Page 133
§8.3. Enumeration of plane and binary trees......Page 134
§8.4. Graph embeddings into sur{aces......Page 136
§8.5. On the number of gluings of a polygon......Page 146
§8.6. Proof of the Harer-Zagier theorem......Page 150
98.7. Problems......Page 154
Final and Bibliographical Remarks......Page 157
Bibliography......Page 159
Index......Page 161