| |
| |
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 | |