 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 ngon. 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 oddnumbered problems, even proofs! The exercises are interesting and wellthought 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 RPTrees  
Exercises  
9.3  Unlabeled Full Binary RPTrees  
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  NPComplete 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  