|
Textbook
Applied Combinatorics, 5th EditionNovember 2006, ©2007
 |
The three principle aspects of combinatorical reasoning emphasized in this book are: the systematic analysis of different possibilities, the exploration of the logical structure of a problem (e.g. finding manageable subpieces or first solving the problem with three objects instead of n), and ingenuity. Although important uses of combinatorics in computer science, operations research, and finite probability are mentioned, these applications are often used solely for motivation. Numerical examples involving the same concepts use more interesting settings such as poker probabilities or logical games.
This book is designed for use by students with a wide range of ability and maturity (sophomores through beginning graduate students). The stronger the students, the harder the exercises that can be assigned. The book can be used for one-quarter, two-quarter, or one-semester course depending on how much material is used.
PART ONE: GRAPH THEORY.
Chapter 1. Elements of Graph Theory.
Chapter 2. Covering Circuits and Graph Coloring.
Chapter 3. Trees and Searching.
Chapter 4. Network Algorithms.
PART TWO: ENUMERATION.
Chapter 5. General Counting Methods for Arrangements and Selections.
Chapter 6. Generating Functions.
Chapter 7. Recurrence Relations.
Chapter 8. Inclusion-Exclusion.
PART THREE: ADDITIONAL TOPICS.
Chapter 9. Polya's Enumeration Formula.
Chapter 10. Computer Science Approaches to Enumeration.
Chapter 11. Games with Graphs.
Appendix.
Glossary of Counting.
Graph Theory Terms.
Bibliography.
Solutions to Odd-Numbered Problems.
Index.
- This new fifth edition has new examples, expanded discussions, and additional exercises throughout the text.
- The game of Mastermind that appeared at the beginning of the first edition has been brought back to this edition
- New material added including: chromatic polynomials, the transportation problem, and NP-completeness.
- The chapter on formal languages and finite-state machines from the second edition is back in abbreviated form.
- Theory is always first motivated by examples, and proofs are given only when their reasoning is needed to solve applied problems. Elsewhere, results are stated without proof, such as the form of solutions to various recurrence relations, and then applied in problem solving.
- This new fifth edition has new examples, expanded discussions, and additional exercises throughout the text.
- The game of Mastermind that appeared at the beginning of the first edition has been brought back to this edition.
- The chapter on formal languages and finite-state machines from the second edition is back in abbreviated form.
- New material added including: chromatic polynomials, the transportation problem, and NP-completeness.
