You are here

A Course in Combinatorics

Cambridge University Press
Number of Pages: 

This is a very wide-ranging survey of combinatorics, presented as an introductory course at the upper undergraduate level. The recommended background is familiarity with abstract algebra, but some chapters need less than this and some depend on some knowledge of other areas of mathematics. The very beginning of the book gives a clever solution of the Instant Insanity puzzle that depends on casting it as a graph and then getting the solution by inspection, without any formal knowledge of graph theory (or of mathematics).

The book meets the authors’ stated goals that “students who subsequently attend a conference on ‘Combinatorics’ would hear no talks where they are completely lost because of unfamiliarity with the topic” and of “doing something substantial or nontrivial with each topic.” The book is slanted away from counting as the final result, and generating functions play a small role, although most parts of the book depend on counting arguments to get the results. There is quite a lot of material on combinatorial designs. Each chapter has challenging exercises scattered through it, and ends with helpful and interesting historical and biographical notes.

The book does not go into great depth on any topic, but it does discuss the most important topics and may state the relevant theorems without proof. For example, Kuratowski’s characterization of planar graphs is quoted and discussed in detail, but not proved. The four-color theorem is stated and discussed, and the five-color theorem is proved and the ideas related to the four-color problem. The standout subject is the chapter on Pólya’s theory of counting. This subject is very difficult to explain well, but the exposition here is very clear, concise, and illustrated with helpful examples.

Allen Stenger is a math hobbyist, library propagandist, and retired computer programmer. He volunteers in his spare time at, a math help site that fosters inquiry learning. His mathematical interests are number theory and classical analysis.

Date Received: 
Wednesday, December 30, 2009
Include In BLL Rating: 
J. H. van Lint and R. M. Wilson
Publication Date: 
Allen Stenger
BLL Rating: 

Preface to the first edition

Preface to the second edition

1. Graphs

2. Trees

3. Colorings of graphs and Ramsey’s theorem

4. Turán’s theorem and extremal graphs

5. Systems of distinct representatives

6. Dilworth’s theorem and extremal set theory

7. Flows in networks

8. De Bruijn sequences

9. Two (0,1,*) problems: addressing for graphs and a hash-coding scheme

10. The principle of inclusion and exclusion: inversion formulae

11. Permanents

12. The Van der Waerden conjecture

13. Elementary counting; Stirling numbers

14. Recursions and generating functions

15. Partitions

16. (0,1)-matrices

17. Latin squares

18. Hadamard matrices, Reed-Muller codes

19. Designs

20. Codes and designs

21. Strongly regular graphs and partial geometries

22. Orthogonal Latin squares

23. Projective and combinatorial geometries

24. Gaussian numbers and q-analogues

25. Lattices and Möbius inversion

26. Combinatorial designs and projective geometries

27. Difference sets and automorphisms

28. Difference sets and the group ring

29. Codes and symmetric designs

30. Association schemes

31. (More) algebraic techniques in graph theory

32. Graph connectivity

33. Planarity and coloring

34. Whitney duality

35. Embedding of graphs on surfaces

36. Electrical networks and squared squares

37. Pólya theory of counting

38. Baranyai’s theorem

Appendix 1. Hints and comments on problems

Appendix 2. Formal power series

Name index

Subject index

Publish Book: 
Modify Date: 
Monday, January 17, 2011