From the preface of the 5th edition:
----------------------------------
I have made some substantial changes in this new edition of {\it
Introductory Combinatorics}, and they are summarized as follows:
\begin{enumerate}
\item[] In Chapter 1, a new section (Section 1.6) on mutually overlapping
circles has been added to illustrate some of the counting
techniques in later chapters. Previously the content of this section
occured in Chapter 7.
\item[] The old section on cutting a cube in Chapter 1 has been deleted,
but the content appears as an exercise.
\item[] Chapter 2 in the previous edition (The Pigeonhole Principle) has
become Chapter 3.
Chapter 3 in the previous edition, on permutations and combinations, is
now Chapter 2.
Pascal's formula, which in the previous edition first appeared in Chapter
5, is now in Chapter 2.
In addition, we have de-emphasized the use of the term {\it combination}
as it applies to a set, using the essentially equivalent term of
{\it subset} for clarity. However, in the case of multisets, we
continue to use
{\it combination} instead of, to our mind, the more cumbersome term
{\it submultiset}.
\item[] Chapter 2 now contains a short section (Section 3.6) on finite
probability.
\item[] Chapter 3 now contains a proof of Ramsey's theorem in the case of
pair$
\item[] Some of the biggest changes occur in Chapter 7, in which
generating
functions and exponential generating functions have been moved to earlier
in the chapter
(Sections
7.2 and 7.3) and have become more central.
\item[] The section on partition numbers (Section 8.3) has been
expanded.
\item[] Chapter 9 in the previous edition, on matchings in bipartite
graphs, has
undergone a major change. It is now an interlude chapter (Chapter 9) on
systems of distinct representatives (SDRs)---the
marriage
and stable marriage problems---and the discussion on bipartite graphs
has been removed.
\item[] As a result of the change in Chapter 9,
in the introductory
chapter on graph theory (Chapter
11), there is no longer the assumption that
bipartite graphs have been discussed previously.
\item[] The chapter on more topics of graph theory (Chapter 13 in the
previous edition)
has
been moved to Chapter 12. A new section on the matching number of a
graph (Section 12.5) has been added in which the basic SDR result of
Chapter 9
is applied to bipartite graphs.
\item[] The chapter on digraphs and networks (Chapter 12 in the previous
edition) is now
Chapter 13. It contains a new section that revisits matchings in
bipartite graphs,
some of which appeared in Chapter 9 in the previous edition.
\end{enumerate}
In addition to the changes just outlined, for this fifth edition, I have
corrected all of the typos that were brought to my attention; included
some small additions; made some clarifying changes in exposition
throughout; and added many new exercises. There are now 700 exercises in
this fifth edition.
Based on comments I have received over the years from many people, this
book seems to have passed the test of time. As a result I always hesitate
to make too many changes or to add too many new topics. I don't like
books that have ``too many words'' (and this preface will not have too
many words) and that try to accomodate everyone's personal preferences on
topics. Nevertheless, I did make the substantial changes described
previously because I was convinced they would improve the book.
As with all previous editions, this book can be used for either a one--
or two--semester undergraduate course. A first semester could emphasize
counting, and a second semester could emphasize graph theory and designs.
This book would also work well for a one--semester course that does some
counting and graph theory, or some counting and design theory, or
whatever combination one chooses. A brief commentary on each of the
chapters and their interrelation follows.
Chapter 1 is an introductory chapter; I usually select just one or two
topics from it and spend at most two classes on this chapter. Chapter 2,
on permutations and combinations, should be covered in its entirety.
Chapter 3, on the pigeonhole principle, should be discussed at least in
abbreviated form. But note that no use is made later of some of the more
difficult applications of the pigeonhole principle and of the section on
Ramsey's theorem. Chapters 4 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 includes an introduction to
partial orders and equivalence relations in Section 4.5. I think one
should at$ discuss equivalence relations, since they are so ubiquitous in
mathematics. Except for the section on partially ordered sets (Section
5.7) in Chapter 5, chapters beyond Chapter 4 are essentially independent
of Chapter 4, and so this chapter can either be omitted or abbreviated.
And one can decide not to cover partially ordered sets at all. I have
split up the material on partially ordered sets into two sections
(Sections 4.5 and 5.7) in order to give students a little time to absorb
some of the concepts. Chapter 5 is on propert$ of the binomial
coefficients, and Chapter 6 covers the inclusion--exclusion principle.
The section on M\"obius inversion, generalizing the inclusion--exclusion
principle, is not used in later sections. Chapter 7 is a long chapter on
generating functions and solutions of recurrence relations. Chapter 8 is
concerned mainly with the Catalan numbers, the Stirling numbers of the
first and second kind, partition numbers and the large and small
Schr\"oder numbers. One could stop at the end of any section of this
chapter. The chapters that follow Chapter 8 are independent of it.
Chapter 9 is about systems of distinct representatives (so-called
marriage problems). Chapters 12 and 13 make some use of Chapter 9, as
does the section on Latin squares in Chapter 10. Chapter 10 concerns some
aspects of the vast theory of combinatorial designs and is independent of
the remainder of the book. Chapters 11 and 12 contain an extensive
discussion of graphs, with some emphasis on graph algorithms. Chapter 13
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.
When I teach a one-semester course out of this book, I like to conclude
with Burnside's theorem, and several applications of it, in Chapter 14.
This result enables one to solve many counting problems that can't be
touched with the techniques of earlier chapters. Usually, I don't get to
P\'olya's theorem.
Following Chapter 14, I give solutions and hints for some of the 700
exercises in the book. A few of the exercises have a $\ast$ symbol beside
them, indicating that they are quite challenging. The end of a proof and
the end of an example are indicated by writing the symbol $\Box$.
It is difficult to assess the prerequisites for this book. As with all
books intended as textbooks, having highly motivated and interested
students helps, as does the enthusiasm of the instructor. Perhaps the
prerequisites 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.
It is especially gratifying to me that, after more than 30 years since
the first edition of {\it Introductory Combinatorics} was published, it
continues to be well received by many people in the professional
mathematical community.