27
$\begingroup$

Hello, can anyone recommend good combinatorics textbooks for undergraduates? I will be teaching a 10-week course on the subject at Stanford, and I assume that the students will be strong and motivated but will not necessarily have background in subjects like abstract algebra or advanced calculus.

I intend to focus on the enumerative side of the subject and do permutations and combinations, generating functions, recurrence relations, Stirling and Catalan numbers, and related topics. However, this hasn't been set in stone and I also welcome advice for what topics to include.

I would be grateful if people would not only suggest names of books but also say a little bit about their merits. Thank you!

Improve this question
$\endgroup$
5
  • $\begingroup$ You might enjoy taking a leaf out of Arthur Benjamin's book, even if it won't fill an entire curriculum: books.google.com/… $\endgroup$
    – Qiaochu Yuan
    Commented Jun 22, 2010 at 20:11
  • $\begingroup$ Hello, thanks to everyone for your answers. In contrast to what I was told initially, my department will mostly be calling the shots (which is perfectly fine with me) and I will be doing a lot of graph theory after all, and using van Lint and Wilson. Thanks to all! $\endgroup$
    – Frank Thorne
    Commented Jun 23, 2010 at 16:58
  • $\begingroup$ @Frank and everyone else: Why do they care whether or not we have a PHD when they hire us to teach classes if they order us what materials to use? Maybe I'm just being too logical. $\endgroup$
    – The Mathemagician
    Commented Jun 24, 2010 at 0:40
  • 2
    $\begingroup$ Andrew -- to answer what is not quite your question, I think consistency from year to year is a very reasonable thing for departments to strive for. I still have plenty of flexibility, and my instructions came from a tenured professor whose expertise in the subject is unquestioned. $\endgroup$
    – Frank Thorne
    Commented Jun 24, 2010 at 17:18
  • 1
    $\begingroup$ The answer will probably overlap with mathoverflow.net/questions/4836/… . $\endgroup$
    – Zsbán Ambrus
    Commented Jun 28, 2011 at 9:08

19 Answers 19

Reset to default
13
$\begingroup$

Two obvious answers are van Lint & Wilson "A Course in Combinatorics" and Peter Cameron "Combinatorics". Which is best really depends on the fine details of your course, and what content you want. Cameron's book has a lot of nice exercises, there are not as many in van Lint & Wilson (and they have a tendency to go of the deep end). As you would expect both books are very well written and have an excellent selection of topics. Cameron's book is possibly more approachable.

Grahm, Knuth and Patashnik is a fine book, but is much more focussed on classical combinatorial sequences and less on combinatorics in general.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think those books might be too difficult for what Frank wants,Chris.Then again,they are Stanford students.So maybe they'll work. $\endgroup$
    – The Mathemagician
    Commented Jun 22, 2010 at 20:20
  • $\begingroup$ I like Cameron's book, and I don't think it's as advanced as all that. $\endgroup$
    – Hugh Thomas
    Commented Jun 23, 2010 at 6:14
11
$\begingroup$

I can hardly do better then recommend the 2 books by Milkos Bona: A Walk Through Combinatorics and Introduction To Enumerative Combinatorics.

The first book is more comprehensive as well as classical,giving thorough discussions of counting arguements and the intuition behind them in addition to bijection arguements.It also contains a very good introduction to graph theory and some topics not normally found in introductory books,like lattices and partial orders.

The second book has considerable overlap with the first,but the emphasis is a lot more on modern counting methods.It is more formal and less intuitive then the first,but the discussion of several topics is better and there are better exercises. The chapter on generating functions is probably the best single chapter source in the current textbook literature on the subject.

Using either or both of these books will give your students a terrific course.There's also quite a bit of material available online for free: Richard Stanley's 2003 Art Of Counting course at the MIT OpenCourseWare website has 233 substantial combinatorics problems for your students to chew on.

You also might want to look at the terrific classic by Wilf on generating functions,generatingfunctionology-available free for download at Wilf's website.

