You are here

Enumerative Combinatorics, Vol I

Richard P. Stanley
Publisher: 
Cambridge University Press
Publication Date: 
2011
Number of Pages: 
626
Format: 
Paperback
Edition: 
2
Series: 
Cambridge Studies in Advanced Mathematics 49
Price: 
49.99
ISBN: 
9781107602625
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee considers this book essential for undergraduate mathematics libraries.

[Reviewed by
Darren Glass
, on
02/25/2012
]

Some books seem like they shouldn’t need reviews: The Bible, Moby Dick, Great Expectations, Euclid’s Elements. Their names are so ingrained in our minds as the pinnacle of what a great book should be that it almost doesn’t occur to us that a review is a good idea. Who is going to decide whether to read Shakespeare based on what folks on Amazon think of it? Now, Richard Stanley’s Enumerative Combinatorics, Volume I is probably not quite at the level of the above-named classics, but it is about as close as a graduate-level text in mathematics can be. Don’t believe me? Look at what others said about the first edition:

  • “In a little over 300 pages of careful exposition, the author has packed a tremendous amount of information into this book.” — MathSciNet
  • “This is a masterful work of scholarship which is, at the same time, eminently readable and teachable. It will be the standard work in the field for years to come.” — Citation for 2001 Leroy Steele Prize For Mathematical Exposition, which Stanley won for the two volumes of his book.
  • “Historically then this is a book of major importance. It provides a widely accessible introduction to many topics in combinatorics… Furthermore, it is sure to become a standard as an introductory graduate text in combinatorics.” — George Andrews, writing in Bulletin of the AMS
  • “Best of all, Stanley has succeeded in dramatizing the subject, in a book that will engage from start to finish the attention of any mathematician who will open it at page one.” — Gian-Carlo Rota, in the preface to the first edition.

Stanley has recently revised the first volume of Enumerative Combinatorics, citing the words of Thucydides in his introduction: “I have written my work, not as an essay which is to win the applause of the moment, but as a possession for all time.” The new edition updates the coverage of the book to include topics that have become more central in the field in the more than two decades since the original edition was published. He has added several sections and many new applications and examples, and in doing so has made a great book even better.

Now that I have hopefully convinced you of the quality of the book, I should say a few words about what it contains. So what is Enumerative Combinatorics? Conveniently, that is the title of the first chapter and Stanley tries to give the simplest answer possible: “The basic problem of enumerative combinatorics is that of counting the number of elements of a finite set… Immediately, philosophical difficulties arise. What does it mean to ‘count’ the number of elements of Si? There is no definitive answer to this question.” Stanley goes on to discuss the differences between explicit formulas, asymptotic formulas, generating functions, and other ways one might try to count finite sets. He then dives into examples, and very quickly the reader is taken on a tour of sets, multisets, cycles, partitions, Euler numbers, and permutations, all leading up to a detailed description of “The Twelvefold Way” (normally attributed to Rota) describing the various ways of counting functions between two sets.

The second chapter of the book deals with Sieve Methods, which Stanley describes as “a method for determining the cardinality of a set S that begins with a larger set and somehow subtracts off or cancels out unwanted elements.” His first example of such a method is the well-known Principle of Inclusion-Exclusion, which Stanley then uses to count sets such as derangements (permutations with no fixed points) and the number of ways to place nonattacking rooks on a chessboard. This latter topic leads to more generalizations such as Ferrers boards, Young diagrams, V-partitions, and involutions. A final section discusses how determinants of matrices have nice combinatorial interpretations.

Partially Ordered Sets (aka posets) are the topic of the third chapter, and Stanley discusses them in a variety of forms, including lattices, incidence algebras, and hyperplane arrangements. He then defines and studies the notion of (P, ω) partitions, which are partitions of an integer with certain restrictions on the parts given by inequalities. Other topics in this chapter include Eulerian posets, Binomial Posets, and Differential Posets. The fourth and final chapter of Stanley’s book deals with counting problems whose answer can be given in terms of a rational generating function. In particular, Stanley gives a classification for when a generating function will actually be given by a polynomial or a quasipolynomial. He also discusses counting problems arising from counting solutions to linear Diophantine equations and gives applications such as counting the number of magic squares. Finally, he discusses the so-called Transfer-Matrix method which has many applications, including some in statistical mechanics.

Enumerative Combinatorics is a book that many people have picked up in order to learn something about the field, and it is excellent for that purpose. Stanley is an extremely clear writer, and there are more than enough examples and applications to give a real feel for what the theory is saying. Additionally, the book has 537 exercises, a number of which have ten or more parts, so there is no shortage of practice for a reader who wants to make sure they understand the theory well. Many of the exercises have hints or solutions, and they are all given a difficulty rating. Stanley has provided a very detailed bibliography and notes to point the interested reader in the proper direction to learn even more.

This is a graduate level textbook, and as such Stanley assumes a pretty high level of mathematical sophistication from his readers. However, the actual content that he assumes is fairly minimal and I suspect that a good undergraduate would also enjoy — and be able to learn quite a bit from — this book. As would a graduate student trying to learn combinatorics. Or an algebraic geometer who has stumbled across a combinatorial problem in their research. Or an expert in the field wanting to brush up on their background. Or just about any mathematician wanting to learn something new. And while I haven’t set up the explicit mapping, I imagine that you fall into one or more of these sets.


Darren Glass is an Associate Professor of Mathematics at Gettysburg College. And yes, he is an algebraic geometer who stumbled across a combinatorial problem in his own research as he was counting components of certain moduli spaces. And Stanley’s book was a big help. He can be reached at dglass@gettysburg.edu.

  • Chapter 1: What is Enumerative Combinatorics?
    1. How to count
    2. Sets and multisets
    3. Permutation statistics
    4. The Twelvefold Way 
      Notes 
      References 
      Exercises 
      Solutions to exercises

     

  • Chapter 2: Sieve methods

     

    1. Inclusion-exclusion
    2. Examples and special cases
    3. Permutations with restricted positions
    4. Ferrers boards
    5. V-partitions and unimodal sequences
    6. Involutions
    7. Determinants 
      Notes 
      References 
      Exercises 
      Solutions to exercises

     

  • Chapter 3: Partially Ordered Sets

     

    1. Basic concepts
    2. New posets from old
    3. Lattices
    4. Distributive lattices
    5. Chains in distributive lattices
    6. The incidence algebra of a locally finite poset
    7. The Möbius inversion formula
    8. Techniques for computing Möbius functions
    9. Lattices and their Möbius functions
    10. The Möbius function of a semimodular lattice
    11. Zeta polynomials
    12. Rank-selection
    13. R-labelings
    14. Eulerian posets
    15. Binomial posets and generating functions
    16. An application to permutation enumeration 
      Notes 
      References 
      Exercises 
      Solutions to exercises

     

  • Chapter 4: Rational generating functions

     

    1. Rational power series in one variable
    2. Further ramifications
    3. Polynomials
    4. Quasi-polynomials
    5. P-partitions
    6. Linear homogeneous diophantine equations
    7. The transfer-matrix method 
      Notes 
      References 
      Exercises 
      Solutions to exercises
  • Appendix: Graph Theory Terminology 
    Errata to the First Printing 
    Supplementary Exercises 
    Index