This book, based on the course given by the author at the College of Mathematics of the Independent University of Moscow, introduces the reader to the language of generating functions, which is nowadays the main language of enumerative combinatorics. It starts with definitions, simple properties, and numerous examples of generating functions. It then discusses topics, such as formal grammars, generating functions in several variables, partitions and decompositions, and theexclusion-inclusion principle. In the final chapter, the author describes applications of generating functions to enumeration of trees, plane graphs, and graphs embedded in two-dimensional surfaces. Throughout the book, the reader is motivated by interesting examples rather than by general theories. It alsocontains a lot of exercises to help the reader master the material. Little beyond the standard calculus course is necessary to understand the book. It can serve as a text for a one-semester undergraduate course in combinatorics.

Preface to the English Edition

xi

Preface

xiii

Chapter 1. Formal Power Series and Generating Functions. Operations with Formal Power Series. Elementary Generating Functions

1

(16)

§1.1. The lucky tickets problem

1

(5)

§1.2. First conclusions

6

(1)

§1.3. Generating functions and operations with them

7

(3)

§1.4. Elementary generating functions

10

(2)

§1.5. Differentiating and integrating generating functions

12

(1)

§1.6. The algebra and the topology of formal power series

13

(1)

§1.7. Problems

14

(3)

Chapter 2. Generating Functions for Well-known Sequences

17

(18)

§2.1. Geometric series

17

(1)

§2.2. The Fibonacci sequence

18

(3)

§2.3. Recurrence relations and rational generating functions

21

(2)

§2.4. The Hadamard product of generating functions

23

(2)

§2.5. Catalan numbers

25

(5)

§2.6. Problems

30

(5)

Chapter 3. Unambiguous Formal Grammars. The Lagrange Theorem

35

(12)

§3.1. The Dyck Language

35

(1)

§3.2. Productions in the Dyck language

36

(2)

§3.3. Unambiguous formal grammars

38

(4)

§3.4. The Lagrange equation and the Lagrange theorem

42

(1)

§3.5. Problems

43

(4)

Chapter 4. Analytic Properties of Functions Represented as Power Series and the Asymptotics of their Coefficients

47

(12)

§4.1. Exponential estimates for aymptotics

47

(3)

§4.2. Asymptotics of hypergeometric sequences

50

(4)

§4.3. Asymptotics of coefficients of functions related by the Lagrange equation

54

(2)

§4.4. Asymptotics of coefficients of generating series and singularities on the boundary of the disc of convergence

56

(2)

§4.5. Problems

58

(1)

Chapter 5. Generating Functions of Several Variables

59

(28)

§5.1. The Pascal triangle

59

(2)

§5.2. Exponential generating functions

61

(2)

§5.3. The Dyck triangle

63

(1)

§5.4. The Bernoulli-Euler triangle and enumeration of snakes

64

(8)

§5.5. Representing generating functions as continued fractions

72

(6)

§5.6. The Euler numbers in the triangle with multiplicities

78

(1)

§5.7. Congruences in integer sequences

79

(3)

§5.8. How to solve ordinary differential equations in generating functions

82

(1)

§5.9. Problems

83

(4)

Chapter 6. Partitions and Decompositions

87

(14)

§6.1. Partitions and decompositions

87

(5)

§6.2. The Euler identity

92

(3)

§6.3. Set partitions and continued fractions

95

(3)

§6.4. Problems

98

(3)

Chapter 7. Dirichlet Generating Functions and the Inclusion-Exclusion Principle

101

(12)

§7.1. The inclusion-exclusion principle

101

(3)

§7.2. Dirichlet generating functions and operations with them

104

(3)

§7.3. Mobius inversion

107

(2)

§7.4. Multiplicative sequences

109

(1)

§7.5. Problems

110

(3)

Chapter 8. Enumeration of Embedded Graphs

113

(30)

§8.1. Enumeration of marked trees

113

(6)

§8.2. Generating functions for non-marked, marked, ordered, and cyclically ordered objects

119

(1)

§8.3. Enumeration of plane and binary trees

120

(2)

§8.4. Graph embeddings into surfaces

122

(10)

§8.5. On the number of gluings of a polygon

132

(4)

§8.6. Proof of the Harer-Zagier theorem

136

(4)

§8.7. Problems

140

(3)

Final and Bibliographical Remarks

143

(2)

Bibliography

145

(2)

Index

147

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.