Preface
1 What 'Is Combinatorics?
1.1 Example: Perfect Covers of Chessboards
1.2 Example: Magic Squares
1.3 Example: The Four-Color Problem
1.4 Example: The Problem of the 36 OfFicers
1.5 ,Example: Shortest-Route Problem
1.6 Example: Mutually Overlapping Circles
1.7 Example: The Game of Nim
1.8 Exercises
2 Permutations and Combinations
2.1 Four Basic Counting Principles
2.2 Permutations of Sets
2.3 Combinations (Subsets) of Sets
2.4 Permutations of Multisets Preface
1 What 'Is Combinatorics?
1.1 Example: Perfect Covers of Chessboards
1.2 Example: Magic Squares
1.3 Example: The Four-Color Problem
1.4 Example: The Problem of the 36 OfFicers
1.5 ,Example: Shortest-Route Problem
1.6 Example: Mutually Overlapping Circles
1.7 Example: The Game of Nim
1.8 Exercises
2 Permutations and Combinations
2.1 Four Basic Counting Principles
2.2 Permutations of Sets
2.3 Combinations (Subsets) of Sets
2.4 Permutations of Multisets
2.5 Combinations of Multisets
2.6 Finite Probability
2.7 Exercises
3 The Pigeonhole Principle
3.1 Pigeonhole Principle: Simple Form
3.2 Pigeonhole Principle: Strong Form
3.3 A Theorem of Ramsey
3.4 Exercises
4 Generating Permutations and Combinations
4.1 Generating Permutations
4.2 Inversions in Permutations
4.3 Generating Combinations
4.4 Generating r-Subsets
4.5 Partial Orders and Equivalence Relations
4.6 Exercises
5 The Binomial Coefficients
5.1 Pascal's Triangle
5.2 The Binomial Theorem
5.3 Unimodality of Binomial Coefficients
5.4 The Multinomial Theorem
5.5 Newton's Binomial Theorem
5.6 More on Partially Ordered Sets
5.7 Exercises
6 The Inclusion-Exclusion Principle and Applications
6.1 The Inclusion-Exclusion Principle
6.2 Combinations with Repetition
6.3 Derangements
6.4 Permutations with Forbidden Positions
6.5 Another Forbidden Position Problem
6.6 M6bius Inversion
6.7 Exercises
7 Recurrence Relations and Generating Functions
7.1 Some Number Sequences
7.2 Generating Functions
7.3 Exponential Generating Functions
7.4 Solving Linear Homogeneous Recurrence Relations ..
7.5 Nonhomogeneous Recurrence Relations
7.6 A Geometry Example
7.7 Exercises
8 Special Counting Sequences
8.1 Catalan Numbers
8.2 Difference Sequences and Stirling Numbers
8.3 Partition Numbers
8.4 A Geometric Problem
8.5 Lattice Paths and Schr6der Numbers
8.6 Exercises
9 Systems of Distinct Representatives
10 Combinatorial Designs
11 Introduction to Graph Theory
12 More ONgraph Theory
13 Digraphs and Networks
14 Polya Counting
Answers and Hints to Exercises
Bibliography
Index