You are here

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