Applied Combinatorics (Hardcover, 2 ed)

What Is Combinatorics?

The Three Problems of Combinatorics

The History and Applications of Combinatorics

THE BASIC TOOLS OF COMBINATORICS

Basic Counting Rules

The Product Rule

The Sum Rule

Permutations

Complexity of Computation

r-Permutations

Subsets

r-Combinations

Probability

Sampling with Replacement

Occupancy Problems

Multinomial Coefficients

Complete Digest by Enzymes

Permutations with Classes of Indistinguishable Objects Revisited

The Binomial Expansion

Power in Simple Games

Generating Permutations and Combinations

Inversion Distance between Permutations and the Study of Mutations

Good Algorithms

Pigeonhole Principle and Its Generalizations

Introduction to Graph Theory

Fundamental Concepts

Connectedness

Graph Coloring and Its Applications

Chromatic Polynomials

Trees

Applications of Rooted Trees to Searching, Sorting, and Phylogeny Reconstruction

Representing a Graph in the Computer

Ramsey Numbers Revisited

Relations

Relations

Order Relations and Their Variants

Linear Extensions of Partial Orders

Lattices and Boolean Algebras

THE COUNTING PROBLEM

Generating Functions and Their Applications

Examples of Generating Functions

Operating on Generating Functions

Applications to Counting

The Binomial Theorem

Exponential Generating Functions and Generating Functions for Permutations

Probability Generating Functions

The Coleman and Banzhaf Power Indices

Recurrence Relations

Some Examples

The Method of Characteristic Roots

Solving Recurrences Using Generating Functions

Some Recurrences Involving Convolutions

The Principle of Inclusion and Exclusion

The Principle and Some of Its Applications

The Number of Objects Having Exactly m Properties

The Polya Theory of Counting

Equivalence Relations

Permutation Groups

Burnside’s Lemma

Distinct Colorings

The Cycle Index

Polya’s Theorem

THE EXISTENCE PROBLEM

Combinatorial Designs

Block Designs

Latin Squares

Finite Fields and Complete Orthogonal Families of Latin Squares

Balanced Incomplete Block Designs

Finite Projective Planes

Coding Theory

Information Transmission

Encoding and Decoding

Error-Correcting Codes

Linear Codes

The Use of Block Designs to Find Error-Correcting Codes

Existence Problems in Graph Theory

Depth-First Search: A Test for Connectedness

The One-Way Street Problem

Eulerian Chains and Paths

Applications of Eulerian Chains and Paths

Hamiltonian Chains and Paths

Applications of Hamiltonian Chains and Paths

COMBINATORIAL OPTIMIZATION

Matching and Covering

Some Matching Problems

Some Existence Results: Bipartite Matching and Systems of Distinct Representatives

The Existence of Perfect Matchings for Arbitrary Graphs

Maximum Matchings and Minimum Coverings

Finding a Maximum Matching

Matching as Many Elements of X as Possible

Maximum-Weight Matching

Stable Matchings

Optimization Problems for Graphs and Networks

Minimum Spanning Trees

The Shortest Route Problem

Network Flows

Minimum-Cost Flow Problems

Appendix: Answers to Selected Exercises

Author Index

Subject Index

References appear at the end of each chapter.