Preface to the Second Edition
Introduction
I Counting
1 Basic Counting
1.1 The Product Rule
1.2 The Sum Rule
1.3 Counting Words and Permutations
1.4 Counting Subsets
1.5 Counting Anagrams
1.6 Counting Rules for Set Operations
1.7 Probability
1.8 Lotteries and Card Games
1.9 Conditional Probability and Independence
1.10 Counting Functions
1.11 Cardinality and the Bijection Rule
1.12 Counting Multisets and Compositions
1.13 Counting Balls in Boxes
1.14 Counting Lattice Paths
1.15 Proofs of the Sum Rule and the Product Rule
Summary
Exercises
2 Combinatorial Identities and Recursions
2.1 Initial Examples of Combinatorial Proofs
2.2 The Geometric Series Formula
2.3 The Binomial Theorem
2.4 The Multinomial Theorem
2.5 More Binomial Coefficient Identities
2.6 Sums of Powers of Integers
2.7 Recursions
2.8 Recursions for Multisets and Anagrams
2.9 Recursions for Lattice Paths
2.10 Catalan Recursions
2.11 Integer Partitions
2.12 Set Partitions
2.13 Surjections, Balls in Boxes, and Equivalence Relations
2.14 Stirling Numbers and Rook Theory
2.15 Stirling Numbers and Polynomials
2.16 Solving Recursions with Constant Coefficients
Summary
Exercises
3 Counting Problems in Graph Theory
3.1 Graphs and Digraphs
3.2 Walks and Matrices
3.3 Directed Acyclic Graphs and Nilpotent Matrices
3.4 Vertex Degrees
3.5 Functional Digraphs
3.6 Cycle Structure of Permutations
3.7 Counting Rooted Trees
3.8 Connectedness and Components
3.9 Forests
3.10 Trees
3.11 Counting Trees
3.12 Pruning Maps
3.13 Bipartite Graphs
3.14 Matchings and Vertex Covers
3.15 Two Matching Theorems
3.16 Graph Coloring
3.17 Spanning Trees
3.18 The Matrix-Tree Theorem
3.19 Eulerian Tours
Summary
Exercises
4 Inclusion-Exclusion, Involutions, and M6bius Inversion
4.1 The Inclusion-Exclusion Formula
4.2 Examples of the Inclusion-Exclusion Formula
4.3 Surjections and Stirling Numbers
4.4 Euler's φ Function
4.5 Derangements
4.6 Involutions
4.7 Involutions Related to Inclusion-Exclusion
4.8 Generalized Inclusion-Exclusion Formulas
4.9 MSbius Inversion in Number Theory
4.10 Partially Ordered Sets
4.11 M6bius Inversion for Posets
4.12 Product Posers
Summary
Exercises
5 Generating Functions
5.1 What is a Generating Function?
5.2 Convergence of Power Series
5.3 Examples of Analytic Power Series
5.4 Operations on Power Series
5.5 Solving Recursions with Generating Functions
5.6 Evaluating Summations with Generating Functions
5.7 Generating Function for Derangements
5.8 Counting Rules for Weighted Sets
5.9 Examples Of the Product Rule for Weighted Sets
5.10 Generating Functions for Trees
5.11 Tree Bijections
5.12 Exponential Generating Functions
5.13 Stirling Numbers of the First Kind
5.14 Stirling Numbers of the Second Kind
5.15 Generating Functions for Integer Partitions
5.16 Partition Bijections
5.17 Euler's Pentagonal Number Theorem
Summary
Exercises
6 Ranking, Unranking, and Successor Algorithms
6.1 Introduction to Ranking and Successor Algorithms
6.2 The Bijective Sum Rule
6.3 The Bijective Product Rule for Two Sets
6.4 The Bijective Product Rule
6.5 Ranking Words
6.6 Ranking Permutations
6.7 Ranking Subsets
6.8 Ranking Anagrams
6.9 Ranking Integer Partitions
6.10 Ranking Set Partitions
6.11 Ranking Trees
6.12 The Successor Sum Rule
6.13 Successor Algorithms for Anagrams
6.14 The Successor Product Rule
6.15 Successor Algorithms for Set Partitions
6.16 Suc