- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants
- News
- About MAA

Foundations of Combinatorics with Applications covers the classic combinatorial topics: counting and listing, graphs, recursion, and generating functions. But in each of these areas, the text brings in new topics and methods that have been developed in this generation. For example, in the section on generating functions, they introduce the rules of sum and product that allow us to “go directly from a combinatorial construction to a generating function expression” without getting bogged down in possibly messy algebraic manipulation. In the graphs section, Bender and Williamson explain how a considerable body of research has built up around planar graphs and they go on to explain some research highlights, like finding algorithms to figure out if a graph is planar. This discussion about research in a textbook connects readers to the idea that mathematics is always new, exciting, and expanding and in a sense, the authors are inviting readers to enter into the professional research community.
The text also focuses on the “interaction between computer science and mathematics.” While other combinatorics texts may only use computer science as motivation for problems, this text dives more deeply into the connection. For example, the text includes brief programs and examples of code, calculations on limits of speed, cost, and storage, and a whole chapter of sorting algorithms.
While they bring in new, fresh themes, Bender and Williamson do a fine job with the classic topics too. One of my favorite parts of combinatorics is the equivalent ways of looking at the same idea. They introduce the Catalan numbers and then explain a few different ways to interpret them: an election between two candidates, a computer science stack, and the triangulation of an n-gon. Bender and Williamson also introduce and solve a problem (like how many ways there are to seat n people on Ferris wheel with one person in each seat) using one method and then later solve this same problem using more and more efficient methods. I like the section on recursions because the authors focus not just on solving recursions, but they also explain methods of how to think recursively.
Bender and Williamson’s text is rigorous. They assert that the text could be used in a “challenging lower level course”, in an upper division course, or in a beginning graduate course. I would not recommend using this text in a lower level course, even a challenging one. Every mathematics textbook author must strike a balance between theorems, proofs, and examples. This text leans toward introducing theorems and then proving them. While there are many examples in the text, especially in the counting and listing section, there are sections sorely lacking examples (like the graphs section) and sometimes, the examples are not really examples, in that they are not problems for the reader to solve. I don’t think the text is appropriate for a student’s first course in combinatorics because there are not enough concrete examples for the student to gain a steady footing in the subject. Upper division and graduate students that are already familiar with combinatorics would be able to use this book.
The homework exercises in the text are great, thought I wish some of these exercises were fleshed out examples included in the main part of the text. Bender and Williamson do provide detailed answers to odd-numbered problems, even proofs! The exercises are interesting and well-thought out. For example, they have an exercise on recursions where proofs are given and the reader must figure out what is wrong with the proof.
Overall, the text is refreshing in its combination of classic and new topics and provides a rigorous investigation into the interaction between combinatorics and computer science.
Kara Shane Colley studied physics at Dartmouth College, math at the University of Albany, and math education at Teachers College. She has taught math and physics to middle school, high school, and community college students in the U.S., the Marshall Islands, and England. Currently, she is volunteering aboard the Halfmoon, a replica of Henry Hudson’s 17th century ship, docked in Albany, NY. Contact her at karashanecolley@yahoo.com.
|
Preface
|
||||||||
| Part I | Counting and Listing | |||||||
| Preliminary Reading | ||||||||
| 1 | Basic Counting | |||||||
| Introduction | ||||||||
| 1.1 | Lists with Repetitions Allowed | |||||||
| Using the Rules of Sum and Product | ||||||||
| Exercises | ||||||||
| 1.2 | Lists with Repetitions Forbidden | |||||||
| Exercises | ||||||||
| 1.3 | Sets | |||||||
| Error Correcting Codes | ||||||||
| Exercises | ||||||||
| 1.4 | Recursions | |||||||
| Exercises | ||||||||
| 1.5 | Multisets | |||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| 2 | Functions | |||||||
| Introduction | ||||||||
| 2.1 | Some Basic Terminology | |||||||
| Terminology for Sets | ||||||||
| What are Functions? | ||||||||
| Exercises | ||||||||
| 2.2 | Permutations | |||||||
| Exercises | ||||||||
| 2.3 | Other Combinatorial Aspects of Functions | |||||||
| Monotonic Functions and Unordered Lists | ||||||||
| Image and Coimage | ||||||||
| The Pigeonhole Principle | ||||||||
| Exercises | ||||||||
| 2.4 | Boolean Functions | |||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| 3 | Decision Trees | |||||||
| Introduction | ||||||||
| 3.1 | Basic Concepts of Decision Trees | |||||||
| Exercises | ||||||||
| 3.2 | Ranking and Unranking | |||||||
| Calculating RANK | ||||||||
| Calculating UNRANK | ||||||||
| Gray Codes | ||||||||
| Exercises | ||||||||
| 3.3 | Backtracking | |||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| 4 | Sieving Methods | |||||||
| Introduction | ||||||||
| Structures Lacking Things | ||||||||
| Structures with Symmetries | ||||||||
| 4.1 | The Principle of Inclusion and Exclusion | |||||||
| Exercises | ||||||||
| Bonferroni's Inequalities | ||||||||
| Partially Ordered Sets | ||||||||
| Exercises | ||||||||
| 4.2 | Listing Structures with Symmetries | |||||||
| Exercises | ||||||||
| 4.3 | Counting Structures with Symmetries | |||||||
| Proofs | ||||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| Part II | Graphs | |||||||
| 5 | Basic Concepts in Graph Theory | |||||||
| Introduction | ||||||||
| 5.1 | What is a Graph? | |||||||
| Exercises | ||||||||
| 5.2 | Equivalence Relations and Unlabeled Graphs | |||||||
| Exercises | ||||||||
| 5.3 | Paths and Subgraphs | |||||||
| Exercises | ||||||||
| 5.4 | Trees | |||||||
| Exercises | ||||||||
| 5.5 | Directed Graphs (Digraphs) | |||||||
| Exercises | ||||||||
| 5.6 | Computer Representations of Graphs | |||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| 6 | A Sampler of Graph Topics | |||||||
| Introduction | ||||||||
| 6.1 | Spanning Trees | |||||||
| Minimum Weight Spanning Trees | ||||||||
| Lineal Spanning Trees | ||||||||
| Exercises | ||||||||
| 6.2 | Coloring Graphs | |||||||
| Exercises | ||||||||
| 6.3 | Planar Graphs | |||||||
| Euler's Relation | ||||||||
| Exercises | ||||||||
| The Five Color Theorem | ||||||||
| Exercises | ||||||||
| Algorithmic Questions | ||||||||
| Exercises | ||||||||
| 6.4 | Flows in Networks | |||||||
| The Concepts | ||||||||
| An Algorithm for Constructing a Maximum Flow | ||||||||
| Exercises | ||||||||
| Cut Partitions and Cut Sets | ||||||||
| Exercises | ||||||||
| 6.5 | Probability and Simple Graps | |||||||
| Exercises | ||||||||
| 6.6 | Finite State Machines | |||||||
| Turing Machines | ||||||||
| Finite State Machines and Digraphs | ||||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| Part III | Recursion | |||||||
| 7 | Induction and Recursion | |||||||
| Introduction | ||||||||
| 7.1 | Inductive Proofs and Recursive Equations | |||||||
| Exercises | ||||||||
| 7.2 | Thinking Recursively | |||||||
| Exercises | ||||||||
| 7.3 | Recursive Algorithms | |||||||
| Obtaining Information: Merge Sorting | ||||||||
| Local Descriptions | ||||||||
| Computer Implementation | ||||||||
| Exercises | ||||||||
| 7.4 | Divide and Conquer | |||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| 8 | Sorting Theory | |||||||
| Introduction | ||||||||
| 8.1 | Limits on Speed | |||||||
| Motivation and Proof of the Theorem | ||||||||
| Exercises | ||||||||
| 8.2 | Software Sorts | |||||||
| Binary Insertion Sort | ||||||||
| Bucket Sort | ||||||||
| Merge Sorts | ||||||||
| Quicksort | ||||||||
| Heapsort | ||||||||
| Exercises | ||||||||
| 8.3 | Sorting Networks | |||||||
| 8.3.1 | Speed and Cost | |||||||
| Parallelism | ||||||||
| How Fast Can a Network Be? | ||||||||
| How Cheap Can a Network Be? | ||||||||
| Exercises | ||||||||
| 8.3.2 | Proving That a Network Sorts | |||||||
| The Batcher Sort | ||||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| 9 | Rooted Plane Trees | |||||||
| Introduction | ||||||||
| 9.1 | Traversing Trees | |||||||
| Depth First Traversals | ||||||||
| Exercises | ||||||||
| 9.2 | Grammars and RP-Trees | |||||||
| Exercises | ||||||||
| 9.3 | Unlabeled Full Binary RP-Trees | |||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| Part IV | Generating Functions | |||||||
| 10 | Ordinary Generating Functions | |||||||
| Introduction | ||||||||
| 10.1 | What are Generating Functions? | |||||||
| Exercises | ||||||||
| 10.2 | Solving a Single Recursion | |||||||
| Exercises | ||||||||
| 10.3 | Manipulating Generating Functions | |||||||
| Obtaining Recursions | ||||||||
| Derivatives, Averages and Probability | ||||||||
| Exercises | ||||||||
| 10.4 | The Rules of Sum and Product | |||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| 11 | Generating Function Topics | |||||||
| Introduction | ||||||||
| 11.1 | Systems of Recursions | |||||||
| Exercises | ||||||||
| 11.2 | Exponential Generating Functions | |||||||
| The Exponential Formula | ||||||||
| Exercises | ||||||||
| 11.3 | Symmetries and Pólya's Theorem | |||||||
| Exercises | ||||||||
| 11.4 | Asymptotic Estimates | |||||||
| Recursions | ||||||||
| Sums of Positive Terms | ||||||||
| Generating Functions | ||||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| Appendix A | Induction | |||||||
| Exercises | ||||||||
| Appendix B | Rates of Growth and Analysis of Algorithms | |||||||
| B.1 | The Basic Functions | |||||||
| Exercises | ||||||||
| B.2 | Doing Arithmetic | |||||||
| B.3 | NP-Complete Problems | |||||||
| Exercises | ||||||||
| Notes and References | ||||||||
| Appendix C | Basic Probability | |||||||
| C.1 | Probability Spaces and Random Variables | |||||||
| C.2 | Expectation and Variance | |||||||
| Appendix D | Partial Fractions | |||||||
| Theory | ||||||||
| Computations | ||||||||
| Solutions to Odd Exercises and Most Appendix Exercises | ||||||||
| Index | ||||||||