| |
| |
| Preface | |
| |
| |
| |
| An Introduction to Enumeration | |
| |
| |
| |
| Elementary Counting Principles | |
| |
| |
| What Is Combinatorics? | |
| |
| |
| The Sum Principle | |
| |
| |
| The Product Principle | |
| |
| |
| Ordered Paris | |
| |
| |
| Cartesian Product of Sets | |
| |
| |
| The General Form of the Product Principle | |
| |
| |
| Lists with Distinct Elements | |
| |
| |
| Lists with Repeats Allowed | |
| |
| |
| Stirling's Approximation for n! | |
| |
| |
| Exercises | |
| |
| |
| |
| Functions and the Pigeonhole Principle | |
| |
| |
| Functions | |
| |
| |
| Relations | |
| |
| |
| Definition of Function | |
| |
| |
| The Number of Functions | |
| |
| |
| One-to-One Functions | |
| |
| |
| Onto Functions and Bijections | |
| |
| |
| The Extended Pigeonhole Principle | |
| |
| |
| Ramsey Numbers | |
| |
| |
| *Using Functions to Describe Ramsey Numbers | |
| |
| |
| Exercises | |
| |
| |
| |
| Subsets | |
| |
| |
| The Number of Subsets of a Set | |
| |
| |
| Binomial Coefficients | |
| |
| |
| [kappa]-Element Subsets | |
| |
| |
| Labelings with Two Labels | |
| |
| |
| Pascal's Triangle | |
| |
| |
| How Fast Does the Number of Subsets Grow? | |
| |
| |
| Recursion and Iteration | |
| |
| |
| Exercises | |
| |
| |
| |
| Using Binomial Coefficients | |
| |
| |
| The Binomial Theorem | |
| |
| |
| Multinomial Coefficients | |
| |
| |
| The Multinomial Theorem | |
| |
| |
| Multinomial Coefficients from Binomial Coefficients | |
| |
| |
| Lattice Paths | |
| |
| |
| Exercises | |
| |
| |
| |
| Mathematical Induction | |
| |
| |
| The Principle of Induction | |
| |
| |
| Proving That Formulas Work | |
| |
| |
| Informal Induction Proofs | |
| |
| |
| Inductive Definition | |
| |
| |
| The General Sum Principle | |
| |
| |
| An Application to Computing | |
| |
| |
| Proving That a Recurrence Works | |
| |
| |
| A Sample of the Strong Form of Mathematical Induction | |
| |
| |
| Double Induction | |
| |
| |
| Ramsey Numbers | |
| |
| |
| Exercises | |
| |
| |
| Suggested Reading for Chapter 1 | |
| |
| |
| |
| Equivalence Relations, Partitions, and Multisets | |
| |
| |
| |
| Equivalence Relations | |
| |
| |
| The Idea of Equivalence | |
| |
| |
| Equivalence Relations | |
| |
| |
| Circular Arrangements | |
| |
| |
| Equivalence Classes | |
| |
| |
| Counting Equivalence Classes | |
| |
| |
| The Inverse Image Relation | |
| |
| |
| The Number of Partitions with Specified Class Sizes | |
| |
| |
| Exercises | |
| |
| |
| |
| Distributions and Multisets | |
| |
| |
| The Idea of a Distribution | |
| |
| |
| Ordered Distributions | |
| |
| |
| Distributing Identical Objects to Distinct Recipients | |
| |
| |
| Ordered Compositions | |
| |
| |
| Multisets | |
| |
| |
| Broken Permutations of a Set | |
| |
| |
| Exercises | |
| |
| |
| |
| Partitions and Stirling Numbers | |
| |
| |
| Partitions of an m-Element Set into n Classes | |
| |
| |
| Stirling's Triangle of the Second Kind | |
| |
| |
| The Inverse Image Partition of a Function | |
| |
| |
| Onto Functions and Stirling Numbers | |
| |
| |
| Stirling Numbers of the First Kind | |
| |
| |
| Stirling Numbers of the Second Kind as Polynomial Coefficients | |
| |
| |
| Stirling's Triangle of the First Kind | |
| |
| |
| The Total Number of Partitions of a Set | |
| |
| |
| Exercises | |
| |
| |
| |
| Partitions of Integers | |
| |
| |
| Distributing Identical Objects to Identical Recipients | |
| |
| |
| Type Vector of a Partition and Decreasing Lists | |
| |
| |
| The Number of Partitions of m into n Parts | |
| |
| |
| Ferrers Diagrams | |
| |
| |
| Conjugate Partitions | |
| |
| |
| The Total Number of Partitions of m | |
| |
| |
| Exercises | |
| |
| |
| Suggested Reading for Chapter 2 | |
| |
| |
| |
| Algebraic Counting Techniques | |
| |
| |
| |
| The Principle of Inclusion and Exclusion | |
| |
| |
| The Size of a Union of Three Overlapping Sets | |
| |
| |
| The Number of Onto Functions | |
| |
| |
| Counting Arrangements with or without Certain Properties | |
| |
| |
| The Basic Counting Functions N[greater than or equal] and N= | |
| |
| |
| The Principle of Inclusion and Exclusion | |
| |
| |
| Onto Functions and Stirling Numbers | |
| |
| |
| Examples of Using the Principle of Inclusion and Exclusion | |
| |
| |
| Derangements | |
| |
| |
| Level Sums and Inclusion-Exclusion Counting | |
| |
| |
| Examples of Level Sum Inclusion and Exclusion | |
| |
| |
| Exercises | |
| |
| |
| |
| The Concept of a Generating Function | |
| |
| |
| Symbolic Series | |
| |
| |
| Power Series | |
| |
| |
| What Is a Generating Function? | |
| |
| |
| The Product Principle for Generating Functions | |
| |
| |
| The Generating Function for Multisets | |
| |
| |
| Polynomial Generating Functions | |
| |
| |
| Extending the Definition of Binomial Coefficients | |
| |
| |
| The Extended Binomial Theorem | |
| |
| |
| Exercises | |
| |
| |
| |
| Applications to Partitions and Inclusion-Exclusion | |
| |
| |
| Polya's Change-Making Example | |
| |
| |
| Systems of Linear Recurrences from Products of Geometric Series | |
| |
| |
| Generating Functions for Integer Partitions | |
| |
| |
| Generating Functions Sometimes Replace Inclusion-Exclusion | |
| |
| |
| Generating Functions and Inclusion-Exclusion on Level Sums | |
| |
| |
| Exercises | |
| |
| |
| |
| Recurrence Relations and Generating Functions | |
| |
| |
| The Idea of a Recurrence Relation | |
| |
| |
| How Generating Functions Are Relevant | |
| |
| |
| Second-Order Linear Recurrence Relations | |
| |
| |
| The Original Fibonacci Problem | |
| |
| |
| General Techniques | |
| |
| |
| Exercises | |
| |
| |
| |
| Exponential Generating Functions | |
| |
| |
| Indicator Functions | |
| |
| |
| Exponential Generating Functions | |
| |
| |
| Products of Exponential Generating Functions | |
| |
| |
| The Exponential Generating Function for Onto Functions | |
| |
| |
| The Product Principle for Exponential Generating Functions | |
| |
| |
| Putting Lists Together and Preserving Order | |
| |
| |
| Exponential Generating Functions for Words | |
| |
| |
| Solving Recurrence Relations with Other Generating Functions | |
| |
| |
| Using Calculus with Exponential Generating Functions | |
| |
| |
| Exercises | |
| |
| |
| Suggested Reading for Chapter 3 | |
| |
| |
| |
| Graph Theory | |
| |
| |
| |
| Eulerian Walks and the Idea of Graphs | |
| |
| |
| The Concept of a Graph | |
| |
| |
| Multigraphs and the Konigsberg Bridge Problem | |
| |
| |
| Walks, Paths, and Connectivity | |
| |
| |
| Eulerian Graphs | |
| |
| |
| Exercises | |
| |
| |
| |
| Trees | |
| |
| |
| The Chemical Origins of Trees | |
| |
| |
| Basic Facts about Trees | |
| |
| |
| Spanning Trees | |
| |
| |
| The Number of Trees | |
| |
| |
| Exercises | |
| |
| |
| |
| Shortest Paths and Search Trees | |
| |
| |
| Rooted Trees | |
| |
| |
| Breadth-First Search Trees | |
| |
| |
| Shortest Path Spanning Trees | |
| |
| |
| Bridges | |
| |
| |
| Depth-First Search | |
| |
| |
| Depth-First Numbering | |
| |
| |
| Finding Bridges | |
| |
| |
| An Efficient Bridge-Finding Algorithm for Computers | |
| |
| |
| Backtracking | |
| |
| |
| Decision Graphs | |
| |
| |
| Exercises | |
| |
| |
| |
| Isomorphism and Planarity | |
| |
| |
| The Concept of Isomorphism | |
| |
| |
| Checking Whether Two Graphs Are Isomorphic | |
| |
| |
| Planarity | |
| |
| |
| Euler's Formula | |
| |
| |
| An Inequality to Check for Nonplanarity | |
| |
| |
| Exercises | |
| |
| |
| |
| Digraphs | |
| |
| |
| Directed Graphs | |
| |
| |
| Walks and Connectivity | |
| |
| |
| Tournament Digraphs | |
| |
| |
| Hamiltonian Paths | |
| |
| |
| Transitive Closure | |
| |
| |
| Reachability | |
| |
| |
| Modifying Breadth-First Search for Strict Reachability | |
| |
| |
| Orientable Graphs | |
| |
| |
| Graphs without Bridges Are Orientable | |
| |
| |
| Exercises | |
| |
| |
| |
| Coloring | |
| |
| |
| The Four-Color Theorem | |
| |
| |
| Chromatic Number | |
| |
| |
| Maps and Duals | |
| |
| |
| The Five-Color Theorem | |
| |
| |
| Kempe's Attempted Proof | |
| |
| |
| Using Backtracking to Find a Coloring | |
| |
| |
| Exercises | |
| |
| |
| |
| Graphs and Matrices | |
| |
| |
| Adjacency Matrix of a Graph | |
| |
| |
| Matrix Powers and Walks | |
| |
| |
| Connectivity and Transitive Closure | |
| |
| |
| Boolean Operations | |
| |
| |
| The Matrix-Tree Theorem | |
| |
| |
| The Number of Eulerian Walks in a Digraph | |
| |
| |
| Exercises | |
| |
| |
| Suggested Reading for Chapter 4 | |
| |
| |
| |
| Matching and Optimization | |
| |
| |
| |
| Matching Theory | |
| |
| |
| The Idea of Matching | |
| |
| |
| Making a Bigger Matching | |
| |
| |
| A Procedure for Finding Alternating Paths in Bipartite Graphs | |
| |
| |
| Constructing Bigger Matchings | |
| |
| |
| Testing for Maximum-Sized Matchings by Means of Vertex Covers | |
| |
| |
| Hall's "Marriage" Theorem | |
| |
| |
| Term Rank and Line Covers of Matrices | |
| |
| |
| Permutation Matrices and the Birkhoff-von Neumann Theorem | |
| |
| |
| Finding Alternating Paths in Nonbipartite Graphs | |
| |
| |
| Exercises | |
| |
| |
| |
| The Greedy Algorithm | |
| |
| |
| The SDR Problem with Representatives That Cost Money | |
| |
| |
| The Greedy Method | |
| |
| |
| The Greedy Algorithm | |
| |
| |
| Matroids Make the Greedy Algorithm Work | |
| |
| |
| How Much Time Does the Algorithm Take? | |
| |
| |
| The Greedy Algorithm and Minimum-Cost Independent Sets | |
| |
| |
| The Forest Matroid of a Graph | |
| |
| |
| Minimum-Cost Spanning Trees | |
| |
| |
| Exercises | |
| |
| |
| |
| Network Flows | |
| |
| |
| Transportation Networks | |
| |
| |
| The Concept of Flow | |
| |
| |
| Cuts in Networks | |
| |
| |
| Flow-Augmenting Paths | |
| |
| |
| The Labeling Algorithm for Finding Flow-Augmenting Paths | |
| |
| |
| The Max-Flow Min-Cut Theorem | |
| |
| |
| More Efficient Algorithms | |
| |
| |
| Exercises | |
| |
| |
| |
| Flows, Connectivity, and Matching | |
| |
| |
| Connectivity and Menger's Theorem | |
| |
| |
| Flows, Matchings, and Systems of Distinct Representatives | |
| |
| |
| Minimum-Cost SDRs | |
| |
| |
| Minimum-Cost Matchings and Flows with Edge Costs | |
| |
| |
| The Potential Algorithm for Finding Minimum-Cost Paths | |
| |
| |
| Finding a Maximum Flow of Minimum Cost | |
| |
| |
| Exercises | |
| |
| |
| Suggested Reading for Chapter 5 | |
| |
| |
| |
| Combinatorial Designs | |
| |
| |
| |
| Latin Squares and Graeco-Latin Squares | |
| |
| |
| How Latin Squares Are Used | |
| |
| |
| Randomization for Statistical Purposes | |
| |
| |
| Orthogonal Latin Squares | |
| |
| |
| Euler's 36-Officers Problem | |
| |
| |
| Congruence Modulo an Integer n | |
| |
| |
| Using Arithmetic Modulo n to Construct Latin Squares | |
| |
| |
| Orthogonality and Arithmetic Modulo n | |
| |
| |
| Compositions of Orthogonal Latin Squares | |
| |
| |
| Orthogonal Arrays and Latin Squares | |
| |
| |
| The Construction of a 10 by 10 Graeco-Latin Square | |
| |
| |
| Exercises | |
| |
| |
| |
| Block Designs | |
| |
| |
| How Block Designs Are Used | |
| |
| |
| Basic Relationships among the Parameters | |
| |
| |
| The Incidence Matrix of a Design | |
| |
| |
| An Example of a BIBD | |
| |
| |
| Isomorphism of Designs | |
| |
| |
| The Dual of a Design | |
| |
| |
| Symmetric Designs | |
| |
| |
| The Necessary Conditions Need Not Be Sufficient | |
| |
| |
| Exercises | |
| |
| |
| |
| Construction and Resolvability of Designs | |
| |
| |
| A Problem That Requires a Big Design | |
| |
| |
| Cyclic Designs | |
| |
| |
| Resolvable Designs | |
| |
| |
| [infinity]-Cyclic Designs | |
| |
| |
| Triple Systems | |
| |
| |
| Kirkman's Schoolgirl Problem | |
| |
| |
| Constructing New Designs from Old | |
| |
| |
| Complementary Designs | |
| |
| |
| Unions of Designs | |
| |
| |
| Product Designs | |
| |
| |
| Composition of Designs | |
| |
| |
| The Construction of Kirkman Triple Systems | |
| |
| |
| Exercises | |
| |
| |
| |
| Affine and Projective Planes | |
| |
| |
| Affine Planes | |
| |
| |
| Postulates for Affine Planes | |
| |
| |
| The Concept of a Projective Plane | |
| |
| |
| Basic Facts about Projective Planes | |
| |
| |
| Projective Planes and Block Designs | |
| |
| |
| Planes and Resolvable Designs | |
| |
| |
| Planes and Orthogonal Latin Squares | |
| |
| |
| Exercises | |
| |
| |
| |
| Codes and Designs | |
| |
| |
| The Concept of an Error-Correcting Code | |
| |
| |
| Hamming Distance | |
| |
| |
| Perfect Codes | |
| |
| |
| Linear Codes | |
| |
| |
| The Hamming Codes | |
| |
| |
| Constructing Designs from Codes | |
| |
| |
| Highly Balanced Designs | |
| |
| |
| t-Designs | |
| |
| |
| Codes and Latin Squares | |
| |
| |
| Exercises | |
| |
| |
| Suggested Reading for Chapter 6 | |
| |
| |
| |
| Ordered Sets | |
| |
| |
| |
| Partial Orderings | |
| |
| |
| What Is an Ordering? | |
| |
| |
| Linear Orderings | |
| |
| |
| Maximal and Minimal Elements | |
| |
| |
| The Diagram and Covering Graph | |
| |
| |
| Ordered Sets as Transitive Closures of Digraphs | |
| |
| |
| Trees as Ordered Sets | |
| |
| |
| Weak Orderings | |
| |
| |
| Interval Orders | |
| |
| |
| Exercises | |
| |
| |
| |
| Linear Extensions and Chains | |
| |
| |
| The Idea of a Linear Extension | |
| |
| |
| Dimension of an Ordered Set | |
| |
| |
| Topological Sorting Algorithms | |
| |
| |
| Chains in Ordered Sets | |
| |
| |
| Chain Decompositions of Posets | |
| |
| |
| Finding Chain Decompositions | |
| |
| |
| Alternating Walks | |
| |
| |
| Finding Alternating Walks | |
| |
| |
| Exercises | |
| |
| |
| |
| Lattices | |
| |
| |
| What Is a Lattice? | |
| |
| |
| The Partition Lattice | |
| |
| |
| The Bond Lattice of a Graph | |
| |
| |
| The Algebraic Description of Lattices | |
| |
| |
| Exercises | |
| |
| |
| |
| Boolean Algebras | |
| |
| |
| The Idea of a Complement | |
| |
| |
| Boolean Algebras | |
| |
| |
| Boolean Algebras of Statements | |
| |
| |
| Combinatorial Gate Networks | |
| |
| |
| Boolean Polynomials | |
| |
| |
| DeMorgan's Laws | |
| |
| |
| Disjunctive Normal Form | |
| |
| |
| All Finite Boolean Algebras Are Subset Lattices | |
| |
| |
| Exercises | |
| |
| |
| |
| Mobius Functions | |
| |
| |
| A Review of Inclusion and Exclusion | |
| |
| |
| The Zeta Matrix | |
| |
| |
| The Mobius Matrix | |
| |
| |
| The Mobius Function | |
| |
| |
| Equations That Describe the Mobius Function | |
| |
| |
| The Number-Theoretic Mobius Function | |
| |
| |
| The Number of Connected Graphs | |
| |
| |
| A General Method of Computing Mobius Functions of Lattices | |
| |
| |
| The Mobius Function of the Partition Lattice | |
| |
| |
| Exercises | |
| |
| |
| |
| Products of Orderings | |
| |
| |
| The Idea of a Product | |
| |
| |
| Products of Ordered Sets and Mobius Functions | |
| |
| |
| Products of Ordered Sets and Dimension | |
| |
| |
| Width and Dimension of Ordered Sets | |
| |
| |
| Exercises | |
| |
| |
| Suggested Reading for Chapter 7 | |
| |
| |
| |
| Enumeration under Group Action | |
| |
| |
| |
| Permutation Groups | |
| |
| |
| Permutations and Equivalence Relations | |
| |
| |
| The Group Properties | |
| |
| |
| Powers of Permutations | |
| |
| |
| Permutation Groups | |
| |
| |
| Associating a Permutation with a Geometric Motion | |
| |
| |
| Abstract Groups | |
| |
| |
| Exercises | |
| |
| |
| |
| Groups Acting on Sets | |
| |
| |
| Groups Acting on Sets | |
| |
| |
| Orbits as Equivalence Classes | |
| |
| |
| The Subgroup Fixing a Point and Cosets | |
| |
| |
| The Size of a Subgroup | |
| |
| |
| The Subgroup Generated by a Set | |
| |
| |
| The Cycles of a Permutation | |
| |
| |
| Exercises | |
| |
| |
| |
| Polya's Enumeration Theorem | |
| |
| |
| The Cauchy-Frobenius-Burnside Theorem | |
| |
| |
| Enumerators of Colorings | |
| |
| |
| Generating Functions for Orbits | |
| |
| |
| Using the Orbit-Fixed Point Lemma | |
| |
| |
| Orbits of Functions | |
| |
| |
| The Orbit Enumerator for Functions | |
| |
| |
| How Cycle Structure Interacts with Colorings | |
| |
| |
| The Polya-Redfield Theorem | |
| |
| |
| Exercises | |
| |
| |
| Suggested Reading for Chapter 8 | |
| |
| |
| Answers to Exercises | |
| |
| |
| Index | |