Foundations of Combinatorics with Applications

by Edward A. Bender, S. Gill Williamson

Overview

This introduction to combinatorics, the foundation of the interaction between computer science and mathematics, is suitable for upper-level undergraduates and graduate students in engineering, science, and mathematics.
The four-part treatment begins with a section on counting and listing that covers basic counting, functions, decision trees, and sieving methods. The following section addresses fundamental concepts in graph theory and a sampler of graph topics. The third part examines a variety of applications relevant to computer science and mathematics, including induction and recursion, sorting theory, and rooted plane trees. The final section, on generating functions, offers students a powerful tool for studying counting problems. Numerous exercises appear throughout the text, along with notes and references. The text concludes with solutions to odd-numbered exercises and to all appendix exercises.

Product Details

ISBN-13:	9780486446035
Publisher:	Dover Publications
Publication date:	02/06/2006
Series:	Dover Books on Mathematics
Pages:	480
Product dimensions:	6.14(w) x 9.21(h) x (d)

Table of Contents

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