You are here

Introductory Combinatorics

Richard A. Brualdi
Prentice Hall
Publication Date: 
Number of Pages: 
BLL Rating: 


[Reviewed by
Miklós Bóna
, on

This is one of only a few classic introductory combinatorics textbooks for undergraduates. The author of such a textbook faces an unusally high number of difficult choices of what topics to include, and in what order, so the reviewer’s task is to discuss the choices the author decided to make. Enumeration is the topic favored by the author, in that nine of his fourteen chapters have this topic at their center. This is an appropriate choice of focus since in most branches of combinatorics, counting is, if not the goal, then at least a tool.

The order of in which the topics are discussed also favors enumeration. Advanced enumeration techniques are treated relatively early in the book. Möbius inversion is explained in Chapter 6, while generating functions are introduced in Chapter 7, so these advanced topics are part of the first half of the text. There is a separate chapter on some famous counting sequences, such as the Catalan numbers and the Schröder numbers, and even that comes before the parts of the book that are not devoted to enumeration.

The next part of the book has gone through a major change since the last edition. Chapter 9 is about systems of distinct representatives, Chapter 10 is on Combinatorial Designs, and the following three chapters are on graph theory. This probably sets the book apart from most similar textbooks: it is easy to view both systems of distinct representatives and Combinatorial Designs as generalizations of concepts in Graph Theory, and therefore, most authors treat graphs first. The order chosen in this book probably has the effect that if you teach a two-semester course from the book, and cover all topics in it in the order in which the book covers them, then all of Graph Theory will be discussed in the second semester.

The book ends with a chapter on Pólya theory (enumeration under group action).

There are about 40 exercises at the end of each chapter, some of which are, commendably, challenging enough to be interesting even for the instructors. Roughly half of them have a numerical answer or a hint at the end of the book, but none come with full solutions.

Miklós Bóna is Professor of Mathematics at the University of Florida.

1. What is Combinatorics?

1.1 Example: Perfect Covers of Chessboards

1.2 Example: Magic Squares

1.3 Example: The Four-Color Problem

1.4 Example: The Problem of the 36 Officers

1.5 Example: Shortest-Route Problem

1.6 Example: Mutually Overlapping Circles

1.7 Example: The Game of Nim


2. The Pigeonhole Principle

2.1 Pigeonhole Principle: Simple Form

2.2 Pigeonhole Principle: Strong Form

2.3 A Theorem of Ramsay


3. Permutations and Combinations

3.1 Four Basic Counting Principles

3.2 Permutations of Sets

3.3 Combinations of Sets

3.4 Permutations of Multisets

3.5 Combinations of Multisets

3.6 Finite Probability


4. Generating Permutations and Combinations

4.1 Generating Permutations

4.2 Inversions in Permutations

4.3 Generating Combinations

4.4 Generating r-Combinations

4.5 Partial Orders and Equivalence Relations


5. The Binomial Coefficients

5.1 Pascal's Formula

5.2 The Binomial Theorem

5.3 Unimodality of Binomial Coefficients

5.4 The Multinomial Theorem

5.5 Newton's Binomial Theorem

5.6 More on Partially Ordered Sets


6. The Inclusion-Exclusion Principle and Applications

6.1 The Inclusion-Exclusion Principle

6.2 Combinations with Repetition

6.3 Derangements

6.4 Permutations with Forbidden Positions

6.5 Another Forbidden Position Problem

6.6 Möbius Inversion


7. Recurrence Relations and Generating Functions

7.1 Some Number Sequences

7.2 Generating Functions

7.3 Exponential Generating Functions

7.4 Solving Linear Homogeneous Recurrence Relations

7.5 Nonhomogeneous Recurrence Relations

7.6 A Geometry Example


8. Special Counting Sequences

8.1 Catalan Numbers

8.2 Difference Sequences and Stirling Numbers

8.3 Partition Numbers

8.4 A Geometric Problem

8.5 Lattice Paths and Schröder Numbers


9. Systems of Distinct Representatives

9.1 General Problem Formulation

9.2 Existence of SDRs

9.3 Stable Marriages


10. Combinatorial Designs

10.1 Modular Arithmetic

10.2 Block Designs

10.3 Steiner Triple Systems

10.4 Latin Squares


11. Introduction to Graph Theory

11.1 Basic Properties

11.2 Eulerian Trails

11.3 Hamilton Paths and Cycles

11.4 Bipartite Multigraphs

11.5 Trees

11.6 The Shannon Switching Game

11.7 More on Trees


12. More on Graph Theory

12.1 Chromatic Number

12.2 Plane and Planar Graphs

12.3 A 5-color Theorem

12.4 Independence Number and Clique Number

12.5 Matching Number

12.6 Connectivity


13. Digraphs and Networks

13.1 Digraphs

13.2 Networks

13.3 Matching in Bipartite Graphs Revisited


14. Pólya Counting

14.1 Permutation and Symmetry Groups

14.2 Burnside's Theorem

14.3 Pólya's Counting formula