Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
You might enjoy taking a leaf out of Arthur Benjamin's book, even if it won't fill an entire curriculum: books.google.com/… –  Qiaochu Yuan Jun 22 '10 at 20:11
1  
I made this community wiki since it is intended to be a collection of resources. See the faq for details - mathoverflow.net/faq#communitywiki –  François G. Dorais Jun 22 '10 at 21:58
    
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! –  Frank Thorne Jun 23 '10 at 16:58
2  
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. –  Frank Thorne Jun 24 '10 at 17:18
1  
The answer will probably overlap with mathoverflow.net/questions/4836/… . –  Zsbán Ambrus Jun 28 '11 at 9:08
show 1 more comment

19 Answers 19

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.

share|improve this answer
    
I think those books might be too difficult for what Frank wants,Chris.Then again,they are Stanford students.So maybe they'll work. –  Andrew L Jun 22 '10 at 20:20
    
I like Cameron's book, and I don't think it's as advanced as all that. –  Hugh Thomas Jun 23 '10 at 6:14
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
3  
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. –  JBL Jun 22 '10 at 22:57
    
(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.) –  JBL Jun 23 '10 at 2:09
    
A Walk Through Combinatorics has some of the worst puns I know. –  Charles Chen Jun 29 '10 at 0:15
    
Can I ask for an example of the puns? –  Felix Goldberg May 17 '12 at 8:12
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Andrew L Jun 22 '10 at 20:18
add comment

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.

share|improve this answer
    
That's six US dollars! –  Amritanshu Prasad Aug 25 '11 at 6:41
    
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 –  Gerhard Paseman Aug 25 '11 at 7:08
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
@Kevin I'd prefer Harris,Hirst and Mossinghoff (mentioned in one of the previous posts) for such a course,Kevin. But that's me. –  Andrew L Jun 23 '10 at 4:56
add comment

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.

share|improve this answer
add comment

Biggs' discrete mathematics is very well written.

share|improve this answer
    
I agree. It was my first introduction to mathematics and it was understandable to me even at that time (middle school). Biggs' books are very comprehensively written. –  Jernej May 17 '12 at 19:33
add comment

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.