Combinatorics: The Art of Counting

This text serves as a nice introduction to the study of combinatorics. The focus is on enumerative combinatorics. Compared to other books, for example, van Lint’s A Course in Combinatorics, this book has a narrower scope and excludes important subjects like extremal theory, finite geometries, or design theory. However, the choice of the material is coherent and covers many fundamental topics like generating functions and symmetric functions. The pace is moderate, there is a good balance between text and formulas, and lots of examples and illustrations punctuate each section. So the book is very pleasant to read, it includes a rich (but not overwhelming) bibliography and contains plenty of exercises. I tried some of the exercises, and generally, I found them doable and useful (which is reassuring because no solutions are provided). Only a minimal background is necessary to understand the theory exposed in this book; the basic definitions from graph theory or group actions, for example, are introduced as needed. Basic knowledge of algebra and linear algebra is required. The book grew out of the lecture notes which the author compiled over years of teaching the graduate combinatorics course at Michigan State University, and is certainly suitable for a graduate or advanced undergraduate course.

 

The first chapter introduces the basic concepts, and the objects that will be re-visited in the subsequent chapters: permutations, partitions, compositions, graphs, and trees. Chapter 2 then explains how the introduction of a sign function on a set can be used to prove combinatorial identities, for example by looking at fixed points of sign-reversing involutions, or by using determinants. Chapters 3 and 4 cover ordinary and exponential generating functions. The necessary background on the algebra of formal power series is presented, before diving into the applications to linear recursions.

 

Chapter 5, nicely written, is one of the longer and richer chapters in the book. Partially ordered sets are introduced, as a natural structure common to many familiar combinatorial objects, like permutations, partitions, and compositions. Then the Möbius function of a partially ordered set is defined; the familiar number-theoretic version of it is shown to be a special case of the more general definition (Proposition 5.4.5). The Möbius inversion formula is proven in full generality; again, the number-theoretic version, and the fundamental theorem of difference calculus, are derived as applications. The chapter closes with showing the connection between the Zeta function of a partially ordered set and the Riemann Zeta function. Along the way, the author gives a proof of Birkhoff’s theorem: every finite distributive lattice is, up to isomorphisms, the lattice of ideals of a partially ordered set. 

 

Often one wants to count objects up to some symmetry; this leads naturally to counting with group actions, the subject of chapter 6. Note that a 5-page appendix on the representation theory of finite groups is included at the end of the book.  The last two chapters are dedicated, respectively, to symmetric and quasi-symmetric functions. These chapters, like others in the book, include results from the recent literature, in addition to more foundational material. I think some of the material, although interesting, may be skipped at first reading, or may be taken as optional reading in an introductory course. 

 

Overall, I found this book very well written; and the choice of topics makes it complementary to other well-known textbooks on combinatorics.

---

 

Fabio Mainardi (fabio.mainardi@rd.nestle.com) works as senior data scientist at Nestlé Research, Lausanne. After a PhD in number theory, he has been working as applied mathematician in R&D divisions of different companies. His mathematical interests include statistical models, probability, discrete mathematics and optimization theory.