Applied Combinatorics QKM9DD2H56

URI	`m2://res/QKM9DD2H56`
Kind	textbook
Creators	Mitchel T. Keller, William T. Trotter
Scope	deferred (no test decides the record, and the classifier has no model)

Expressions

e1: edition

Contents

chapter 1: An Introduction to Combinatorics
section 1.1: Introduction
section 1.2: Enumeration
section 1.3: Combinatorics and Graph Theory
section 1.4: Combinatorics and Number Theory
section 1.5: Combinatorics and Geometry
section 1.6: Combinatorics and Optimization
section 1.7: Sudoku Puzzles
section 1.8: Discussion
chapter 2: Strings, Sets, and Binomial Coefficients
section 2.1: Strings: A First Look
section 2.2: Permutations
section 2.3: Combinations
section 2.4: Combinatorial Proofs
section 2.5: The Ubiquitous Nature of Binomial Coefficients
section 2.6: The Binomial Theorem
section 2.7: Multinomial Coefficients
section 2.8: Discussion
chapter 3: Induction
section 3.1: Introduction
section 3.2: The Positive Integers are Well Ordered
section 3.3: The Meaning of Statements
section 3.4: Binomial Coefficients Revisited
section 3.5: Solving Combinatorial Problems Recursively
subsection 3.5.1: Finding Greatest Common Divisors
subsection 3.5.2: Sorting
section 3.6: Mathematical Induction
section 3.7: Inductive Definitions
section 3.8: Proofs by Induction
section 3.9: Strong Induction
section 3.10: Discussion
chapter 4: Combinatorial Basics
section 4.1: The Pigeon Hole Principle
section 4.2: An Introduction to Complexity Theory
subsection 4.2.1: Three Questions
subsection 4.2.2: Certificates
subsection 4.2.3: Operations
subsection 4.2.4: Input Size
section 4.3: The Big Oh and Little Oh Notations
section 4.4: Exact Versus Approximate
subsection 4.4.1: Approximate and Asymptotic Solutions
subsection 4.4.2: Polynomial Time Algorithms
subsection 4.4.3: $\cgP=\cgN\cgP$?
section 4.5: Discussion
chapter 5: Graph Theory
section 5.1: Basic Notation and Terminology for Graphs
section 5.2: Multigraphs: Loops and Multiple Edges
section 5.3: Eulerian and Hamiltonian Graphs
section 5.4: Graph Coloring
subsection 5.4.1: Bipartite Graphs
subsection 5.4.2: Cliques and Chromatic Number
subsection 5.4.3: Can We Determine Chromatic Number?
section 5.5: Planar Graphs
section 5.6: Counting Labeled Trees
section 5.7: A Digression into Complexity Theory
section 5.8: Discussion
chapter 6: Partially Ordered Sets
section 6.1: Basic Notation and Terminology
section 6.2: Additional Concepts for Posets
section 6.3: Dilworth's Chain Covering Theorem and its Dual
section 6.4: Linear Extensions of Partially Ordered Sets
section 6.5: The Subset Lattice
subsection 6.5.1: Sperner's Theorem
section 6.6: Interval Orders
section 6.7: Finding a Representation of an Interval Order
section 6.8: Dilworth's Theorem for Interval Orders
section 6.9: Discussion
chapter 7: Inclusion-Exclusion
section 7.1: Introduction
section 7.2: The Inclusion-Exclusion Formula
section 7.3: Enumerating Surjections
section 7.4: Derangements
section 7.5: The Euler $\phi$ Function
section 7.6: Discussion
chapter 8: Generating Functions
section 8.1: Basic Notation and Terminology
section 8.2: Another look at distributing apples or folders
section 8.3: Newton's Binomial Theorem
section 8.4: An Application of the Binomial Theorem
section 8.5: Partitions of an Integer
section 8.6: Exponential generating functions
section 8.7: Discussion
chapter 9: Recurrence Equations
section 9.1: Introduction
subsection 9.1.1: Fibonacci numbers
subsection 9.1.2: Recurrences for strings
subsection 9.1.3: Lines and regions in the plane
section 9.2: Linear Recurrence Equations
section 9.3: Advancement Operators
subsection 9.3.1: Constant Coefficient Equations
subsection 9.3.2: Roots and Factors
subsection 9.3.3: What's Special About Zero?
section 9.4: Solving advancement operator equations
subsection 9.4.1: Homogeneous equations
subsection 9.4.2: Nonhomogeneous equations
section 9.5: Formalizing our approach to recurrence equations
subsection 9.5.1: The Principal Theorem
subsection 9.5.2: The Starting Case
subsection 9.5.3: Repeated Roots
subsection 9.5.4: The General Case
section 9.6: Using generating functions to solve recurrences
section 9.7: Solving a nonlinear recurrence
section 9.8: Discussion
chapter 10: Probability
section 10.1: An Introduction to Probability
section 10.2: Conditional Probability and Independent Events
subsection 10.2.1: Independent Events
section 10.3: Bernoulli Trials
section 10.4: Discrete Random Variables
subsection 10.4.1: The Linearity of Expectation
subsection 10.4.2: Implications for Bernoulli Trials
section 10.5: Central Tendency
subsection 10.5.1: Variance and Standard Deviation
section 10.6: Probability Spaces with Infinitely Many Outcomes
section 10.7: Discussion
chapter 11: Applying Probability to Combinatorics
section 11.1: A First Taste of Ramsey Theory
section 11.2: Small Ramsey Numbers
section 11.3: Estimating Ramsey Numbers
section 11.4: Applying Probability to Ramsey Theory
section 11.5: Ramsey's Theorem
section 11.6: The Probabilistic Method
subsection 11.6.1: Gaining Intuition with the Probabilistic Method
section 11.7: Discussion
chapter 12: Graph Algorithms
section 12.1: Minimum Weight Spanning Trees
subsection 12.1.1: Preliminaries
subsection 12.1.2: Kruskal's Algorithm
subsection 12.1.3: Prim's Algorithm
subsection 12.1.4: Comments on Efficiency
section 12.2: Digraphs
section 12.3: Dijkstra's Algorithm for Shortest Paths
subsection 12.3.1: Description of the Algorithm
subsection 12.3.2: Example of Dijkstra's Algorithm
subsection 12.3.3: The Correctness of Dijkstra's Algorithm
section 12.4: Historical Notes
chapter 13: Network Flows
section 13.1: Basic Notation and Terminology
section 13.2: Flows and Cuts
section 13.3: Augmenting Paths
subsection 13.3.1: Caution on Augmenting Paths
section 13.4: The Ford-Fulkerson Labeling Algorithm
section 13.5: A Concrete Example
subsection 13.5.1: How the Labeling Algorithm Halts
section 13.6: Integer Solutions of Linear Programming Problems
chapter 14: Combinatorial Applications of Network Flows
section 14.1: Introduction
section 14.2: Matchings in Bipartite Graphs
section 14.3: Chain partitioning
chapter 15: Pólya's Enumeration Theorem
section 15.1: Coloring the Vertices of a Square
section 15.2: Permutation Groups
subsection 15.2.1: Representing permutations
subsection 15.2.2: Multiplying permutations
section 15.3: Burnside's Lemma
section 15.4: Pólya's Theorem
subsection 15.4.1: The cycle index
subsection 15.4.2: The full enumeration formula
section 15.5: Applications of Pólya's Enumeration Formula
subsection 15.5.1: Counting musical scales
subsection 15.5.2: Enumerating isomers
subsection 15.5.3: Counting nonisomorphic graphs
chapter 16: The Many Faces of Combinatorics
section 16.1: On-line algorithms
subsection 16.1.1: Doing Relatively Well in an On-Line Setting
section 16.2: Extremal Set Theory
section 16.3: Markov Chains
subsection 16.3.1: Absorbing Markov Chains
section 16.4: The Stable Matching Theorem
section 16.5: ZeroOne Matrices
subsection 16.5.1: The Obvious Necessary Condition
section 16.6: Arithmetic Combinatorics
section 16.7: The Lovász Local Lemma
section 16.8: Applying the Local Lemma
appendix A: Epilogue
appendix B: Background Material for Combinatorics
section B.1: Introduction
section B.2: Intersections and Unions
subsection B.2.1: The Meaning of $2$-Letter Words
subsection B.2.2: The Empty Set: Much To Do About Nothing
subsection B.2.3: The First So Many Positive Integers
subsection B.2.4: Subsets, Proper Subsets and Equal Sets
section B.3: Cartesian Products
section B.4: Binary Relations and Functions
section B.5: Finite Sets
section B.6: Notation from Set Theory and Logic
section B.7: Formal Development of Number Systems
subsection B.7.1: Addition as a Binary Operation
section B.8: Multiplication as a Binary Operation
section B.9: Exponentiation
section B.10: Partial Orders and Total Orders
section B.11: A Total Order on Natural Numbers
section B.12: Notation for Natural Numbers
subsection B.12.1: Alternate Versions of Induction
section B.13: Equivalence Relations
section B.14: The Integers as Equivalence Classes of Ordered Pairs
section B.15: Properties of the Integers
section B.16: Obtaining the Rationals from the Integers
subsection B.16.1: Integer Exponents
section B.17: Obtaining the Reals from the Rationals
section B.18: Obtaining the Complex Numbers from the Reals
subsection B.18.1: Decimal Representation of Real Numbers
section B.19: The Zermelo-Fraenkel Axioms of Set Theory
appendix C: List of Notation

Catalogue records

applied_combinatorics: applied_combinatorics (work)