×

A first course in discrete mathematics. (English) Zbl 0960.00005

Springer Undergraduate Mathematics Series. London: Springer. viii, 200 p. (2001).
In the Preface the author explains that this textbook “could be used at undergraduate level, probably in the second year of an English undergraduate mathematics course” and that it is written more for the student of mathematics than of computer science. This text would be appropriate at the same level for a one- or two-semester course at most North American colleges and universities, although it is not sufficiently challenging for a combinatorics course for more advanced undergraduate mathematics majors. Following is a list of the chapter titles with a summary of the contents of each chapter.
1. Counting and Binomial Coefficients. Basic notions of combinations and permutations up through selections with repetitions.
2. Recurrence. The auxiliary (or characteristic) equation of a recurrence, ordinary generating functions, and applications to derangements, two sorting algorithms, and the Catalan numbers.
3. Introduction to Graphs. Basic terminology, trees and tree algorithms, bipartite graphs, Euler’s formula for plane graphs, Kuratowski’s forbidden subgraph theorem (without proof), the Platonic graphs, and Buckyballs.
4. Traveling Round a Graph. Some properties of Hamiltonian graphs, the traveling salesman problem, Gray codes (applied to the \(n\)-cube), Eulerian graphs, and all these notions applied to directed graphs.
5. Partitions and Colorings. More enumeration, Stirling numbers of the second kind, enumeration of functions, and vertex- and edge-colorings of graphs.
6. The Inclusion-Exclusion Principle. Applications of this principle to counting derangements, surjections, and labeled trees, the ménage problem. The Euler \(\varphi\)-function appears in an exercise.
7. Latin Squares and Hall’s Theorem. Orthogonality, magic squares, SDR’s, and affine planes.
8. Schedules and 1-Factorizations.
9. Introduction to Designs. BIBD’s including Steiner triple systems, resolvable designs, finite projective planes, Hadamard matrices and designs, difference methods, and error-correcting codes.
Appendix. Arithmetic modulo \(n\). Squares and non-squares in \(\mathbb{Z}_p\).
Solutions. The answer or a suggested method (or both) is included for every exercise.
Further Reading. Bibliography. Index.
Each chapter concludes with many exercises, ranging from routine to presentation of additional notions. The thrust of this book is clearly more to lead the student into thinking combinatorially and becoming acquainted with standard combinatorial mathematics than to present the student with a compendium of theorems with elegant proofs. Toward this goal this text is eminently successful. However, if the instructor wishes to introduce the student to the rigors of theorem-proving with proper notation, then this text is not appropriate, although it may be a good companion to such a text.

MSC:

00A05 Mathematics in general
05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
PDFBibTeX XMLCite