Anywho,those are some of my favorite books on combinatorics.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ An acquaintance who taught a class out of (I believe) A Walk Through Combinatorics found it to be full of typos, so keep an eye out for that. $\endgroup$
    – JBL
    Commented Jun 22, 2010 at 22:57
  • $\begingroup$ (I should say also that I read parts of another Bona book, The Combinatorics of Permutations. I found his writing style enjoyable, and was disappointed to hear about my acquaintance's problems with his other book.) $\endgroup$
    – JBL
    Commented Jun 23, 2010 at 2:09
  • $\begingroup$ A Walk Through Combinatorics has some of the worst puns I know. $\endgroup$
    – Charles Chen
    Commented Jun 29, 2010 at 0:15
  • 1
    $\begingroup$ Can I ask for an example of the puns? $\endgroup$
    – Felix Goldberg
    Commented May 17, 2012 at 8:12
11
$\begingroup$

Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik.

http://en.wikipedia.org/wiki/Concrete_Mathematics

I agree that this book does not make a standard combinatorics course, although it has chapters on binomial coefficients, special numbers, and generating functions. At least it's a very accessible additional source. It definitely does not require a solid background in algebra or calculus.

Improve this answer
$\endgroup$
10
$\begingroup$

It's obviously slanted towards the generating-function view of enumeration, but I enthusiastically recommend Generatingfunctionology by Herb Wilf. It covers all the topics you mentioned, written mainly in the style of examples, rather than theory---something that usually appeals to undergraduates. To me what makes the book a great introduction for a newcomer to combinatorics is Wilf's obvious enthusiasm and easy-going (yet firmly exacting) writing style. The mileage he gets out of changing a recurrence relation into a generating function is truly amazing. I think most undergraduates would be amazed that their skills in calculus can help them enumerate discrete objects, and this book does exactly that over and over again. If price matters, this one is tough to beat---the second edition is free at Wilf's website.

Improve this answer
$\endgroup$
9
$\begingroup$

For a single quarter basic introductory course, I recommend J. Matousek and J. Nesetril, Invitation to Discrete Mathematics, Oxford Univ Press, 1998. I have taught from it several times - it is well written, clear, inexpensive, and fun on occasion. It also has the advantage of being not overly ambitious in scope (compared to van Lint & Wilson, for example, excellent otherwise for a longer course and more advanced students), while still having a good selection of topics.

Improve this answer
$\endgroup$
7
$\begingroup$

I would recommend Combinatorics and Graph Theory, 2nd ed. by Harris, Hirst and Mossinghoff link to publisher's page. It presupposes little more than some knowledge of mathematical induction, a modicum of linear algebra, and some sequences and series material from calculus. The book is divided into three largish chapters: the first on graph theory, the second on combinatorics and the third (more advanced) on infinite combinatorics. Your course sounds like it might cover much of chapter two (sum rule, product rule, binomial and multinomial coefficients, the pigeonhole principle, the principle of inclusion and exclusion, generating functions, Pólya's theory of counting, Stirling numbers, Bell numbers, stable marriage, etc.). There's even a brief introduction to combinatorial geometry. Furthermore, the exposition is clear, with a touch of humour.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I forgot that one,J.W.-it's terrific,but it might be a bit too gentle for the students at Stanford.But by all means,Frank,I concur-give it a look. $\endgroup$
    – The Mathemagician
    Commented Jun 22, 2010 at 20:18
5
$\begingroup$

Notes on Introductory Combinatorics by Pólya, Tarjan, Woods.

Improve this answer
$\endgroup$
5
$\begingroup$

Neither of these suggestions seem to exactly fit the level the OP was aiming for, but I add them for others who come across this thread with a different group of students in mind:

(1) For a gentle, problem-based introduction for undergraduates, I really like Ken Bogart's Combinatorics Through Guided Discovery. Sadly, he passed away while writing the text, but he has left it publically available at no charge.

(2) For a comprehensive and structured approach to combinatorics at the introductory graduate level, I really like Martin Aigner's A Course in Enumeration.

Improve this answer
$\endgroup$
4
$\begingroup$

Combinatorics: Theory and Applications by V. Krishnamurthy.

