| |
| |
| The Basics | |
| |
| |
| Counting and Proofs | |
| |
| |
| Introduction and Summary Try This! Let's Count | |
| |
| |
| The Sum and Product Principles | |
| |
| |
| Preliminaries on Proofs and Disproofs | |
| |
| |
| Pigeons and Correspondences | |
| |
| |
| Where to Go from Here | |
| |
| |
| Sets and Logic | |
| |
| |
| Introduction and Summary | |
| |
| |
| Sets | |
| |
| |
| Logic | |
| |
| |
| Try This! Problems on Sets and Logic | |
| |
| |
| Proof Techniques: Not! Try This! A Tricky Conundrum | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Truth Tellers | |
| |
| |
| Graphs and Functions | |
| |
| |
| Introduction and Summary | |
| |
| |
| Function Introduction Try This! Play with Functions and Graphs | |
| |
| |
| Functions and Counting | |
| |
| |
| Graphs: Definitions and Examples | |
| |
| |
| Isomorphisms | |
| |
| |
| Graphs: Operations and Uses | |
| |
| |
| Try This! More Graph Problems | |
| |
| |
| Ramseyness | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Party Tricks | |
| |
| |
| Bonus 2 Counting with the Characteristic Function | |
| |
| |
| Induction | |
| |
| |
| Introduction and Summary | |
| |
| |
| Induction Try This! Induction | |
| |
| |
| More Examples | |
| |
| |
| The Best Inducktion Proof Ever Try This! More Problems about Induction | |
| |
| |
| Are They or Aren't They? Resolving Grey Ducks | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Small Crooks | |
| |
| |
| Bonus 2 An Induction Song | |
| |
| |
| Algorithms with Ciphers | |
| |
| |
| Introduction and Summary | |
| |
| |
| Algorithms | |
| |
| |
| Modular Arithmetic (and Equivalence Relations) | |
| |
| |
| Cryptography: Some Ciphers | |
| |
| |
| Try This! Encryptoequivalent Modulagorithmic Problems | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Algorithms for Searching Graphs | |
| |
| |
| Bonus 2 Pigeons and Divisibility | |
| |
| |
| Combinatorics | |
| |
| |
| Binomial Coefficients and Pascal's Triangle | |
| |
| |
| Introduction and Summary | |
| |
| |
| You Have a Choice Try This! Investigate a Triangle | |
| |
| |
| Pascal's Triangle | |
| |
| |
| Overcounting Carefully and Reordering at Will | |
| |
| |
| Try This! Play with Powers and Permutations | |
| |
| |
| Binomial Basics | |
| |
| |
| Combinatorial Proof Try This! Pancakes and Proofs | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Sorting Bubbles in Order of Size | |
| |
| |
| Bonus 2 Mastermind | |
| |
| |
| Balls and Boxes and PIE-Counting Techniques | |
| |
| |
| Introduction and Summary | |
| |
| |
| Combinatorial Problem Types Try This! Let's Have Some PIE | |
| |
| |
| Combinatorial Problem Solutions and Strategies | |
| |
| |
| Let's Explain Our PIE! Try This! What Are the Balls and What Are the Boxes? And Do You Want Some PIE? | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Linear and Integer Programming | |
| |
| |
| Recurrences | |
| |
| |
| Introduction and Summary | |
| |
| |
| Fibonacci Numbers and Identities | |
| |
| |
| Recurrences and Integer Sequences and Induction Try This! Sequences and Fibonacci Identities | |
| |
| |
| Naive Techniques for Finding Closed Forms and Recurrences | |
| |
| |
| Arithmetic Sequences and Finite Differences | |
| |
| |
| Try This! Recurrence Exercises | |
| |
| |
| Geometric Sequences and the Characteristic Equation Try This! Find Closed Forms for These Recurrence Relations! | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Recurring Stories | |
| |
| |
| Cutting up Food (Counting and Geometry) | |
| |
| |
| Introduction and Summary | |
| |
| |
| Try This! Slice Pizza (and a Yam) | |
| |
| |
| Pizza Numbers Try This! Spaghetti, Yams, and More | |
| |
| |
| Yam, Spaghetti and Pizza Numbers | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Geometric Gems | |
| |
| |
| Graph Theory | |
| |
| |
| Trees | |
| |
| |
| Introduction and Summary | |
| |
| |
| Basic Facts about Trees Try This! Spanning Trees | |
| |
| |
| Spanning Tree Algorithms | |
| |
| |
| Binary Trees Try This! Binary Trees and Matchings | |
| |
| |
| Matchings | |
| |
| |
| Backtracking | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: The Branch-and-Bound Technique in Integer Programming | |
| |
| |
| Euler's Formula and Applications | |
| |
| |
| Introduction and Summary Try This! Planarity Explorations | |
| |
| |
| Planarity | |
| |
| |
| A Lovely Story | |
| |
| |
| Or, Are Emus Full?: A Theorem and a Proof | |
| |
| |
| Applications of Euler's Formula | |
| |
| |
| Try This! Applications of Euler's Formula | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Topological Graph Theory | |
| |
| |
| Graph Traversals | |
| |
| |
| Introduction and Summary Try This! Euler Traversals | |
| |
| |
| Euler Paths and Circuits | |
| |
| |
| Hamilton Circuits, the Traveling Salesperson Problem, and Dijkstra's Algorithm Try This!-Do This!-Try This! | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Digraphs, Euler Traversals, and RNA Chains | |
| |
| |
| Bonus 2 Network Flows | |
| |
| |
| Bonus 3 Two Hamiltonian Theorems | |
| |
| |
| Graph Coloring | |
| |
| |
| Introduction and Summary Try This! Coloring Vertices and Edges | |
| |
| |
| Introduction to Coloring | |
| |
| |
| Try This! Let's Think about Coloring | |
| |
| |
| Coloring and Things (Graphs and Concepts) That Have Come Before | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: The Four-Color Theorem | |
| |
| |
| Other Material | |
| |
| |
| Probability and Expectation | |
| |
| |
| Introduction and Summary | |
| |
| |
| What Is Probability, Exactly? | |
| |
| |
| High Expectations | |
| |
| |
| You are Probably Expected to Try This! | |
| |
| |
| Conditional Probability and Independence | |
| |
| |
| Try This! . . . Probably, Under Certain Conditions | |
| |
| |
| Higher Expectations | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: Ramsey Numbers and the Probabilistic Method | |
| |
| |
| Fun with Cardinality | |
| |
| |
| Introduction and Summary | |
| |
| |
| Read This! Parasitology, The Play | |
| |
| |
| How Big Is Infinite? Try This! Investigating the Play | |
| |
| |
| How High Can We Count? | |
| |
| |
| Where to Go from Here | |
| |
| |
| Bonus: The Schr�der-Bernstein Theorem | |
| |
| |
| Additional Problems | |
| |
| |
| Solutions to Check Yourself Problems | |
| |
| |
| The Greek Alphabet and Some Uses for Some Letters | |
| |
| |
| List of Symbols | |
| |
| |
| Glossary | |
| |
| |
| Bibliography | |
| |
| |
| Problems and Instructor Notes appear at the end of each chapter | |