Lectures on generating functions. Transl. from the Russian by the author. (English) Zbl 1032.05001
Student Mathematical Library. 23. Providence, RI: American Mathematical Society (AMS). xv, 148 p. (2003).
The title of this little book is partly misleading. So, we quote from the preface: “The goal of the present book is to serve as a basis for a one-semester undergraduate course in combinatorics, based on the notion of generating function.” However, although most of the material is based on problems from combinatorics, such as counting triangulations of an \(n\)-gon or studying partition problems, a large part of the book is indeed about properties of generating functions and formal power series. In the reviewer’s opinion much of the material is beyond the comprehension of present-day undergraduates.
The style of presentation is clear but for some of the problems it is hard to see a connection to what has just been discussed. The book originally appeared in Russian and was translated by the author himself. This was done quite reasonably. There are some mistakes that could have easily been prevented, e.g. “disorder” for a derangement, “degree” for power, “erasing the brackets” for expanding a product. A mistake that I have seen before is “Ferrer’s diagram” (the man’s name is Ferrers). None of these seriously affect the readability of the book.
The first chapter introduces the idea of using power series to count combinatorial objects. Unfortunately, the chosen example cannot be solved using power series.
Chapter 2 is mainly about the Fibonacci sequence and Catalan numbers.
Chapter 3 treats formal grammars.
Chapter 4 is completely on power series, analytic properties and asymptotics.
In Chapter 5 generating functions of several variables are introduced using a number of triangular arrays such as the Pascal triangle as motivation. Here the idea of using continued fractions is also introduced.
Chapters 6 and 7 are much more combinatorial: partitions and the principle of inclusion-exclusion. Here it turns out that the problem from Chapter 1 is quite easily solved without the use of generating functions!
The final chapter is much more difficult. It treats enumeration of labeled trees and problems on embedding graphs into surfaces of higher genus. In the reviewer’s opinion it does not fit well with the earlier material.
Even experts in this area probably find a number of surprising and interesting facts in this book. Undergraduates have a rough time with it, especially with some of the problems.
The style of presentation is clear but for some of the problems it is hard to see a connection to what has just been discussed. The book originally appeared in Russian and was translated by the author himself. This was done quite reasonably. There are some mistakes that could have easily been prevented, e.g. “disorder” for a derangement, “degree” for power, “erasing the brackets” for expanding a product. A mistake that I have seen before is “Ferrer’s diagram” (the man’s name is Ferrers). None of these seriously affect the readability of the book.
The first chapter introduces the idea of using power series to count combinatorial objects. Unfortunately, the chosen example cannot be solved using power series.
Chapter 2 is mainly about the Fibonacci sequence and Catalan numbers.
Chapter 3 treats formal grammars.
Chapter 4 is completely on power series, analytic properties and asymptotics.
In Chapter 5 generating functions of several variables are introduced using a number of triangular arrays such as the Pascal triangle as motivation. Here the idea of using continued fractions is also introduced.
Chapters 6 and 7 are much more combinatorial: partitions and the principle of inclusion-exclusion. Here it turns out that the problem from Chapter 1 is quite easily solved without the use of generating functions!
The final chapter is much more difficult. It treats enumeration of labeled trees and problems on embedding graphs into surfaces of higher genus. In the reviewer’s opinion it does not fit well with the earlier material.
Even experts in this area probably find a number of surprising and interesting facts in this book. Undergraduates have a rough time with it, especially with some of the problems.
Reviewer: J.H.van Lint (Eindhoven)
MSC:
| 05-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics |
| 05A15 | Exact enumeration problems, generating functions |
| 05C30 | Enumeration in graph theory |
