Foundations of Combinatorics with Applications (eBook)

PrefacePart I Counting and Listing Preliminary Reading 1 Basic Counting Introduction 1.1 Lists with Repetitions Allowed Using the Rules of Sum and Product Exercises 1.2 Lists with Repetitions Forbidden Exercises 1.3 Sets Error Correcting Codes Exercises 1.4 Recursions Exercises 1.5 Multisets Exercises Notes and References 2 Functions Introduction 2.1 Some Basic Terminology Terminology for Sets What are Functions? Exercises 2.2 Permutations Exercises 2.3 Other Combinatorial Aspects of Functions Monotonic Functions and Unordered Lists Image and Coimage The Pigeonhole Principle Exercises 2.4 Boolean Functions Exercises Notes and References 3 Decision Trees Introduction 3.1 Basic Concepts of Decision Trees Exercises 3.2 Ranking and Unranking Calculating RANK Calculating UNRANK Gray Codes Exercises 3.3 Backtracking Exercises Notes and References 4 Sieving Methods Introduction Structures Lacking Things Structures with Symmetries 4.1 The Principle of Inclusion and Exclusion Exercises Bonferroni's Inequalities Partially Ordered Sets Exercises 4.2 Listing Structures with Symmetries Exercises 4.3 Counting Structures with Symmetries Proofs Exercises Notes and ReferencesPart II Graphs 5 Basic Concepts in Graph Theory Introduction 5.1 What is a Graph? Exercises 5.2 Equivalence Relations and Unlabeled Graphs Exercises 5.3 Paths and Subgraphs Exercises 5.4 Trees Exercises 5.5 Directed Graphs (Digraphs) Exercises 5.6 Computer Representations of Graphs Exercises Notes and References 6 A Sampler of Graph Topics Introduction 6.1 Spanning Trees Minimum Weight Spanning Trees Lineal Spanning Trees Exercises 6.2 Coloring Graphs Exercises 6.3 Planar Graphs Euler's Relation Exercises The Five Color Theorem Exercises Algorithmic Questions Exercises 6.4 Flows in Networks The Concepts An Algorithm for Constructing a Maximum Flow Exercises Cut Partitions and Cut Sets Exercises 6.5 Probability and Simple Graps Exercises 6.6 Finite State Machines Turing Machines Finite State Machines and Digraphs Exercises Notes and ReferencesPart III Recursion 7 Induction and Recursion Introduction 7.1 Inductive Proofs and Recursive Equations Exercises 7.2 Thinking Recursively Exercises 7.3 Recursive Algorithms Obtaining Information: Merge Sorting Local Descriptions Computer Implementation Exercises 7.4 Divide and Conquer Exercises Notes and References 8 Sorting Theory Introduction 8.1 Limits on Speed Motivation and Proof of the Theorem Exercises 8.2 Software Sorts Binary Insertion Sort Bucket Sort Merge Sorts Quicksort Heapsort Exercises 8.3 Sorting Networks 8.3.1 Speed and Cost Parallelism How Fast Can a Network Be? How Cheap Can a Network Be? Exercises 8.3.2 Proving That a Network Sorts The Batcher Sort Exercises Notes and References 9 Rooted Plane Trees Introduction 9.1 Traversing Trees Depth First Traversals Exercises 9.2 Grammars and RP-Trees Exercises 9.3 Unlabeled Full Binary RP-Trees Exercises Notes and ReferencesPart IV Generating Functions 10 Ordinary Generating Functions Introduction 10.1 What are Generating Functions? Exercises 10.2 Solving a Single Recursion Exercises 10.3 Manipulating Generating Functions Obtaining Recursions Derivatives, Averages and Probability Exercises 10.4 The Rules of Sum and Product Exercises Notes and References 11 Generating Function Topics Introduction 11.1 Systems of Recursions Exercises 11.2 Exponential Generating Functions The Exponential Formula Exercises 11.3 Symmetries and Pólya's Theorem Exercises 11.4 Asymptotic Estimates Recursions Sums of Positive Terms Generating Functions Exercises Notes and ReferencesAppendix A Induction ExercisesAppendix B Rates of Growth and Analysis of Algorithms B.1 The Basic Functions Exercises