**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 Pólya Theory of Counting**

Equivalence Relations

Permutation Groups

Burnside’s Lemma

Distinct Colorings

The Cycle Index

Pólya’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.*