Good combinatorics textbooks for teaching undergraduates? - MathOverflow

Good combinatorics textbooks for teaching undergraduates?

2010-06-22T19:10:29Z

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!

Answer by AlB for Good combinatorics textbooks for teaching undergraduates?

2010-06-22T19:46:00Z

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.

Answer by J W for Good combinatorics textbooks for teaching undergraduates?

2010-06-22T19:51:27Z

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.

Answer by Chris Godsil for Good combinatorics textbooks for teaching undergraduates?

2010-06-22T19:53:08Z

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.

Answer by Andrew L for Good combinatorics textbooks for teaching undergraduates?

2010-06-22T20:15:34Z

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.

Answer by SandeepJ for Good combinatorics textbooks for teaching undergraduates?

2010-06-22T22:02:24Z

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

Answer by Igor Pak for Good combinatorics textbooks for teaching undergraduates?

2010-06-22T22:43:01Z

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.

Answer by Kevin O'Bryant for Good combinatorics textbooks for teaching undergraduates?

2010-06-22T22:56:37Z

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.

Answer by Gerry Myerson for Good combinatorics textbooks for teaching undergraduates?

2010-06-24T00:17:56Z

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.

Answer by lhf for Good combinatorics textbooks for teaching undergraduates?

2010-06-25T13:10:28Z

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

Answer by Leah Wrenn Berman for Good combinatorics textbooks for teaching undergraduates?

2010-06-28T21:37:21Z

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

Answer by Amritanshu Prasad for Good combinatorics textbooks for teaching undergraduates?

2011-08-25T06:23:35Z

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.

Answer by Russell May for Good combinatorics textbooks for teaching undergraduates?

2011-08-25T13:54:22Z

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.

Answer by Jeff Norden for Good combinatorics textbooks for teaching undergraduates?

2012-05-17T04:16:50Z

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

Answer by David Feldman for Good combinatorics textbooks for teaching undergraduates?

2012-05-17T04:46:16Z

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.

Answer by Saikat Biswas for Good combinatorics textbooks for teaching undergraduates?

2012-05-17T06:20:23Z

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

Answer by Yiftach Barnea for Good combinatorics textbooks for teaching undergraduates?

2012-05-17T06:46:30Z

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

Answer by Michael Joyce for Good combinatorics textbooks for teaching undergraduates?

2012-05-17T15:51:27Z

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.

Answer by Igor Rivin for Good combinatorics textbooks for teaching undergraduates?

2012-05-17T16:08:36Z

Biggs' discrete mathematics is very well written.