Undergrad-level combinatorics texts easier than Stanley's Enumerative Combinatorics?

I am an undergrad, math major, and I had basic combinatorics class before (undergrad level.) Currently reading Stanley's Enumerative Combinatorics with other math folks. We have found this book somewhat challenging~ Do you have any suggestions on other books to read? or books to help going thru Enumerative combinatorics?


Solution 1:

Here is a somewhat haphazard list of sources on algebraic combinatorics which appear to be suited to undergraduates (I have not personally read most of them, so I am making semi-educated guesses here). My notion of "algebraic combinatorics" includes such things as binomial coefficient identities, symmetric functions, lattice theory, enumerative problems, Young tableaux, determinant identities; it does not include graph theory (except for the parts of it that are secretly algebra) or extremal combinatorics.

General remarks:

  • Combinatorics is a living subject, and so are the authors of many of the sources listed below. If you find errors, do let them know!

  • If some of the links below are inaccessible, try adding https://web.archive.org/web/*/ before the link. For example, https://www.whitman.edu/mathematics/cgt_online/cgt.pdf would become https://web.archive.org/web/*/https://www.whitman.edu/mathematics/cgt_online/cgt.pdf. This will take you to an archived version of the link (assuming that archive.org has made such a version).

Textbooks/notes on algebraic combinatorics in general:

Stanley's EC (Enumerative Combinatorics) is supposed to be a challenging read for graduate students. In its (rather successful) attempt at being encyclopedic, it has very little space for details and leaves a lot to the reader. There are many other texts on combinatorics, and I suspect that the average among them will be easier to read than EC1 (although probably less "from the horse's mouth"). In no particular order:

  • Jeremy Martin, Lecture Notes on Algebraic Combinatorics. This covers posets, matroids, hyperplane arrangements, symmetric functions, among other things.

  • Richard Stanley, Algebraic Combinatorics. This is still Stanley, but now explicitly writing for undergrads. Unlike EC1-2, this is not trying to survey everything, and so what it does is given more space. The 2nd edition is out already.

  • Miklos Bona, A Walk Through Combinatorics. This is a student of Stanley. The 4th edition appeared in 2017. Errata.

  • Edward A. Bender and S. Gill Williamson, Foundations of Combinatorics with Applications, 2006. This covers both enumeration and graph theory; the specific choice of topics appears tailored to computer scientists.

  • Bruce Sagan, Combinatorics: The Art of Counting. This is a draft of a book that has been published by AMS in 2020. It is meant for readers "at the advanced undergraduate or beginning graduate level" and appears to assume some knowledge of abstract algebra. Errata.

  • Anna de Mier, Lecture notes for "Enumerative Combinatorics", 2004. (Alternative link via archive.org.)

  • Geir Helleloid, Algebraic combinatorics (fall 2008). Rough draft of a grad-level course with some newer results. No longer easily found online, but downloadable from gen.lib (as many other books that are not easily found online...).

  • Kenneth P. Bogart, Combinatorics Through Guided Discovery. (Specifically, the 2017 version is the most up-to-date so far.) This is a heavily introductory text, written as a collection of exercises with ample hints and motivation. (Yes, there is a version with solutions in the tar.gz source archive.) I have seen lots of people use this text in classes, so I assume it's good.

  • Nicholas A. Loehr, Bijective Combinatorics, 2011. See his website for errata. What little I've seen of this book is great, and I have used it in my teaching. It is one of very few sources defining formal power series properly. There is a 2nd edition out, which is just called Combinatorics and seems to feature new sections on quasisymmetric functions as well as shuffled-around material on power series; your mileage may vary as to whether that update is worth the money.

  • David R. Mazur, Combinatorics: A Guided Tour, MAA 2010. An introduction into various kinds of combinatorics (including both counting and graph theory). Claims to be graduate-level, although I would place it at (late) undergraduate level based on its content. I have heard good things about it.

  • Drew Armstrong, Discrete mathematics, 2019. An introductory undergraduate class that includes the basics of enumerative combinatorics (up until Prüfer codes for trees) and of graph theory, probably quite appropriate as an appetizer before most of the other texts here. Armstrong writes in an intriguing conversational way that exposes not just proofs but also motivations and thought processes (as well as tidbits of tangential context).

  • David Guichard, An Introduction to Combinatorics and Graph Theory, 2017.

  • Alexander Hulpke, Combinatorics is another fresh set of notes for a combinatorics class (2 semesters, graduate).

  • Nicolaas Govert de Bruijn, J. W. Nienhuys, Ling-Ju Hung, Tom Kloks, de Bruijn's Combinatorics. These are notes from a class by de Bruijn himself. Might be terse in places, but probably worth it for the informal classroom style. (The only useful file I've ever found on viXra...)

  • Peter J. Cameron, Notes on Combinatorics; see also the rest of his notes, including the "St Andrews Notes on Advanced Combinatorics" (errata to part 1). Unfortunately, this has the classical British terseness as far as the proofs are concerned; I wouldn't recommend it for self-learning.

  • Gary MacGillivray, Course Notes Math 422 Combinatorial Mathematics, 2011.

  • Torsten Ueckerdt, Lecture notes Combinatorics, scribed by Stefan Walzer; see also the class site. (Old version from 2015.) These notes are more suited for grad students due to their brevity, but an undergrad will likely find something of interest in there. Unofficial errata.

  • Ulrich Dempwolff, Algebraic Combinatorics. These, too, are lecture notes for a more graduate audience.

  • Richard A. Brualdi, Introductory Combinatorics, 5th edition 2010. See his website for errata. From what I've seen, a thorough and detailed text with a classical focus (enumeration, flows&cuts, designs).

  • Martin Aigner, A course in enumeration, Springer 2007.

  • J. H. van Lint, R. M. Wilson, A Course in Combinatorics, 2nd edition, CUP 2001. In the comments, Brian M. Scott warns that this is "graduate level and not easy going".

  • Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan, Combinatorics: The Rota Way, CUP 2009 is a nonstandard textbook, originating from Rota's MIT classes and reflecting his interests (many of which have never hit the combinatorial mainstream). Errata and a sample chapter.

  • Carl G. Wagner, Basic Combinatorics. This looks like another introductory set of notes for (enumerative) combinatorics, with a somewhat algebraic touch (generating functions, difference operators and linear recursions are major topics). Also, the first chapter of Carl G. Wagner, Choice, Chance and Inference (a textbook on probability) by the same author treats the very basics of enumerative combinatorics. Finally, the recent book Carl G. Wagner, A First Course in Enumerative Combinatorics (AMS 2020) by the same author goes deeper.

  • David G. Wagner's website (the link goes to archive.org) is a treasure trove of old material, although navigating it on archive.org can be a pain. Highlights: combinatorics lecture notes by David Wagner and lecture notes by Chris Godsil.

  • Stephan Wagner, Combinatorics is yet another set of notes. Generating functions appear to be the red thread here. Seems terse, though.

  • Ian Goulden, Math 249 notes is more detailed than I would have expected given its length and coverage. The first half is an introduction to the uses (including some rather advanced ones) of generating functions; the second is devoted to graph theory.

  • Gregory G. Smith's Math 402 Fall 2019 lecture notes cover elementary counting techniques and generating functions.

  • David Galvin's Math 60610 Spring 2017 lecture notes mostly on enumerative combinatorics. Currently, a more up-to-date version can be found on my website (but probably will go back to David's eventually). This is a grad-level course that should work for sufficiently cultured undergraduates as well.

  • Kevin Purbhoo's 630 notes ("Algebraic Enumeration") introduce various more advanced topics such as species, symmetric functions, representations of symmetric groups and cycle index functions.

  • Melody Chan, Introduction to Higher Mathematics: Combinatorics and Graph Theory (scroll down) looks like a nice little introduction.

  • Michael Tait, Lecture Notes for 21-301: Combinatorics, 2017 version and 2018 version and 2021 version. Most of this is about extremal combinatorics, but the first 30 or so pages of the 2017 version are a short introduction to enumeration.

  • Michel Goemans, Math 18.310A (2015) is a rather eclectic discrete mathematics class; it includes notes on counting and on generating functions.

  • I have started writing lecture notes on enumerative combinatorics with the eventual goal of covering all the basics with Bourbakist rigor while remaining reasonably readable. At the moment, the first two chapters are finished; more is to come when I get to teach the same class again. I have also started writing introductory lecture notes on algebraic combinatorics; I am not sure how far they will go and how detailed they will be.

I don't know these books/notes well enough to tell which of them are better suited for a first course (although I don't have any reasons to suspect any of them to be unsuitable), but it cannot hurt to try each of them and go as far as you can before meeting serious resistance. (And once you meet serious resistance, either keep going or try the next one.) Half of these are freely available (and so are the other half, if you search in the darker places).

Specific subjects:

Just a few so far...

Enumeration:

  • Miklos Bona, Introduction to Enumerative Combinatorics, 2007. This is another Bona book, and explicitly directed at undergraduates, though it does percolate into some advanced topics as well (unimodality, magic square enumeration). A 2nd edition has come out in 2016 under the extended title Introduction to Enumerative and Analytic Combinatorics (adding, as the name change suggests, a chapter on analytic combinatorics). Errata.

  • Tero Harju, Combinatorial Enumeration (Fall 2011). This is a short introductory class with lecture notes and exercises.

  • Alex Fink, Enumerative Combinatorics (Fall 2015). Another short course, doing some of the nicest stuff (in my opinion). The writing is enjoyable, but perhaps too terse for an undergraduate reader.

  • Arthur Benjamin and Jennifer Quinn, Proofs that Really Count. This looks rather introductory (focusing on proofs of identities involving binomial coefficients or Fibonacci numbers using bijections). (Suggested by JSchlather.)

  • Titu Andreescu and Zuming Feng, A Path to Combinatorics for Undergraduates: Counting Strategies. Another introduction to enumerative combinatorics. This one takes a problem-solving approach, illustrating principles on olympiad-style problems. (Suggested by Marko Amnell.)

  • Chen Chuan-Chong and Koh Khee-Meng, Principles and Techniques in Combinatorics is another text that approaches the subject through olympiad problems.

  • Dominique Foata and Guo-Niu Han, Principes de Combinatoire Classique, 2008. These are the notes (in French) of a "cursus de la maîtrise" (equivalent to first year of master's degree) at Strasbourg; they include several subjects not commonly found in introductions (Eulerian polynomials, Lagrange inversion, symmetric functions). Foata is one of the major names in combinatorial enumeration.

  • Dominique Foata and Guo-Niu Han, The q-series in combinatorics; permutation statistics is a text on $q$-enumeration, focusing on its permutations. Some symmetric function theory included.

  • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd edition 1994 (errata). This one is really sui generis and not fully a combinatorics book; it discusses elementary number theory, several important integer sequences, binomial coefficients and their multiple identities (unlike many texts, the focus here is less on bijective proofs and more on algebraic tricks), generating functions and some probability.

  • Donald E. Knuth, The Art of Computer Programming was started in 1962 as an attempt at a comprehensive textbook for programming. Four volumes are out by now, thus giving computer science its own Song of Ice and Fire to wait on. Arguably, much of the books is not overly relevant to modern computer science, but combinatorics (enumerative and algorithmic and occasionally even algebraic) is everywhere dense in them (at least in Volumes 1, 3 and 4A), and Knuth's propensity to wildly curious digressions (one gets the impression that he even digresses from digressions) makes these books an incredibly addictive nerd-read. Volume 3 is the one most relevant to algebraic combinatorics, with its §5.1 devoted to permutations and tableaux. Few authors have dug as deep as Knuth into the history of the subject -- witness a draft of §7.2.1.7.

  • Herbert S. Wilf, generatingfunctionology, on enumeration using generating functions. This is the 2nd edition. The newer 3rd edition can be bought from Amazon. (Suggested by Fredrik Meyer.)

  • Andrés Aranda, Manuel Bodirsky, Combinatorics. These are notes for what would probably be a late-undergrad topics class (in Germany, a third year bachelor course). They cover flows/cuts, probabilistic method, Ramsey theory, generating functions. There is a more elementary prequel (Diskrete Strukturen) in German. Both are works in progress and welcome corrections.

  • David M. Bressoud, Proofs and Confirmations: The Story of the Alternating-Sign Matrix Conjecture. This is a nonstandard introduction to algebraic combinatorics which, instead of covering the basics breadth-first, takes aim at a recent result (the alternating-sign matrix conjecture), introducing everything necessary for it along the way. (Errata.)

  • Peter J. Cameron, Notes on Counting goes deeper into enumeration than his above-mentioned Notes on Combinatorics. A draft version is available online.

  • Jay Pantone, Graduate Combinatorics, 2016 lecture notes. This is about generating functions, including some advanced methods. Not so much written for undergraduates (see the title), but probably a good second confrontation with power series.

  • Qiaochu Yuan, Topics in generating functions. What the title says. Written for maths olympiad trainees, thus terser and less theoretical but also more eclectic than the usual texts, with various examples not commonly found.

  • Markus Fulmek, VO Combinatorics, 2018. Graduate topics course covering species, asymptotics and posets.

Young tableaux and representations of symmetric groups:

  • William Fulton, Young tableaux, CUP 1997. Part I and Appendix A are purely combinatorial, and (in my opinion) the most readable source on a lot of semistandard tableau theory.

  • The papers of Marc van Leeuwen (mostly on Young tableaux) have a significant expository component.

  • Bruce Sagan, The Symmetric Group, 2nd edition 2001. See also the errata on Sagan's website. This is somewhere between undergraduate and graduate in level, and covers symmetric functions, Young tableaux and representations of the symmetric group. I can recommend this. (There is surprisingly little intersection with Fulton's book.) Sagan's papers, including this expository one on Young tableaux, are also worth a mention.

  • Mark Wildon's lecture notes include some on symmetric functions (errata) and some on symmetric groups (highly recommended). (He is also writing a textbook on enumerative combinatorics, and the first two chapters are available.)

  • Anthony Mendes, Jeffrey Remmel, Counting with Symmetric Functions is a treatment of the symmetric functions and the RSK algorithm that claims to be a graduate text, probably because it uses some abstract algebra; but it doesn't seem particularly unforgiving.

  • Eric Egge, An Introduction to Symmetric Functions and their Combinatorics, AMS 2019. Recent introduction to the subject, using mostly combinatorial methods. Requires rather little algebra, but the combinatorics can become somewhat vertiginous. Suited for advanced undergraduates or graduates.

  • D. Laksov, A. Lascoux, P. Pragacz, and A. Thorup, The LLPT notes. This is a fairly readable introduction to the combinatorial part of Schubert calculus and the work of Lascoux and others. (Don't worry about the missing sections; nothing depends on them.)

  • Claudio Procesi, Lie Groups -- An Approach through Invariants and Representations, Springer 2007. This is probably the most combinatorial textbook ever written on Lie groups (particularly, Chapters 9, 12 and 13).

  • Hanspeter Kraft and Claudio Procesi, Classical Invariant Theory -- A Primer. I made an unofficial list of errata for this long ago. It is partly a precursor of the Procesi book above, so expect quite some intersection.

  • Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli, Representation theory of the symmetric groups, CUP 2010. A slow-paced introduction to symmetric functions and representations of symmetric groups, taking a rather nonstandard approach. (Particularly recommended due to the inclusion of partition algebras, which are currently underexposed in textbooks.)

  • Alistair Savage, Modern Group Theory is a set of lecture notes in development, following the Ceccherini-Silberstein-Scarabotti-Tolli book on representations of the symmetric groups. (Other notes by same author.)

  • Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Springer 2005 (downloadable); see also the errata. This is a graduate text, but it starts off with rather elementary things.

  • Geordie Williamson, Mind your $P$- and $Q$-symbols, Honours thesis 2003. This is actually an introduction into Coxeter groups, the RSK algorithm, and Hecke algebras, written by someone who went on to prove one of the main conjectures in the latter field.

Monoids:

  • Benjamin Steinberg, The representation theory of finite monoids, Springer 2016 (see also a public draft). You might not regard monoid/semigroup theory as combinatorics, but this book crosses over into combinatorics several times (particularly Chapters 7 and 15).

  • Tero Harju, Lecture Notes on Semigroups, 1996 and Tero Harju, Lecture Notes on Semigroups, 2017.

Combinatorics on words:

  • J. Berstel, J. Karhumäki, Combinatorics on Words -- A Tutorial.

  • Lothaire's Combinatorics on Words trilogy. The 2nd and 3rd volume are downloadable in PS format from this link; the 1st can be found elsewhere. These are edited volumes -- usually with a different author per chapter; but significant parts of them can be used as texts.

  • Jean Berstel, Aaron Lauve, Christophe Reutenauer, Franco Saliola, Combinatorics on Words: Christoffel Words and Repetitions in Words.

  • Dominique Perrin and Antonio Restivo, Enumerative Combinatorics on Words, a chapter from the "Handbook of Enumerative Combinatorics" (edited by Miklós Bóna, CRC 2015). Unlike many other chapters of that Handbook, this one seems self-contained, and is the only exposition of many newer results around Lyndon words and the Gessel-Reutenauer transform. Some unofficial errata.

Chipfiring aka sandpiles:

Chip-firing is ostensibly about (a certain "game" on) graphs, but once you start studying it, algebraic structures quickly emerge. Thus, the subject is beloved by many combinatorialists that don't usually study graphs.

  • Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp and David B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs, arXiv:0801.3306v4. This is a well-written (if somewhat terse) introduction; I learnt chip-firing here. Errata to an older version (some still apply).

  • Scott Corry, David Perkinson, Divisors and Sandpiles: An Introduction to Chip-Firing, AMS 2018 is an introduction written with undergraduate readers in mind. Draft version.

  • Caroline J. Klivans, The Mathematics of Chip-firing, CRC Press 2019 is new and freely available. It covers various generalizations of chip-firing as well.