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

MAA Review
Table of Contents

[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