Combinatorics and probability

1. Apr 18, 2007

Werg22

What would be a good text on elementary combinatorics and combinatorial probability (I don't know if I'm using the right term here)? I'm looking for a classic and elegant text, nothing too modern or fancy.

2. May 8, 2007

Chris Hillman

Some good books on combinatorics

Anyway, you have many excellent choices. There is widespread agreement on coverage of certain basic topics, but in such a huge subject, each textbook seems to have something uniquely valuable to offer. Some I'd recommend, roughly in order of sophistication:

Alan Tucker, Applied Combinatorics, Second Ed., Wiley, 1984.

J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.

Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, 1996.

As you know, combinatorics overlaps with graph theory. Two wonderful textbooks with similar coverage but distinct approaches:

Bela Bollobas, Modern Graph Theory, Springer, 1998. One of the best math books ever published.

Reinhard Diestel, Graph Theory, Second Ed., Springer, 2000. Compare for example the treatments of the Szemeredi regularity lemma, which is increasingly recognized as one of the most important theorems in mathematics, the foundation for what has been called "ergodic Ramsey theory".

I happen to be a huge fan of "enumerative combinatorics". Here a basic skill is the use of generating functions to count the number of n-vertex trees (say), and to study the asymptotics of such counts:

Herbert S. Wilf, Generatingfunctionology, Academic Press, 1990. Opens with one of the most inspired "mathematical riffs" in the English langage, well worth reading for that alone. Wilf's centerpiece is a theorem which unfortunately he states in a way which obscures it's close connection with Polya enumeration, which is very unfortunate. I have rewritten but not formatted much of the content of this book from the viewpoint of structors, aka "combinatorial species", a beautiful theory due to Andre Joyal which perfectly captures the basic notions of Wilf's book in terms of category theory. I haven't read the WP article, but a glance at the history shows contribs from at least some known "good editors" whom I wouldn't expect to make serious factual errors: http://en.wikipedia.org/wiki/Combinatorial_species

Peter S. Cameron, Permutation Groups, University of Cambridge Press,1999. Provides a partial corrective.

The standard reference on enumerative combinatorics is by a multivolume work by the redoubtable Richard P. Stanley http://en.wikipedia.org/wiki/Richard_P._Stanley Another closely related subject is algorithms for finite data structures. The standard reference on algorithms is of course the multivolume work by Donald E. Knuth http://en.wikipedia.org/wiki/Donald_Knuth

Last edited by a moderator: Apr 22, 2017