Author: Pierre Audibert
Publisher: Wiley-Blackwell, 2010
Pages: 944
ISBN:978-1848211964
Aimed at: Practical algorithmic programmers
Rating: 4
Pros: A real world approach, makes combinatorics fun
Cons: If you want a pure math approach you may disapprove
Reviewed by: Mike James

There isn't much scope for new books on the mathematics of computer science - or so you might have thought. In fact there are few coherent accounts to choose from and they all have their particular emphasis that makes them incomplete. So it is with this relatively new work. It has just short or 1000 pages yet its coverage is confined to matters combinatoric and the related probability theory. As long as this is what you are looking for it is a worthwhile addition to your bookshelf.

It is divided into three parts - Combinatorics, Probability and Graphs prefaced by a with a nice historical introduction to the sorts of problems and solutions that led up to the modern maths of algorithms. Then we get started on combinatorics proper. It really does start off from the very beginnings of the subject with a look at Pascal's triangle and the combinations that are related to it. From here the emphasis falls on combinatorics that arise naturally from the considerations of algorithms. Chapter 3 deals with enumerations in alphabetical order, then Chapter 4 deals with enumerations that result from tree structures. Chapter 5 looks at generating functions and recurrences. Chapter 6 is about routes in a square grid and Chapter 7 deals with arrangements and combinations with repetition including anagrams and lots of detailed algorithmic applications. Then we have sieve formulae and two chapters on "mountain ranges" - arrangements of line segments corresponding to up/down - which is the bracket nesting problem in thin disguise. Then we have some example applications, Burnside's formula, matrices and circulations on a graph, parts and partitions of a set, partitions of a number, flags, walls with stacks, tiling and permutations, This brings us to the end of the first part and as you can tell by the number of topics each chapter is quite short.

Part 2 is about probability and it starts off with a revision on discrete probabilities and then a chapter on implementing some basic probability processes on a computer. Chapter 22 introduces the idea of a continuous distribution but the main focus of the book is on discrete distributions so this is no more than an aside. Chapter 23 deals with generating functions, then we have graphs and matrices, repeated games of heads-or-tails, random routes on a graph, repetitive draws until a condition is satisfied, and some exercises. This is not a book on the theory of probability or advanced methods such as Monte Carlo simulation or Markov chains. It's mostly the application of basic ideas and the presentation of results.

The final part of the book is about graph theory. Chapter 29 introduces the basic ideas. Then we have a look at different types of exploration of a graph, then trees with numbered nodes, binary trees, weighted graphs including shortest path and minimum spanning tree - all classic computer science and algorithms. Chapter 34 is about Eulerian paths, then we have the enumeration of spanning trees, enumeration of Eulerian paths and finally Hamiltonian Paths. The book ends with two appendixes on linear algebra and determinants.

This is not a deeply theoretical book. You won't find any discussion of measure theory or NP hard problems. In the main it takes very simple algebraic methods and applies them relentlessly to problems expressed in real world terms. For example, instead of repeated Bernoulii trials the topic is called "repeated games of heads-or-tails". In many ways the book reads more like a title on recreational mathematics than pure math.  As a result there are some with a leaning to pure math who are going to see the book as unnecessary and naive in its approach and certainly if you prefer stochastic differential equations and Markov chain Monte Carlo then the chances that you will approve of this book are low.

On the other hand if you are looking for an approach to  combinatorics that is routed in applications and with lots of exercises then this is the book for you. Yes, dare I say it, it's fun.