This is an undergraduate text. Comprehensive and clear. If you live in India, there is an additional benefit: it can be yours for Rs. 275 only (I bought it on flipkart for Rs. 215 recently). It covers Polya Theory, Schur Functions, Matching Theory, Inversion Techniques, Ramsey Theory and Designs. It has a large collection of examples and problems.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That's six US dollars! $\endgroup$
    – Amritanshu Prasad
    Commented Aug 25, 2011 at 6:41
  • $\begingroup$ I should have bought one last year when I was in India and the rupee was weaker. Oh well. Gerhard "Maybe It Is Online Now" Paseman, 2011.08.25 $\endgroup$
    – Gerhard Paseman
    Commented Aug 25, 2011 at 7:08
4
$\begingroup$

I've also been searching for a good undergraduate book for combinatorics, which I'm teaching next fall for the first time. One book not mentioned yet is Brualdi's "Introductory Combinatorics"[1]

It looks to be at a good level for beginning undergraduates while still maintaining a reasonable level of rigor. Some of the comments at Amazon seem say that the most recent edition is an improvement over the previous ones. Anyone have any specific experiences with this book?

[1] http://www.pearsonhighered.com/educator/product/Introductory-Combinatorics/9780136020400.page

Improve this answer
$\endgroup$
3
$\begingroup$

Stanton and White's Constructive Combinatorics emphasizes bijective proofs, and enumerative algorithms (with the theoretical insights that follow from the analysis thereof). The approach beautifully bridges the cultures of mathematics and computer science. I think undergraduates appreciate seeing powerful theoretical methods that nevertheless don't involve much abstraction. The contrast here would be to generating function methods, for which one would need a separate source.

Improve this answer
$\endgroup$
3
$\begingroup$

'Mathematics of Choice : Or, How to Count without Counting' by Ivan Niven. Clear, succinct and an absolute joy to read.

Improve this answer
$\endgroup$
3
$\begingroup$

I liked Roberts & Tesman, Applied Combinatorics (2nd edition), but it's out of print. It has nice applications and nice references.

[Not to be confused with Tucker's book also called Applied Combinatorics]

Improve this answer
$\endgroup$
2
$\begingroup$

Daniel I A Cohen, Basic Techniques Of Combinatorial Theory, covers all the requested topics and more, and has a superb collection of exercises. To give you some idea, in the chapter on binomial coefficients, there are exercises leading you through a proof of Bertrand's Postulate and Chebyshev's estimates for the counting function for the primes.

I think that, unfortunately, the book is out of print.

Another fine book of the same vintage is Alan Tucker, Applied Combinatorics.

Improve this answer
$\endgroup$
2
$\begingroup$

It was long time ago, but I remeber Combinatorial Problems and Exercises by Lovasz fondly. However, this might be too challenging for undergraduates.

Improve this answer
$\endgroup$
2
$\begingroup$

Biggs' discrete mathematics is very well written.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great book, and covers a surprisingly large amount of topics. $\endgroup$
    – 5space
    Commented Aug 10, 2014 at 18:07
1
$\begingroup$

Mazur's recently published Combinatorics guided tour is quite well-organized. This is the MAA page for the book

Improve this answer
$\endgroup$
1
$\begingroup$

If your students aren't yet sophisticated (that is, if the course is to include an intro to proofs, and truth-tables, and induction, and such) then you should definitely pick up a copy of Ralph Grimaldi's "Discrete and Combinatorial Mathematics: An Applied Introduction" (Amazon, Publisher).

This book is very carefully written, and in my opinion does an excellent job of reaching students who are intelligent but who begin the course with little mathematical maturity.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Kevin I'd prefer Harris,Hirst and Mossinghoff (mentioned in one of the previous posts) for such a course,Kevin. But that's me. $\endgroup$
    – The Mathemagician
    Commented Jun 23, 2010 at 4:56
1
$\begingroup$

How about A Path to Combinatorics for Undergraduates: Counting Strategies by Andreescu and Feng. I remember using this for my olympiad preparation a decade ago. Its a well structured book with lots of challenging problems, after all its Andreescu!

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .