# Foundations of Combinatorics with Applications

###### Edward A. Bender and S. Gill Williamson
Publisher:
Dover Publications
Publication Date:
2006
Number of Pages:
468
Format:
Paperback
Price:
22.95
ISBN:
0486446034
Category:
Textbook
[Reviewed by
Kara Shane Colley
, on
08/1/2006
]

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