by Richard A. Brualdi
Prentice Hall, 1999.
This third edition of Introductory Combinatorics contains extensive
rewriting of some sections and the inclusion of some new material and
exercises. Some of the major changes are:
An introductory section on partial orders and equivalence relations
has been added to Chapter 4.
Chapter 5 contains a new section on partially ordered sets, where
Dilworth's theorem and its dual are proved.
Chapter 8 now includes a section on partitions of a positive integer.
In Chapter 11, the first chapter on graph theory, a tree is now
defined as a connected graph that becomes disconnected upon the
removal of any edge, and the section on digraphs has been removed.
Chapter 12, which is new, discusses digraphs and networks. This
chapter includes a proof of the max-flow min-cut theorem of Ford and
Fulkerson, from which Menger's theorem and K\"onig's theorem of
Chapter 9 are deduced as corollaries.
Fundamental numbers of graph theory (Chapter 12 in the second
edition) is now Chapter 13.
P\'olya counting, formerly Chapter 13, is now Chapter 14.
There is enough material in this third edition for a two semester
course. A first semester could have an emphasis on counting and a
second semester an emphasis on graph theory. A brief commentary on
each of the chapters and their interrelation follows:
Chapter 1 is an introductory chapter. Chapter 2, on the pigeonhole
principle, should be discussed at least in abbreviated form. But note
that no use is made later of some of the harder applications of the
pigeonhole principle and of the section on Ramsey's theorem. Chapters
3 to 8 are primarily concerned with counting techniques and
properties of some of the resulting counting sequences. They should
be covered in sequence. Chapter 4 is about schemes for generating
permutations and combinations and, as mentioned above, includes an
introduction to partial orders and equivalence relations. However,
except for the section on partially ordered sets in Chapter 5,
chapters beyond Chapter 4 are essentially independent of Chapter 4,
and so this chapter can either be omitted or abbreviated. Chapter 5
is on properties of the binomial coefficients, and Chapter 6 covers
the inclusion-exclusion principle. Chapter 7 is a long chapter on
solving recurrence relations and the use of generating functions in
counting. Chapter 8 is concerned mainly with the Catalan numbers, the
Stirling numbers of the first and second kind, and partition numbers.
The chapters that follow are independent of it. Chapter 9 concerns
matchings in bipartite graphs. I introduce bipartite graphs before
graphs, but there is no essential dependence of this chapter on the
later chapters on graph theory. Except for the application of
matching theory to Latin squares, Chapter 10 on designs is
independent of the rest of the book. Toward the end of section 10.4,
I make use of the matching theory developed in Chapter 9. Chapters
11 and 13 contain an extensive discussion of graphs, with some
emphasis on graph algorithms. Chapter 12 is concerned with digraphs
and network flows. Chapter 14 deals with counting in the presence of
the action of a permutation group and does make use of many of the
earlier counting ideas. Except for the last example, it is
independent of the chapters on graph theory and designs. In Chapter
15, I give solutions and hints for some of the approximately 500
exercises in the book.
A few of the exercises have a $\ast$ symbol beside them, indicating
that they are more challenging. The end of a proof and the end of an
example are indicated by writing a $\Box$ symbol.
It is difficult to assess the prerequisites for this book. Perhaps
they can be best described as the mathematical maturity achieved by
the successful completion of the calculus sequence and an elementary
course on linear algebra. Use of calculus is minimal, and the
references to linear algebra are few and should not cause any problem
to those not familiar with it.
I am very grateful to many individuals who encouraged me to do a
third edition and who provided me with useful comments. To avoid the
risk of not acknowledgeing someone, I will mention only Leroy F.
Meyers and Tom Zaslavsky, each of whom provided me with extensive and
detailed comments. The book, I hope, continues to reflect my love of
the subject of combinatorics and my enthusiasm for teaching it.
Finally, I thank my dear wife, Mona, who has brought such happiness,
spirit, and adventure into my life.
Richard A. Brualdi
Go back to Home
Page