Schaum's Outline of Combinatorics [Paperback]

This book is an introduction to combinatorics for the undergraduate mathematics student and for those working in applications of combinatorics. As with all the other guides in the Schaums series on mathematics, this one has a plethora of many interesting examples and serves its purpose well. Readers who need a more in-depth view can move on to more advanced works after reading this one. The author dedicates this book to the famous mathematician Paul Erdos, who is considered the father of modern combinatorics, and is considered one of most prolific of modern mathematicians, with over 1500 papers to his credit.

The author defines combinatorics as the branch of mathematics that attempts to answer enumeration questions without considering all possible cases. The latter is possible by the use of two fundamental rules, namely the sum rule and the product rule. The practical implementation of these rules involves the determination of permutations and combinations, which are discussed in the first chapter, along with the famous pigeonhole principle. Most of this chapter can be read by someone with a background in a typical college algebra course. The author considers some interesting problems in the "Solved Problems" section, for example one- and two-dimensional binomial random walks, and problems dealing with Ramsey, Catalan, and Stirling numbers. The consideration of Ramsey numbers will lead the reader to several very difficult open problems in combinatorics involving their explicit values.

Generalized permutations and combinations are considered in chapter two, along with selections and the inclusion-exclusion principle. The author proves the Sieve formula and the Phillip Hall Marriage Theorem. In the "Solved Problems" section, the duality principle of distribution, familiar from integer programming is proved, and the author works several problems in combinatorial number theory. A reader working in the field of dynamical systems will appreciate the discussion of the Moebius function in this section. Particularly interesting in this section is the discussion on rook and hit polynomials.

The consideration of generating functions and recurrence relations dominates chapter 3, wherein the author considers the partition problem for positive integers. The first and second identities of Euler are proved in the "Solved Problems" section, and Bernoulli numbers, so important in physics, are discussed in terms of their exponential generating functions. The physicist reader working in statistical physics will appreciate the discussion on Vandermonde determinants. Applications to group theory appear in the discussion on the Young tableaux, preparing the reader for the next chapter.

A more detailed discussion of group theory in combinatorics is given in chapter 4, the last chapter of the book. The author proves the Burnside-Frobenius, the Polya enumeration theorems, and Cayley's theorem in the "Solved Problems" section. Readers without a background in group theory can still read this chapter since the author reviews in detail the basic constructions in group theory, both in the main text and in the "Solved Problems" section. Combinatorial techniques had a large role to play in the problem of the classification of finite simple groups, the eventual classification proof taking over 15,000 journal pages and involving a large collaboration of mathematicians. Combinatorics also made its presence known in the work of Richard Borchers on the "monstrous moonshine" that brought together ideas from mathematical physics and the largest simple group, called the monster simple group.

The author devotes an appendix to graph theory, which is good considering the enormous power of combinatorics to problems in graph theory and computational geometry. Even though the discussion is brief, he does a good job of summarizing the main results, including a graph-theoretic version of Dilworth's theorem. Combinatorial/graph-theoretic considerations are extremely important in network routing design and many of the techniques discussed in this appendix find their way into these kinds of applications. The author asks the reader to prove that Dilworths' theorem, the Ford-Fulkerson theorem, Hall's marriage theorem, Konig's theorem, and Menger's theorem are equivalent. A very useful glossary of the important definitions and concepts used in the book is inserted at the end of the book.