Combinatorics

Content: Cover
 Half Title
 Discrete Mathematics and Its Application
 Title
 Copyright
 Dedication
 Contents
 Preface to the Second Edition
 Introduction
 Part I Counting
 Chapter 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 Paths1.15 Proofs of the Sum Rule and the Product Rule
 Summary
 Exercises
 Chapter 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 Theory2.15 Stirling Numbers and Polynomials
 2.16 Solving Recursions with Constant Coefficients
 Summary
 Exercises
 Chapter 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 Coloring3.17 Spanning Trees
 3.18 the Matrix-tree Theorem
 3.19 Eulerian Tours
 Summary
 Exercises
 Chapter 4 Inclusion-exclusion, Involutions, and Möbius 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 F Function
 4.5 Derangements
 4.6 Involutions
 4.7 Involutions Related to Inclusion-exclusion
 4.8 Generalized Inclusion-exclusion Formulas
 4.9 Möbius Inversion in Number Theory
 4.10 Partially Ordered Sets
 4.11 Möbius Inversion for Posets
 4.12 Product Posets
 Summary
 Exercises Chapter 5 Generating Functions5.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