Combinatorics is growing in popularity as part of a computer science program. This student text, designed to support a one-semester course in combinatorics at the third- or fourth-year level, recognizes this by taking an algorithmic approach to many of the techniques discussed and using machine examples of clear relevance in computer science. Nevertheless, the work is primarily mathematical, and all of the more than 850 problems presented (as well as many worked examples) can be solved without recourse to a machine. As the text itself points out, however, many could be the basis of practical coding exercises, and several are made so through the inclusion of short sections of supplementary computer projects, some of which quote code.
Some previous exposure to mathematical reasoning is essential, as is some basic knowledge of analysis. Links with both graph theory and games (theoretical and practical) are made explicit.
The text begins with a not-totally-successful discussion of mathematical problem-solving techniques, including some well-known chestnuts such as the impossibility of covering an 8 × 8 square with two opposite 1 × 1 corner pieces removed by using 2 × 1 rectangles, and generating amounts of water with two containers of volumes integral and coprime in the units in question. The set of problems then invites reasoning by attempting close analogies with a small finite set of recently solved problems. (This technique, the usual approach in student problems, is not one of the techniques listed.) A similar introduction to induction is given, leading to a rapid overview of recurrence relations, number systems, and the fundamental theorem of arithmetic (without uniqueness and with primes defined by implication as irreducibles). Sets are now rapidly introduced via Venn diagrams, as are relations, equivalence relations, partitions, and functions. The first chapter is best viewed as a test for the reader. If you do not already have a thorough grasp of the bulk of this material, the course is not for you. The problems may well give you new insight into the concepts covered, however, by introducing new examples. This chapter, like the others, ends with a helpful summary and a useful bibliography. The choice of references is a strength of the work, although it is not clear how many students will follow up even a small fraction of the references.
Chapters 2 and 3 cover counting principles. The formal words are again hard to understand without knowing the material, but the worked examples and problems compensate for this weakness by their extensive, varied coverage. In this way distinguishable outcomes, independence, and the addition and multiplication principles leading to traditional permutation and combination work are explained, and finite probabilities computed with binomial and multinomial coefficients are introduced at the appropriate moment. The inclusion/exclusion principle extends the work to overlapping sets.
Chapter 4 introduces combinational algorithms and their division into direct, enumeration, and interactive/recursive. Sorting algorithms appear as examples before the authors cover big-O notation and the asymptotic analysis of algorithms (complexity). An optional section addresses enumerating permutations and combinations (in a lexicographic sense).
Chapter 5 introduces finite graph theory and its terminology and related problems. Again, the approach is through the standard problems and examples, and concepts are introduced in an appropriate order prior to their use. Eulerian and Hamiltonian graphs and planarity are introduced rapidly, and their relationships to well-known problems are explained without much detail. For example, Kuratowski’s theorem is stated without proof. Coloring and chromatic polynomials complete this thorough but rapid discussion. Graph-based algorithms and search techniques are covered in chapter 6. The emphasis is again on practical problems, leading to spanning trees and Cayley’s theorem (which is proven). A specific discussion of trees and their applications, in sorting and elsewhere, follows. As with the previous chapter and the later chapters, this sets the level of the course more effectively than the early chapters; the level seems appropriate for mathematicians, but may stretch some computer scientists.
The next chapter covers generating functions and computations using them, with corresponding simplification of many combinational problems. Partitions are a good example. Chapter 8 covers recurrence relations as an alternative approach to combinational problems and introduces, among other things, Bell, Catalan, and Stirling numbers. Solutions of recurrence relations are covered in some detail, including exponential terms and difference equations. This leads to Polya’s theory of counting in chapter 9, which requires a reasonable knowledge of elementary finite group theory (although this background is provided skimpily in the text). The final chapter returns to the harder end of graph and network algorithms and is likely to stretch most students, being somewhat thinner on examples and problems than all previous chapters.
The text is laid out well and is of an appropriate length for the material covered. It would be a good text to support a third- or fourth-year combinatorics course, but will need to be sensitively backed up, especially for computer science students. The work is a reprint of a 1989 original, and the opportunity has been taken to correct earlier misprints.
The solutions to odd-numbered problems are given and are relatively easy to follow. The problems and examples themselves would be of considerable value, even if the text itself were little used. This book is a useful addition to the shelf.
